Циклические массивы

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

Например, с датчика непрерывно поступают данные с частотой дискретизации 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