|
|
|
TrnasitionMan |
|
|||
Новичок Профиль Группа: Участник Сообщений: 6 Регистрация: 27.12.2016 Репутация: нет Всего: нет |
Друзья,
Направьте на путь истинный. Пытаюсь сообразить алгоритм для следующей задачи. Причем, алгоритм хочется получить простой, так как аппаратные ресурсы скромные, но ум постепенно заходит за разум. Итак, задача. Раз в секунду на входное устройство поступает сигнал, который может быть логическим нулем или единицей. Задача поднять флаг, если количество единиц за заданный промежуток времени превысит установленный лимит. Т.е. в наличие бесконечный дискретный поток данных, в которых надо отлавливать единички и смотреть сколько единичек поймалось за установленный период времени. Пример 1: Окно времени = 40 секунд Количество единиц = 8 штук Пример 2: Окно времени = 3600 секунд Количество единиц = 6 штук Решать в лоб, т.е. заводить массив размерностью в окно времени, а затем каждую итерацию его двигать, очень не хочется. На другом форуме предлагался вариант со счетчиком: Окно времени = 3600 секунд Количество единиц = 1200 Доля (окно на количество единиц) = 3 Изначальное состояние счетчика = 3600+3, при 0 на входе увеличиваем значение счетчика на 1, если значение счетчика меньше изначального состояния. При 1 уменьшаем значение счетчика на 3. Флаг поднимается когда счетчик <=0. В целом он работает, но получаются неточности (в сторону увеличения) при получении на входе последовательности из 010101010101. И чем больше значения количества единиц и окна времени, тем больше возникает ошибка. Пока попробовал различные варианты, включая кучу и два счетчика. Но как-то не выходит каменный цветок. Срубается на описанной выше последовательности. Что думаете? |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
От хранения состояний за текущее окно никуда тебе не деться - или ты будешь определять состояние только с некоей долей вероятности. Так что можно только оптимизировать решение с хранением.
Я бы делал так: 1) Создаём массив размером в окно времени, заполняем нулями. 2) Создаём указатель на текущее местоположение, равный началу массива. 3) Создаём счётчик, равный нулю. При поступлении очередного сигнала: Счётчик = Счётчик - Значение по текущему указателю + Поступивший сигнал Элемент по текущему указателю = Поступивший сигнал Текущий указатель = (Текущий указатель + 1) MOD Размер окна Если (Счётчик >= Порог) Флаг = 1 Иначе Флаг = 0 Профиты: 1) Не нужно двигать элементы массива. 2) Минимальное количество вычислений по получению нового значения счётчика. 3) Хранение актуального значения счётчика. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
TrnasitionMan |
|
|||
Новичок Профиль Группа: Участник Сообщений: 6 Регистрация: 27.12.2016 Репутация: нет Всего: нет |
Нутром чую, что можно обойтись вообще без массива или его аналога.
В текущей версии алгоритма используется два счетчика, срабатывание стабильное в рамках Window или Window+1... На куралесицу с 01010101 срабатывание нормально. |
|||
|
||||
Lipetsk |
|
|||
в форме ;) Профиль Группа: Участник Сообщений: 180 Регистрация: 28.1.2009 Где: Липецк Репутация: 2 Всего: 5 |
если единички редки, а промежутки велики, то можно запоминать только моменты времени, в которые были получены единички
|
|||
|
||||
TrnasitionMan |
|
|||
Новичок Профиль Группа: Участник Сообщений: 6 Регистрация: 27.12.2016 Репутация: нет Всего: нет |
Последовательность поступления единичек никак не нормируется. Совершенно стохастический процесс. Насчет сохранения времени я думал, возможно это вариант, тем более, что время в системе считается. Пока хочу разобраться со счетчиками. |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Если я верно понимаю, то: - начальное значение счётчика равно (ОкноВремени)+(ОкноВремени/КоличествоЕдиниц) - при нуле счётчик увеличивается на 1 - при единице счётчик уменьшается на (ОкноВремени/КоличествоЕдиниц). Верно? Добавлено через 5 минут и 27 секунд Да, проверьте-ка этот алгоритм на потоке (001)*N. По моим подсчётам после 3600 значений счётчик будет равен: 3600+3 (начальное значение) плюс 2400 (количество нулей) минус 3*1200 (количество единиц) ИТОГО (3600+3+2400-3*1200)=2403 > 0. А флаг-то уже надо подымать... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
TrnasitionMan |
|
|||
Новичок Профиль Группа: Участник Сообщений: 6 Регистрация: 27.12.2016 Репутация: нет Всего: нет |
Да, понимаете предложенный алгоритм верно, за исключением того, что счетчик не увеличивается более окно+окно/доля и не опускается менее 0, это условия алгоритма. Но, я его погонял несколько раз и там есть проблема связанная с чередованием нулей и единиц. В этом случае флаг поднимается позже чем следует. Причем чем больше величины, тем больше получается разбег. Сейчас я протестировал алгоритм с четырьмя переменными-счетчиками, работает намного стабильнее, но в некоторых случаях срабатывает на Window+1. Что не есть сильно критично, но просто не красиво. Попробую его нарисовать, для наглядности.... Пока он в виде формул в экселе. Это сообщение отредактировал(а) TrnasitionMan - 27.12.2016, 14:00 |
|||
|
||||
TrnasitionMan |
|
|||
Новичок Профиль Группа: Участник Сообщений: 6 Регистрация: 27.12.2016 Репутация: нет Всего: нет |
Так, текущая версия с двумя счетчиками и их предыдущими состояниями:
Что думаете? Это сообщение отредактировал(а) TrnasitionMan - 27.12.2016, 14:20 |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
В таком случае предложенный расчёт надо подкорректировать - итоговое значение счётчика будет 2401, но это всё равно куда как больше нуля... косяк, короче, а не метода. Да вот думаю, не написать ли в отместку свой ответ на корейском... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
TrnasitionMan |
|
|||
Новичок Профиль Группа: Участник Сообщений: 6 Регистрация: 27.12.2016 Репутация: нет Всего: нет |
[QUOTE=Akina,27.12.2016, 14:25]
Если попробовать описать его словами, то получается нечто следующее: Переменные: Флаг Входящий поток Окно Дозволенное время работы Счетчик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 достигает размера Окно. |
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |