Во многих задачах, связанных с обработкой данных, возникает проблема нехватки памяти для хранения их.
Например, с датчика непрерывно поступают данные с частотой дискретизации F=1000 Гц, которые сохраняются в массиве. Однако, для анализа данных используется конечное временное окно наблюдения, например, T=10 секунд. Таким образом, при поступлении нового отсчета данных необходимы лишь последние N=T*F=10000 значений.
Подобные задачи возникают при фильтрации сигналов датчиков, построении индикаторов для торговли на биржах, в нейронных сетях.
Возможно несколько вариантов накопления данных для обработки в реальном масштабе времени:
Массив неограниченного объема. Недостаток: Избыточные затраты памяти.
Два массива по N элементов. При заполнении одного переключаемся на другой. Недостаток: сложность непрерывной обработки данных. Избыточные затраты памяти.
Массив N элементов. При заполнении очищаем. Недостаток: невозможность непрерывной обработки.
Массив N элементов. Сдвиг на элемент влево и запись нового элемента вместо N-го. Недостаток: Относительно большие затраты времени на сдвиг массива.
Массив 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