Вычисление отсечки для скользящего окна по количес

 
0
 
Algorithmen
ava
TrnasitionMan | 27.12.2016, 10:40
Друзья,

Направьте на путь истинный. Пытаюсь сообразить алгоритм для следующей задачи. Причем, алгоритм хочется получить простой, так как аппаратные ресурсы скромные, но ум постепенно заходит за разум.

Итак, задача. Раз в секунду на входное устройство поступает сигнал, который может быть логическим нулем или единицей. Задача поднять флаг, если количество единиц за заданный промежуток времени превысит установленный лимит.

Т.е. в наличие бесконечный дискретный поток данных, в которых надо отлавливать единички и смотреть сколько единичек поймалось за установленный период времени.

Пример 1:
Окно времени = 40 секунд
Количество единиц = 8 штук

Пример 2:
Окно времени = 3600 секунд
Количество единиц = 6 штук

Решать в лоб, т.е. заводить массив размерностью в окно времени, а затем каждую итерацию его двигать, очень не хочется. На другом форуме предлагался вариант со счетчиком:
Окно времени = 3600 секунд
Количество единиц = 1200
Доля (окно на количество единиц) = 3

Изначальное состояние счетчика = 3600+3, при 0 на входе увеличиваем значение счетчика на 1, если значение счетчика меньше изначального состояния. При 1 уменьшаем значение счетчика на 3. Флаг поднимается когда счетчик <=0.

В целом он работает, но получаются неточности (в сторону увеличения) при получении на входе последовательности из 010101010101. И чем больше значения количества единиц и окна времени, тем больше возникает ошибка.

Пока попробовал различные варианты, включая кучу и два счетчика. Но как-то не выходит каменный цветок. Срубается на описанной выше последовательности.

Что думаете?
Kommentare (9)
ava
Akina | 27.12.2016, 11:09 #
От хранения состояний за текущее окно никуда тебе не деться - или ты будешь определять состояние только с некоей долей вероятности. Так что можно только оптимизировать решение с хранением.

Я бы делал так:

1) Создаём массив размером в окно времени, заполняем нулями.
2) Создаём указатель на текущее местоположение, равный началу массива.
3) Создаём счётчик, равный нулю.

При поступлении очередного сигнала:

Счётчик = Счётчик - Значение по текущему указателю + Поступивший сигнал
Элемент по текущему указателю = Поступивший сигнал
Текущий указатель = (Текущий указатель + 1) MOD Размер окна
Если (Счётчик >= Порог) Флаг = 1 Иначе Флаг = 0

Профиты:
1) Не нужно двигать элементы массива.
2) Минимальное количество вычислений по получению нового значения счётчика.
3) Хранение актуального значения счётчика.
ava
TrnasitionMan | 27.12.2016, 11:54 #
Нутром чую, что можно обойтись вообще без массива или его аналога.

В текущей версии алгоритма используется два счетчика, срабатывание стабильное в рамках Window или Window+1...

На куралесицу с 01010101 срабатывание нормально.
ava
Lipetsk | 27.12.2016, 12:28 #
если единички редки, а промежутки велики, то можно запоминать только моменты времени, в которые были получены единички
ava
TrnasitionMan | 27.12.2016, 13:29 #
Цитата (Lipetsk @ 27.12.2016,  12:28)
если единички редки, а промежутки велики, то можно запоминать только моменты времени, в которые были получены единички

Последовательность поступления единичек никак не нормируется. Совершенно стохастический процесс.

Насчет сохранения времени я думал, возможно это вариант, тем более, что время в системе считается. Пока хочу разобраться со счетчиками.
ava
Akina | 27.12.2016, 13:45 #
Цитата (TrnasitionMan @  27.12.2016,  11:40 findReferencedText)
На другом форуме предлагался вариант со счетчиком:

Окно времени = 3600 секунд

Количество единиц = 1200

Доля (окно на количество единиц) = 3



Изначальное состояние счетчика = 3600+3, при 0 на входе увеличиваем значение счетчика на 1, если значение счетчика меньше изначального состояния. При 1 уменьшаем значение счетчика на 3. Флаг поднимается когда счетчик <=0.

Если я верно понимаю, то:
- начальное значение счётчика равно (ОкноВремени)+(ОкноВремени/КоличествоЕдиниц)
- при нуле счётчик увеличивается на 1
- при единице счётчик уменьшается на (ОкноВремени/КоличествоЕдиниц).
Верно?
ava
TrnasitionMan | 27.12.2016, 13:58 #
Цитата (Akina @ 27.12.2016,  13:45)
Цитата (TrnasitionMan @  27.12.2016,  11:40 findReferencedText)
На другом форуме предлагался вариант со счетчиком:


Окно времени = 3600 секунд


Количество единиц = 1200


Доля (окно на количество единиц) = 3





Изначальное состояние счетчика = 3600+3, при 0 на входе увеличиваем значение счетчика на 1, если значение счетчика меньше изначального состояния. При 1 уменьшаем значение счетчика на 3. Флаг поднимается когда счетчик <=0.


Если я верно понимаю, то:

