Во многих задачах, связанных с обработкой данных, возникает проблема нехватки памяти для хранения их.
Например, с датчика непрерывно поступают данные с частотой дискретизации F=1000 Гц, которые сохраняются в массиве. Однако, для анализа данных используется конечное временное окно наблюдения, например, T=10 секунд. Таким образом, при поступлении нового отсчета данных необходимы лишь последние N=T*F=10000 значений.
Подобные задачи возникают при фильтрации сигналов датчиков, построении индикаторов для торговли на биржах, в нейронных сетях.
Возможно несколько вариантов накопления данных для обработки в реальном масштабе времени:
1: Массив неограниченного объема. Недостаток: Избыточные затраты памяти.
2: Два массива по N элементов. При заполнении одного переключаемся на другой. Недостаток: сложность непрерывной обработки данных. Избыточные затраты памяти.
3: Массив N элементов. При заполнении очищаем. Недостаток: невозможность непрерывной обработки.
4: Массив N элементов. Сдвиг на элемент влево и запись нового элемента вместо N-го. Недостаток: Относительно большие затраты времени на сдвиг массива.
5: Массив N элементов циклический. Этот метод является самым эффективным из перечисленных. Для его реализации необходимо номер очередного элемента данных преобразовать в индекс элемента массива по модулю N.
Метод такого преобразования зависит от языка программирования. Рассмотрим это на примерах.
Например: Используем язык программирования с возможностью явного указания типа переменных. Если N=256, для хранения индекса применяем тип unsigned char; N=65536 - применяем тип unsigned short, N=4294967296 - применяем тип unsigned long.
При других значениях N, для быстрого преобразования номера отсчета в индекс элемента в массиве эффективно выбирать N как степень двойки, т.е. из ряда 8,16,32,64,128,256,512,1024,2048,4096…65536.
Тогда индекс “I” по номеру элемента” j“ можно вычислить через & - бинарное "И" в виде: i=j&(N-1).
Если в языке программирования нет бинарных операций, то индекс можно вычислить через остаток от целочисленного деления i=j%N.
Целочисленное деление исполняется дольше, чем бинарное "И".
В любом случае, применение циклического массива существенно уменьшает затраты времени и памяти при обработке больших объемов данных в реальном времени.
Кроме того, циклические массивы удобно использовать для организации стеков и очередей.
Тот факт, что величина индекса массива не может превышать размер массива полностью исключает ошибки из-за выхода за пределы области расположения массива.
В скриптовых языках циклические массивы позволяют практически исключить необходимость обращаться в процессе работы к куче и к сборщику мусора.
Вариант теста на Lua:
local size=100000; local N=1024; local M=N-1; local t={}; for i=0,N do t[i]=0 end
start=os.clock() for i = 1, size do t[i]=i; end time = 1000000*(os.clock()- start)/size
print("1.Неогр.объем(мкс):", time)
local function shift(t) for j=2,N do t[j-1]=t[j] end end
start=os.clock() for i = 1, size do shift(t) t[N]=i; end time = 1000000*(os.clock()- start)/size
print("4.Сдвиг влево(мкс):", time)
start=os.clock() for i = 1, size do t[i&M]=i; end time = 1000000*(os.clock()- start)/size
print("5.Цикл., бинарное'И'(мкс):", time)
start=os.clock() for i = 1, size do t[i%N]=i; end time = 1000000*(os.clock()- start)/size
print("5.Цикл., остат.целоч.деление(мкс):", time)результат теста для N=1024:
1.Неогр.объем(мкс): 0.02
4.Сдвиг влево(мкс): 13.07
5.Цикл., бинарное'И'(мкс): 0.01
5.Цикл., остат.целоч.деление(мкс): 0.02
Комментарии (35)
SpiderEkb
13.07.2024 09:23+3индекс можно вычислить через целочисленное деление i=j%N
В том же С % - это не целочисленное деления, а остаток от целочисленного деления.
int a = 5, b = 4, c; c = b / a; // Целочисленное деление - с = 0 c = b % a; // Остаток от целочисленного деления - с = 4Мысль правильная, формулировка - нет.
И да. "Циклический массив" (он же "кольцевой буфер") вещь давно известная и столь же давно применяемая.
saluev
13.07.2024 09:23+4"Недостаток: сложность непрерывной обработки данных" — он ведь и для циклического массива присущ. Если функция обработки ожидает указатель на данные, идущие подряд в памяти — вызвать её нельзя. А это, например, BLAS/LAPACK и функции из прочих быстрых библиотек.
Если бы мне нужно было уметь очень быстро обрабатывать текущий буфер, я бы сделал массив длины
с записью в два места сразу. Пример для N=3:[_, _, _, _, _] [1, _, _, _, _] [1, 2, _, _, _] [1, 2, 3, _, _] [4, 2, 3, 4, _] ^^^^^^^ [4, 5, 3, 4, 5] ^^^^^^^ [4, 5, 6, 4, 5] ^^^^^^^ [7, 5, 6, 7, 5] ^^^^^^^Так я занимаю O(N) памяти, имею запись за O(1) и всегда имею на руках актуальный срез данных, расположенный в памяти линейно.
nikolz Автор
13.07.2024 09:23"Недостаток: сложность непрерывной обработки данных" — он ведь и для циклического массива присущ.
Полагаю, что для циклического этого недостатка нет, так как нет затрат времени на дополнительные действия по извлечению данных, кроме бинарной операции, по сравнению с неограниченным массивом.
adeshere
13.07.2024 09:23+1Полагаю, что для циклического этого недостатка нет, так как нет затрат времени на дополнительные действия по извлечению данных, кроме бинарной операции, по сравнению с неограниченным массивом.
Я правильно понял, что Вы собираетесь извлекать данные из буфера поэлементно?!
Нет, это конечно бывает нужно при решении некоторых специальных задач. Только вот в условиях об этом не сказано. По моим представлениям, гораздо более типичное применение циклического буфера - это блочная обработка. Для эффективной реализации которой нужно именно последовательное размещение в памяти. Причем как на верхнем уровне (при вызове процедур), так и на самом нижнем.
Офтопик
Чтобы немного разрядить обстановку, напомню хохму про автобусный парк, который освоил массивные операции
задолго то того, как они вошли в моду в языках программирования ;-)
Обычная программа подъезжает к остановке, открывает дверь, сажает одного пассажира, закрывает дверь. Далее - цикл, пока не кончатся пассажиры. Про массивные операции, наверно, можно не пояснять ;-)
SpiderEkb
13.07.2024 09:23Не очень понятна мысль.
Кольцевые буфера (уж простите меня за привычную терминологию) применяются там, где нужно работать со скользящим окном из последних N элементов в непрерывном потоке данных.
И если вам так надо именно непрерывное расположение в памяти, то количество одновременно заполняемых массивов у вас должно быть равно размеру окна (и каждый массив будет равен размеру окна). Хорошо, если у вас размер окна определяется однозначным числом. А если трех-, или, не дай бог четырех- или пятизначным?
Тут мало что придется постоянно вычислять номер текущего окна, так еще и для каждого окна вычислять позицию для очередного элемента...
Сложность вычислений растет просто катастрофически...
В кольцевом буфере (если его размер равен размеру окна) нет единственного условия - не сохраняется порядок элементов. Если процедура обработки данных обладает свойством коммутативности (например, усреднение, вычисление медианы и т.п.), то вы точно также можете передавать в свою функцию указатель на кольцевой буфер и быть уверенным, что в нем содержатся те самые последние N элементов, необходимые для обработки.
nikolz Автор
13.07.2024 09:23В данной статье речь идет не об абсолютной сложности решения задачи обработки данных, а об относительной. Я написал конкретно 5 вариантов и сравниваю их относительно друг друга.
-----------------------
Кольцевой буфер (по вашей терминологии) позволяет просто выполнять непрерывную обработку сигналов. Так как в массиве данных всегда ровно N последних значений и они всегда расположены с 0 по N-1 индекс. Т.е. в алгоритме обработке можно вообще исключить текущий номер отсчета. Поэтому нет сложности непрерывной обработки.
---------------------
Но хочу заметить, что в статье я рассматривал задачи , когда обработка выполняется блоками , например, БПФ.
Во многих задачах реального времени можно избежать блочную обработку, что позволяет вообще отказаться от массивов. Но это уже другая история.
saluev
13.07.2024 09:23+2И если вам так надо именно непрерывное расположение в памяти, то количество одновременно заполняемых массивов у вас должно быть равно размеру окна
Почему?.. По-моему, расходы памяти просто в два раза больше и всё.
SpiderEkb
13.07.2024 09:23Ну напишите подробнее как вы предлагаете реализовать обработку, например, 1000 последних отсчетов из некоторого непрерывного потока данных.
Ну вот идут данные, например, с какого-то АЦП. И при поступлении нового отчета вам нужно посчитать... Ну, положим, медиану по последним 999 отсчетам. Т.е. вам нужно помнить последние 999 значений и постоянно пересчитывать медианное для них.
Возможно, я просто не понял вашу мысль.
saluev
13.07.2024 09:23+3Ну. Массив длины 1999. Сначала заполняю первые 1000 индексов. Потом при поступлении очередного значения записываю его в i-ю и (i+1000)-ю позиции. При такой организации процесса у меня всегда есть непрерывный подмассив, содержащий последние 1000 элементов (см. пример для N=3 в моём комментарии выше). С этим непрерывным подмассивом делаю что хочу.
Медиана — не очень практичный пример (для медианы проще держать две кучи), а вот, например, FFT — вполне.
SpiderEkb
13.07.2024 09:23Ок. А что будет когда элементов станет, скажем, 2001 и вам нужно обработать окно с 1002 по 2001?
Речь-то идет о непрерывном бесконечном потоке данных... Там могут быть миллионы и миллиарды элементов (допустим это какой-то датчик, работающий годами в режиме 24/7 с частотой 10Гц), но вас всегда интересуют только последние 999 из них. В каждый момент времени. Т.е. пришел 1 000 000 элемент - вам нужно обработать его и 998 элементов перед ним.
saluev
13.07.2024 09:23+2Когда элементов будет обработано 2001, окно с 1002 по 2001 будет расположено в индексах с 1 по 1000. Давайте покажу. Текущее окно подчёркиваю снизу стрелкой ^.
Сначала заполняем пустой массив:
[_, _, _, ..., _] [1, _, _, ..., _] ^ [1, 2, _, ..., _] ^^^^ ... [1, 2, ..., 1000, _, _, ..., _] ^^^^^^^^^^^^^^^Дальше, поскольку нам нужны только последние 1000 элементов, единичку можно затирать:
[1001, 2, 3, ..., 1000, 1001, _, _, ..., _] ^^^^^^^^^^^^^^^^^^^^^ [1001, 1002, 3, ..., 1000, 1001, 1002, _ ..., _] ^^^^^^^^^^^^^^^^^^^^^^^^К тому времени, как массив заполнится до конца, у нас, помимо актуального окна, смещающегося к концу, появится почти полная копия этого же окна в начале:
[1001, 1002, ..., 1998, 999, 1000, 1001, ..., 1998, _] ^^^^^^^^^^^^^^^^^^^^^^^^^^ [1001, 1002, ..., 1998, 1999, 1000, 1001, ..., 1998, 1999] ^^^^^^^^^^^^^^^^^^^^^^^^^^^Почти полная, потому что элементы с 1001 по 1999 — это 999 элементов, то есть как раз на один меньше, чем нужно. Но следующим шагом мы допишем этот элемент в конец и снова получим полноценное окно длины 1000, начинающееся с первого элемента массива:
[1001, 1002, ..., 1998, 1999, 2000, 1001, 1002, ..., 1998, 1999] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ [1001, 1002, ..., 1998, 1999, 2000, 2001, 1002, ..., 1998, 1999] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^SpiderEkb
13.07.2024 09:23А, спасибо, понял. Да, наверное, так сработает. Массив в два размера окна, а окно для обработки скользит внутри него. Теперь дошло :-)
nikolz Автор
13.07.2024 09:23Индекс элемента в массиве вычисляется через операцию по модулю N. это означает, что для N=1000 при изменении номера элемента данных от 0 до 10000000... индекс элемента в массиве будет циклически изменятся от 0 до N-1.
nikolz Автор
13.07.2024 09:23Попробую объяснить.
Вариант 1: Данные с АЦП пишем в массив, размер которого мы задаем существенно большим , чем ожидаемое число данных, либо его размер мы динамически увеличиваем.
При вычислении медианы мы должны знать текущий размер массива и размер окна(N) и использовать скользящее смещение в массиве дынных. Т е процесс вычисления медианы должен знать текущее состояние массива данных.
--------------------------
Вариант 2: Применение циклического массива.
Данные с АЦП пишем в циклический массив размером окна . Причем в массиве всегда последние N элементов.
Вычисление медианы выполняется по массиву c известной и постоянной размерностью , с 1 по N-ый элемент. Т е. это задача расчета медианы массива постоянного размера. Она вообще никак не зависит от источника данных(АЦП) и текущего размера данных.
Kerman
13.07.2024 09:23+1У вас запись O(1), но дважды.
Можно также брать массив N+M и через каждые M записей сдвигать в ноль. При 2N массиве это будет быстрее, чем дважды писать каждую запись.
saluev
13.07.2024 09:23+2Насчёт быстрее — это надо проверять. Но сдвиги подразумевают, что время обработки не размазано равномерно, а раз в сколько-то итераций "тормозит" — подозреваю, для потоковой обработки это нежелательно.
Kerman
13.07.2024 09:23Проверять конечно надо. Но я думаю, что результат совершенно предсказуем при наличии векторных операций или каком-либо кэше.
Вы абсолютно правы, что ваш алгоритм лучше для минимизации времени каждой выборки. Собственно, я подумал, а можно ли уменьшить максимальное время выборки и думал в сторону размазывания сдвига по операциям записи. Получился тот же алгоритм, что у вас.
Но. Можно сделать ещё лучше. Так сказать объединить алгоритмы. Если у нас известна кратность копирования (например копируется по 128 бит, а юнит у нас инт в 32 бита), то можно писать через 4 записи. Так же дважды, как предлагали.
adeshere
13.07.2024 09:23+4Если бы мне нужно было уметь очень быстро обрабатывать текущий буфер, я бы сделал массив длины
с записью в два места сразу. Пример для N=3:Именно что!
В 90% практических задач вместо оптимизации скорости вычисления индекса нужно оптимизировать скорость обработки данных, хранящихся в массиве. Хотя бы потому, что даже запись значения в массив и чтение из него - это почти всегда гораздо более более тяжелая операция, чем вычисление индекса (которое в большинстве случаев сводится к инкременту регистра). Я уж не говорю о том, что обычно данные пишутся в буфер один раз, а читаются многократно (сравн. с цитатой N2 про программный код ;-) .
Вообще, очень странная статья с каким-то совершенно искусственным набором альтернатив. Для вариантов 1-3 нужно специально изобретать ситуации, когда они могут быть оптимальны. А варианты 4 и 5 и вовсе не взаимозаменяющие, а имеют разные области применения. При этом совершенно разумный (и иногда наиболее оптимальный) вариант от @saluevи вовсе не упомянут!
На мое скромное имхо, там, где реально нужна оптимизация "мукомольного производства" - там зона ответственности языков, умеющих в массивные операции. Так что я дико извиняюсь за свою
возможную профдеформацию
я много лет занимаюсь перемалыванием чисел, и одна из типичных задач - это обработка данных в скользящем окне. При ширине окна в миллионы точек и длине ряда - до нескольких миллиардов. Правда, ряды у нас обычно архивные, т.е. обрабатываются в офлайне. Но скорость все равно требуется максимальная просто в силу объема данных. Поэтому язык программирования - фортран, который специально заточен под
эффективные вычисления
точнее, по моему скромному имхо, во многих других языках вполне можно добиться примерно одинаковой с фортраном производительности перемалывания чисел. Вся разница в том, что на фортране такую программу может написать мидл (как бы не джун), и займет она несколько строчек. А на каком-нибудь Си для того же самого нам потребуется сеньор и пара страниц не самого дилетантского кода
Впрочем, потенциально никто не мешает сделать на фортране библиотеку для работы с циклическим буфером и прицепить ее хоть к Питону.
но как по мне, на таких задачах оптимизация вычисления индексов - это что-то сродни ловле блох на фоне гангрены. Да, без блох будет легче, но я бы сперва все-таки занялся гангреной...
nikolz Автор
13.07.2024 09:23Для N=3 вообще нет смысла что-то городить. Можно просто смещать на два элемента.
Проблема когда у Вас N существенно больше.
--------------
Например, применяю циклические массивы в фильтрах, при обнаружении сигналов в реальном времени в микроконтроллерах.
В организации стеков и очередей.
----------------
В скриптовых языках циклические массивы позволяют практически исключить необходимость обращаться в процессе работы к куче и к сборщику мусора.
dyadyaSerezha
13.07.2024 09:23+3Я тоже не понял, почему автор акцентировал внимание на оптимизации вычисления индекса. По-моему, это вообще последняя головная боль из всех возможных тут. А вот переписать тот же БПФ (и все другие алгоритмы) для "рваного" входного массива, это гораздо более существенно. Поэтому лучший вариант (кольцевой или двойной буфер с двойной записью) сильно зависит от конкретных требований.
nikolz Автор
13.07.2024 09:23Поясняю.
В начале статьи я написал о множестве задач в которых эффективно применение циклических массивов. В последнее время многие не профессиональные разработчики увлекаются написанием торговых роботов и индикаторов рынка на скриптовых языках. При этом важным моментом является быстродействие и нехватка памяти для хранения данных. Циклические массивы позволяют решить эти проблемы. Но реализация их не является очевидной. Это можно увидеть во многих публикациях о них в интернете. Поэтому я и попытался доходчиво объяснить как эффективно организовать циклический массив. Вопросы о применении этих массивов в различных задачах не входят в данную статью.
dyadyaSerezha
13.07.2024 09:23+1Оптимизировать вычисления индекса в скриптовом языке? Вы серьёзно? Сама скриптовость замедляет всё раз в сто, а вы учите, что логическое "и" быстрее остатка от деления? (что спорно для многих CPU, думаю). Мда уж....
Да и кроме того, там даже логического "и" можно не делать, а просто вести свой индекс в другой переменной.
nikolz Автор
13.07.2024 09:23Вы ошибаетесь. Вот результаты тестов (SciLua - это LuaJit со встроенной библиотекой BLAS и др.):
rukhi7
13.07.2024 09:23В последнее время многие не профессиональные разработчики увлекаются написанием торговых роботов и индикаторов рынка на скриптовых языках. При этом важным моментом является быстродействие и нехватка памяти для хранения данных.
Интересно это сколько же данных у такого робота в обработке что у него появляется проблема нехватки памяти? Даже если там сохраняется массив курсов валют, например, за всю историю данные будут измеряться- не будут превышать единиц мегабайт. В связи с этим я подозреваю что проблемы организации буфферов не так актуальны как то что разработчики просто не являются профессиональными. Вряд ли какие-то абстрактные рассуждения на тему некоторых аспектов программирования могут помочь НЕ профессиональным разработчикам профессионально работать в области в которую они случайно попали.
nikolz Автор
13.07.2024 09:23Относительно недавно биржа перешла на 64-битный формат номера сделки, так как 32-бита стало не хватать.
Ну вот и посчитайте сколько надо памяти, чтобы все это сохранить и обработать.
Подробнее об объемах торгов можно посмотреть на сайте биржи.
rukhi7
13.07.2024 09:23Подробнее об объемах торгов можно посмотреть на сайте биржи.
на сайте какой биржи? А вам трудно написать примерное среднее число сделок в день на этой бирже? Неужели больше 10 тысяч?
64-битный формат номера сделки, так как 32-бита стало не хватать
это не очем не говорит с профессиональной точки зрения, потому что может вы там текстовые поля добавили.
nikolz Автор
13.07.2024 09:23По своему опыту торговли могу сказать следующее:
Объем таблицы обезличенных сделок к концу дня только по акциям (без облигаций, валюты и опционов) составляет несколько сотен миллионов байт. Число опционов примерно 8 тысяч. Но есть еще заявки и стоп-заявки, которых на одну сделку приходится раз в десять больше, примерно составит полагаю десятки миллионов в день. Простому смертному торговать всеми инструментами практически не получится, комп просто не успеет все обработать в реальном масштабе.
Вот тут есть объемы в рублях. https://www.moex.com/n70851.
-----------------------
Ежедневное количество сделок корпоративных облигаций на Московской бирже (основной, Т+, РПС) и СПВБ - Россия 2 302 409 за 30.06.2024 Предыдущее значение 2 510 894 на 31.05.2024
----------------------------------
Ежедневное количество сделок ОФЗ на Московской бирже (Т+ и РПС) - Россия 49 984 Предыдущее значение 55 585 на 11.07.2024
---------------------------------
Московская биржа, акция Сбербанк об. 12.07.2024
Средневзвешенная цена дня:293,3900
ОБЪЕМЫ ТОРГОВ ЗА ДЕНЬ
Количество сделок, шт.:123 842
Объем в единицах ценных бумаг:49 999 170
Объем в денежных единицах:14 669 454 270,00 RUB
rukhi7
13.07.2024 09:23Вот это действительно интересная справка.
торговать всеми инструментами практически не получится, комп просто не успеет все обработать в реальном масштабе.
я подозреваю что торговать всеми инструментами с одного компа просто не нужно, надо сделать так чтобы торговый робот на заданное количество связанных инструментов легко добавлялся на текущий компьютер, при этом должна считаться-работать оценка производительности на этом компьютере которая будет зависеть от количества заведенных роботов, ну а завести робота на отдельном компе вообще не должно быть проблемой, хотя придется считать оценку производительности линии связи (сети) для обращения к базе данных сделок. Вот такую задачу(задачи) надо формулировать и решать, а то что в статье поощряет и размножает НЕ профессионализм в этом направлении, мне так кажется.
randomsimplenumber
13.07.2024 09:23переписать тот же БПФ
Переписать то несложно, все обращения к массиву по индексу переписать на вычисление индекса по модулю. Но у FFT сложность O(N log N), очень легко можно получить уменьшение производительности, несмотря на уход от O(N) при записи..
Так что да, запись в буфер и чтение из буфера нужно рассматривать в комплексе.
dyadyaSerezha
13.07.2024 09:23Кстати, в зависимости от требований, перед вызовом БПФ или похожего можно переписывать кольцевой буфер в нормальный массив, и опционально, использовать два кольцеавх буфера, если вызов алгоритма может вызвать пропуск добавления очередного значения в буфер или race condition. В общем, вариантов решений вагон, в зависимости от требований, опять же.
randomsimplenumber
Если коротко, то О(1) как правило лучше чем О(N).