View on GitHub


Initialize and fill an array in O(1) time and space.

Time and Space Analysis

Timings Results and Statistics

The timings folder contains code for timing the project’s classes.
The implemented arrays are faster than a normal array, when calling fill(v) at least ~0.05% of the times.
See the last full results of Farray1, Farray, and NFarray.

Space Analysis

The Farray1Direct functions only need the uses 1 extra bit - the functions request a boolean flag beside the array and its size.

The Farray1 class is simpler to use but holds a pointer to the array, its (constant) size, the flag, and a constant boolean indicating if the array was allocated by the Farray constructor. So it’s debatable if it is pure 1 extra bit, or a bit more (pun intended).

The Farray takes an extra word and the default value saved separately, but it is a bit faster than Farray1 because the block size is smaller.

The NFarray takes a few extra words of memory than Farray but allows you to sum all of the values in the array in O(1) time, and to add/multiply all values simultaneously in O(1).

Time Analysis

As you know - every operation in this project is O(1) time and consumes O(1) extra space (1 bit, or a bunch of memory words).

In this part we will show the number of read/write accesses in every operation:
*More information can be found in the code itself.
*If r(read) or w(write) not specified - it’s zero.
*HB stands for accessing of the size of a Half Block.
*The numbers were directly calculated from the implementation. For more details read the paper, and then view the code.

Farray1 / Direct Functions

Half Block size is (sizeof(ptr_size)*2+sizeof(T)-1) / sizeof(T) + 1, while ptr_size is by-default size_t.

// w <= 2HB+1

// r <= 5

// already_written: r <=  6, w <=     2    (or if another index in the same block was written)
//     first_write: r <= 13, w <= 5HB+7
write(i, v);

// r == 1

// r == 1
// r == 3