- начальное значение счётчика равно (ОкноВремени)+(ОкноВремени/КоличествоЕдиниц)

- при нуле счётчик увеличивается на 1

- при единице счётчик уменьшается на (ОкноВремени/КоличествоЕдиниц). 

Верно?



später ergänzt:

Да, проверьте-ка этот алгоритм на потоке (001)*N. По моим подсчётам после 3600 значений счётчик будет равен:



3600+3 (начальное значение)

плюс

2400 (количество нулей)

минус 

3*1200 (количество единиц)



ИТОГО (3600+3+2400-3*1200)=2403 > 0.



А флаг-то уже надо подымать...

Да, понимаете предложенный алгоритм верно, за исключением того, что счетчик не увеличивается более окно+окно/доля и не опускается менее 0, это условия алгоритма.

Но, я его погонял несколько раз и там есть проблема связанная с чередованием нулей и единиц. В этом случае флаг поднимается позже чем следует. Причем чем больше величины, тем больше получается разбег.

Сейчас я протестировал алгоритм с четырьмя переменными-счетчиками, работает намного стабильнее, но в некоторых случаях срабатывает на Window+1. Что не есть сильно критично, но просто не красиво. Попробую его нарисовать, для наглядности.... Пока он в виде формул в экселе (самый правый вариант).
ava
TrnasitionMan | 27.12.2016, 14:19 #
Так, текущая версия с двумя счетчиками и их предыдущими состояниями:

// Initial values
unsigned long window=40;
unsigned long work=7;
// Working values
unsigned long counter1=0;
unsigned long counter2=0;
unsigned long counter1p=0;
unsigned long counter2p=0;
bool failure=false;
void setup() {
    pinMode(1,INPUT_PULLUP);
    counter2p=work;
}

void loop() {
    int value=digitalRead(1);
    // Updating Counter 1
    if(value==0 && counter1p<window){
        counter1=counter1p+1;
    }else{
        if(value==1 && counter1p>0){
            counter1=counter1p-1;
        }else{
            counter1=counter1p;
        }
    }
    // Updating Counter 2
    if (value==0 && counter1p==(window-work) && counter2p<work){
        counter2=counter2p+1;
    }else{
        if(value==1 && counter2p>0){
            counter2=counter2p-1;
        }else{
            counter2=counter2p;
        }
    }
    // Updating Flag
    if (counter2==0 || failure==true){
        failure=true;
    }
    // Updating previous counters values
    counter1p=counter1;
    counter2p=counter2;
}



Что думаете?
ava
Akina | 27.12.2016, 14:25 #
Цитата (TrnasitionMan @  27.12.2016,  14:58 findReferencedText)
понимаете предложенный алгоритм верно, за исключением того, что счетчик не увеличивается более окно+окно/доля и не опускается менее 0, это условия алгоритма. 

В таком случае предложенный расчёт надо подкорректировать - итоговое значение счётчика будет 2401, но это всё равно куда как больше нуля... косяк, короче, а не метода.

Цитата (TrnasitionMan @  27.12.2016,  15:19 findReferencedText)
Что думаете?

Да вот думаю, не написать ли в отместку свой ответ на корейском...
ava
TrnasitionMan | 28.12.2016, 10:42 #
[QUOTE=Akina,27.12.2016,  14:25]
Цитата (TrnasitionMan @  27.12.2016,  14:58 findReferencedText)


Да вот думаю, не написать ли в отместку свой ответ на корейском...

Если попробовать описать его словами, то получается нечто следующее:
Переменные:
Флаг
Входящий поток
Окно
Дозволенное время работы
Счетчик1
Предыдущее состояние Счетчик1
Счетчик2
Предыдущее состояние Счетчик2

Начальное состояние:
Счетчик1=Предыдущее состояние Счетчик1=0
Счетчик2=Дозволенное время работы
Предыдущее состояние Счетчик2=0
Флаг=ложь

Условия изменения переменных:
Флаг=истина когда Счетчик2=0 или когда Флаг был истина в предыдущей итерации.

Условие увеличения Счетчик1:
Увеличивается на 1, когда Входящий поток =0 и пока Предыдущее состояние Счетчик1 меньше Окно

Условие увеличения Счетчик2:
Увеличивается на 1, когда Входящий поток =0, Предыдущее состояние Счетчик1 равно разницы Окно и Дозволенное время работы, Предыдущее состояние Счетчик2 меньше Дозволенное время работы. Все по логическому И.

Условие уменьшения Счетчик1:
Уменьшается на 1, когда Входящий поток = 1 и Предыдущее состояние Счетчик 1>0

Условие уменьшения Счетчик2:
Уменьшается на 1, когда Входящий поток = 1 и Предыдущее состояние Счетчик2 >0


Суть алгоритма на движении двух счетчиков. Вначале, когда алгоритм только запущен, движение идет разнонаправленное, после прохождения времени Окно, движение во время остуствия поступления единичек однонаправленное. Фишка в том, что Счетчик2 растет, только когда Счетчик1 достигает размера Окно.
Registrieren Sie sich oder melden Sie sich an, um schreiben zu können.
Unternehmen des Tages
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Mitwirkende
advanced
Absenden