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.
Farray1Direct functions only need the uses 1 extra bit - the functions request a boolean flag beside the array and its size.
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).
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.
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).
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
// w <= 2HB+1 fill(v); // r <= 5 read(i); // 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 writtenSize(); // r == 1 iterator::operator++(); // r == 3 iterator::operator*();