Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Вычисление отсечки для скользящего окна по количес, Хочется решить задачу при помощи  
:(
    Опции темы
TrnasitionMan
  Дата 27.12.2016, 10:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 6
Регистрация: 27.12.2016

Репутация: нет
Всего: нет



Друзья,

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

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

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

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

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

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

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

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

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

Что думаете?
PM MAIL   Вверх
Akina
Дата 27.12.2016, 11:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



От хранения состояний за текущее окно никуда тебе не деться - или ты будешь определять состояние только с некоей долей вероятности. Так что можно только оптимизировать решение с хранением.

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

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

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

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

Профиты:
1) Не нужно двигать элементы массива.
2) Минимальное количество вычислений по получению нового значения счётчика.
3) Хранение актуального значения счётчика.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
TrnasitionMan
Дата 27.12.2016, 11:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 6
Регистрация: 27.12.2016

Репутация: нет
Всего: нет



Нутром чую, что можно обойтись вообще без массива или его аналога.

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

На куралесицу с 01010101 срабатывание нормально.
PM MAIL   Вверх
Lipetsk
Дата 27.12.2016, 12:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


в форме ;)
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 28.1.2009
Где: Липецк

Репутация: 2
Всего: 5



если единички редки, а промежутки велики, то можно запоминать только моменты времени, в которые были получены единички
PM   Вверх
TrnasitionMan
Дата 27.12.2016, 13:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 6
Регистрация: 27.12.2016

Репутация: нет
Всего: нет



Цитата(Lipetsk @ 27.12.2016,  12:28)
если единички редки, а промежутки велики, то можно запоминать только моменты времени, в которые были получены единички

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

Насчет сохранения времени я думал, возможно это вариант, тем более, что время в системе считается. Пока хочу разобраться со счетчиками.

PM MAIL   Вверх
Akina
Дата 27.12.2016, 13:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



Цитата(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.

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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
TrnasitionMan
Дата 27.12.2016, 13:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 6
Регистрация: 27.12.2016

Репутация: нет
Всего: нет



Цитата(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:00
PM MAIL   Вверх
TrnasitionMan
Дата 27.12.2016, 14:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 6
Регистрация: 27.12.2016

Репутация: нет
Всего: нет



Так, текущая версия с двумя счетчиками и их предыдущими состояниями:
Код

// 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;
}



Что думаете?

Это сообщение отредактировал(а) TrnasitionMan - 27.12.2016, 14:20
PM MAIL   Вверх
Akina
Дата 27.12.2016, 14:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



Цитата(TrnasitionMan @  27.12.2016,  14:58 Найти цитируемый пост)
понимаете предложенный алгоритм верно, за исключением того, что счетчик не увеличивается более окно+окно/доля и не опускается менее 0, это условия алгоритма. 

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

Цитата(TrnasitionMan @  27.12.2016,  15:19 Найти цитируемый пост)
Что думаете?

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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
TrnasitionMan
Дата 28.12.2016, 10:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 6
Регистрация: 27.12.2016

Репутация: нет
Всего: нет



[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 достигает размера Окно.

PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1515 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.