Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Вычисление отсечки для скользящего окна по количес

Автор: TrnasitionMan 27.12.2016, 10:40

Друзья, Направьте на путь истинный. Пытаюсь сообразить алгоритм для следующей задачи. Причем, алгоритм хочется получить простой, так как аппаратные ресурсы скромные, но ум постепенно заходит за разум. Итак, задача. Раз в секунду на входное устройство поступает сигнал, который может быть логическим нулем или единицей. Задача поднять флаг, если количество единиц за заданный промежуток времени превысит установленный лимит. Т.е. в наличие бесконечный дискретный поток данных, в которых надо отлавливать единички и смотреть сколько единичек поймалось за установленный период времени. Пример 1: Окно времени = 40 секунд Количество единиц = 8 штук Пример 2: Окно времени = 3600 секунд Количество единиц = 6 штук Решать в лоб, т.е. заводить массив размерностью в окно времени, а затем каждую итерацию его двигать, очень не хочется. На другом форуме предлагался вариант со счетчиком: Окно времени = 3600 секунд Количество единиц = 1200 Доля (окно на количество единиц) = 3 Изначальное состояние счетчика = 3600+3, при 0 на входе увеличиваем значение счетчика на 1, если значение счетчика меньше изначального состояния. При 1 уменьшаем значение счетчика на 3. Флаг поднимается когда счетчик <=0. В целом он работает, но получаются неточности (в сторону увеличения) при получении на входе последовательности из 010101010101. И чем больше значения количества единиц и окна времени, тем больше возникает ошибка. Пока попробовал различные варианты, включая кучу и два счетчика. Но как-то не выходит каменный цветок. Срубается на описанной выше последовательности. Что думаете?

Автор: Akina 27.12.2016, 11:09

От хранения состояний за текущее окно никуда тебе не деться - или ты будешь определять состояние только с некоей долей вероятности. Так что можно только оптимизировать решение с хранением. Я бы делал так: 1) Создаём массив размером в окно времени, заполняем нулями.  2) Создаём указатель на текущее местоположение, равный началу массива.  3) Создаём счётчик, равный нулю.  При поступлении очередного сигнала: Счётчик = Счётчик - Значение по текущему указателю + Поступивший сигнал Элемент по текущему указателю = Поступивший сигнал Текущий указатель = (Текущий указатель + 1) MOD Размер окна Если (Счётчик >= Порог) Флаг = 1 Иначе Флаг = 0 Профиты: 1) Не нужно двигать элементы массива. 2) Минимальное количество вычислений по получению нового значения счётчика. 3) Хранение актуального значения счётчика.

Автор: TrnasitionMan 27.12.2016, 11:54

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

Автор: Lipetsk 27.12.2016, 12:28

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

Автор: TrnasitionMan 27.12.2016, 13:29

Цитата(Lipetsk @ 27.12.2016,  12:28) если единички редки, а промежутки велики, то можно запоминать только моменты времени, в которые были получены единички Последовательность поступления единичек никак не нормируется. Совершенно стохастический процесс. Насчет сохранения времени я думал, возможно это вариант, тем более, что время в системе считается. Пока хочу разобраться со счетчиками.

Автор: Akina 27.12.2016, 13:45

Цитата(TrnasitionMan @  27.12.2016,  11:40 ) На другом форуме предлагался вариант со счетчиком: Окно времени = 3600 секунд Количество единиц = 1200 Доля (окно на количество единиц) = 3 Изначальное состояние счетчика = 3600+3, при 0 на входе увеличиваем значение счетчика на 1, если значение счетчика меньше изначального состояния. При 1 уменьшаем значение счетчика на 3. Флаг поднимается когда счетчик <=0. Если я верно понимаю, то: - начальное значение счётчика равно (ОкноВремени)+(ОкноВремени/КоличествоЕдиниц) - при нуле счётчик увеличивается на 1 - при единице счётчик уменьшается на (ОкноВремени/КоличествоЕдиниц).  Верно? Добавлено через 5 минут и 27 секунд Да, проверьте-ка этот алгоритм на потоке (001)*N. По моим подсчётам после 3600 значений счётчик будет равен: 3600+3 (начальное значение) плюс 2400 (количество нулей) минус  3*1200 (количество единиц) ИТОГО (3600+3+2400-3*1200)=2403 > 0. А флаг-то уже надо подымать...

Автор: TrnasitionMan 27.12.2016, 13:58

Цитата(Akina @ 27.12.2016,  13:45) Цитата(TrnasitionMan @  27.12.2016,  11:40 ) На другом форуме предлагался вариант со счетчиком: Окно времени = 3600 секунд Количество единиц = 1200 Доля (окно на количество единиц) = 3 Изначальное состояние счетчика = 3600+3, при 0 на входе увеличиваем значение счетчика на 1, если значение счетчика меньше изначального состояния. При 1 уменьшаем значение счетчика на 3. Флаг поднимается когда счетчик <=0. Если я верно понимаю, то: - начальное значение счётчика равно (ОкноВремени)+(ОкноВремени/КоличествоЕдиниц) - при нуле счётчик увеличивается на 1 - при единице счётчик уменьшается на (ОкноВремени/КоличествоЕдиниц).  Верно? Добавлено @ 13:50 Да, проверьте-ка этот алгоритм на потоке (001)*N. По моим подсчётам после 3600 значений счётчик будет равен: 3600+3 (начальное значение) плюс 2400 (количество нулей) минус  3*1200 (количество единиц) ИТОГО (3600+3+2400-3*1200)=2403 > 0. А флаг-то уже надо подымать... Да, понимаете предложенный алгоритм верно, за исключением того, что счетчик не увеличивается более окно+окно/доля и не опускается менее 0, это условия алгоритма.  Но, я его погонял несколько раз и там есть проблема связанная с чередованием нулей и единиц. В этом случае флаг поднимается позже чем следует. Причем чем больше величины, тем больше получается разбег. Сейчас я протестировал алгоритм с четырьмя переменными-счетчиками, работает намного стабильнее, но в некоторых случаях срабатывает на Window+1. Что не есть сильно критично, но просто не красиво. Попробую его нарисовать, для наглядности.... Пока он в виде формул в экселе.

Автор: 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; } Что думаете?

Автор: Akina 27.12.2016, 14:25

Цитата(TrnasitionMan @  27.12.2016,  14:58 ) понимаете предложенный алгоритм верно, за исключением того, что счетчик не увеличивается более окно+окно/доля и не опускается менее 0, это условия алгоритма.  В таком случае предложенный расчёт надо подкорректировать - итоговое значение счётчика будет 2401, но это всё равно куда как больше нуля... косяк, короче, а не метода. Цитата(TrnasitionMan @  27.12.2016,  15:19 ) Что думаете? Да вот думаю, не написать ли в отместку свой ответ на корейском...

Автор: TrnasitionMan 28.12.2016, 10:42

[QUOTE=Akina,27.12.2016,  14:25] Цитата(TrnasitionMan @  27.12.2016,  14:58 ) Да вот думаю, не написать ли в отместку свой ответ на корейском... Если попробовать описать его словами, то получается нечто следующее: Переменные: Флаг Входящий поток Окно Дозволенное время работы Счетчик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 достигает размера Окно.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)