Cyclic arrays
In many tasks related to data processing, the problem of lack of memory for storing them arises.
For example, data with a sampling frequency of F=1000 Hz are continuously received from the sensor and stored in the array. However, a finite observation time window is used for data analysis, for example, T=10 seconds. Thus, when a new data sample is received, only the last N=T*F=10000 values are needed.
Similar tasks arise when filtering sensor signals, constructing indicators for trading on exchanges, and in neural networks.
There are several options for accumulating data for real-time processing:
1: Array of unlimited size. Disadvantage: Excessive memory consumption.
2: Two arrays of N elements. When one is full, we switch to the other. Disadvantage: complexity of continuous data processing. Excessive memory costs.
3: Array of N elements. When full, clear. Disadvantage: cannot be processed continuously.
4: Array of N elements. Shift one element to the left and write the new element instead of the Nth. Disadvantage: Relatively large time costs for shifting the array.
5: Array of N elements is cyclic. This method is the most effective of those listed. To implement it, the number of the next data element must be converted into the index of the array element modulo N.
The method of such transformation depends on the programming language. Let's consider this with examples.
For example: We use a programming language with the ability to explicitly specify the variable type. If N=256, we use the unsigned char type to store the index; N=65536 – we use the unsigned short type, N=4294967296 – we use the unsigned long type.
For other values of N, to quickly convert the count number into the index of an element in the array, it is effective to choose N as a power of two, i.e. from the series 8,16,32,64,128,256,512,1024,2048,4096…65536.
Then the index “I” by the element number “j” can be calculated using & – binary “AND” in the form: i=j&(N-1).
If the programming language does not have binary operations, then the index can be calculated using integer division i=j%N.
Integer division takes longer to execute than binary AND.
In any case, using a cyclic array significantly reduces time and memory costs when processing large amounts of data in real time.
In addition, cyclic arrays are convenient to use for organizing stacks and queues.
The fact that the array index value cannot exceed the array size completely eliminates errors due to going beyond the array location area.
Lua test version:
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
start=os.clock() for i = 1, size do shift
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)test result for N=1024:
1.Unlimited volume (µs): 0.02
4. Shift left (µs): 13.07
5.Cycle, binary 'I'(µs): 0.01
5.Cycle, integer division (µs): 0.02
