Циклические массивы
Во многих задачах, связанных с обработкой данных, возникает проблема нехватки памяти для хранения их.
Например, с датчика непрерывно поступают данные с частотой дискретизации 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
