Initialize a dynamic array in O(1) time in C/C++

Question

Is there any way to initialize a whole dynamic array in O(1) time? Is there something similar to bool a[10] = {false} in the case of a static array?

Answer 1

For a dynamic array, each element you want to set must be individually considered by the CPU, so the time complexity is O(N).

Or is it?

But that's not really how big-oh works. It is also not really how CPUs work.

Big-oh notation concerns itself with the asymptotic behavior of a system as the number of elements grows towards infinity. Which is to say: we should take it with a grain of salt when we apply it to small numbers of elements!

CPUs also behave differently for small versus large numbers of elements because they have different cache levels which imply different access latencies. And you see this all the time in designing high-performance algorithms. See, for instance, this page describing how to optimize matrix multiplication: the section on "Blocking to maintain performance" is all about rearranging computations so they stay in the CPU's cache.

Now, let's talk about your question more specifically.

Consider below the handy chart of Latency Numbers Every Computer Scientist Should Know (source).

The salient point here is that a (random) main memory reference costs about 100ns, whereas references to the L1 cache cost 0.5ns and to the L2 cache cost 7ns. Due to caching effects, reading sequentially from RAM gives a significant speed boost.

This means that, all else being equal, you can read 200 numbers from L1, or 14 numbers from L2, in the time it takes to read a single number from RAM.

And this gets us into cost models.

Consider initializing two dynamic arrays like so:

std::vector<int> a(20,1);
std::vector<int> a(21,1);

From the foregoing, we expect that the additional element takes ~0.5ns to deal with (since the whole array fits into the cache) whereas storing the array to memory takes 100ns. That is, the marginal cost of adding an additional element is negligible. In fact, the marginal cost of adding even many elements would be negligible (how many depends on the processor).

Let's apply these ideas. Consider these two statements.

int m = array1[20];
std::vector<int> a(900,1);

If you're thinking about this from a O(1) vs. O(N) perspective you might think something silly, like "the second statement will take 900x longer than the first". A more sophisticated thought you might have is that "the hidden coefficients of the O(N) second statement may be small, so it is difficult to know which will be faster".

With some knowledge of caching you might instead say to yourself "for these small N values an asymptotic analysis is not appropriate". You might further think "these statements may take the same time" or "the second statement may run faster than the first due to caching effects".

An Experiment

We can use a simple experiment to demonstrate this.

The following program initializes arrays of different lengths:

#include <vector>
#include <iostream>
#include <chrono>
#include <string>

int main(int argc, char **argv){
  const int len = std::stoi(std::string(argv[1]));
  auto begin = std::chrono::high_resolution_clock::now();
  for(int i=0;i<10000;i++){
    std::vector<int> a(len,1);
    (void)a;
  }
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count() << std::endl; //Nanoseconds
}

The program runs many initializations of the dynamic array to average over fluctuations due to other programs running on the machine.

We run this program many times:

for n in {1..100}; do ./a.out 1; done | awk '{print "1 "$1}' | xclip

To deal with differences in the program's start-up and the machine's memory-state due to other programs running.

On my Intel(R) Core(TM) i5 CPU M480 @ 2.67GHz with a 32K L1 cache, 256K L2 cache, and 3072K L3 cache, the result is this:

Note that the increase in time for small arrays is sublinear (when combined with the later behavior on larger arrays) through about 1000 elements. This is not O(N) behavior. After this, adding 10x more elements leads to about 10x more time consumed. This is O(N) behavior.

Trying the same test on my Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50GHz with a 32K L1 cache, 256K L2 cache, and 30720K L3 cache yielded very similar results:

Bottom Line

Array initialization is in O(N) since it grows with the number of elements. However, in practice, due to caching, the cost does not rise linearly. Therefore, an "O(1)" command may take the same time as an "O(N)" command, depending on the magnitude of N.

Answer 2

No, there is not, not in c++, nor in c, not in any language or CPU I know of. But it can be done with 1 line of code.

in C: for a array of char:

char a[N];
memset(a, '1', N);  // only works for data 1 byte long

in C++

std::vector<T> v;
std::fill(v.begin(), v.end(), value);

Answer 3

There is no way to initialize an array in less than O(n) time, by the very definition of big-O. CPU needs to fill the array of n elements with n zeros.

When you declare an array bool a[10] = {false} in a static or global context, CPU still spends O(n) time filling it with zeros, but it happens at the time the program is loaded. Similarly, declaring this array in the automatic context (local array variable) results in CPU cycles being spent upon entering the function where the array is declared.

Finally, you can value-initialize a dynamically allocated array using this syntax:

int *array = new int[ARRAY_SIZE](); // Note the parentheses

Again, this is done in O(n) time upon allocation.

Answer 4

define: tells the compiler there is an array type char and size 100 but not created yet Compiler takes note but not reserving memory space char a[100];

initialize: tells the ompiler there is an array and reserves space of 100 bytes for the array char b[100] = {}; or char b[100] = {0}; the value of each element is undefined, not initialized but available for use.

If you want to set the array to starting value you need to write it manually char c[100] = {}; for(;i < 100; i++){ c[i] = 0; }

So creating the array and reserving space is 1(0); Setting a value takes longer

Answer 5

You can actually do it in O(1) time

I'll explain the simpler solution, while you should read about the better one here,
and see my cpp implementation of the latter.

The next (simpler) algorithm can also be found here.

You want to initialize an array A of size n. You'll need to allocate two more arrays - from and to (array of unsigned ints, of size n), and use two more variables - one to save the "default value", let's call it def, and another one called b.

initialization (or the fill operation) is just setting b=0, and changing def if needed.

The cell i is considered initialized if from[i] (lets call it j) makes that to[j]<b and to[j] == i.
This is called a chain (from[i] == j and to[j] == i, while j<b).

Read by checking if the cell is chained, if so return A[i], else return the default def.

Write by first checking if the cell is chained. if it isn't - chain it:

from[i] = b;
to[b] = i;
b++;

Then just write to A[i].

Why does it work?

After fill all cells are uninitialized, and that's because b=0 (from[i]>=b so i cant be chained).

An uninitialized cell can't accidently form a chain because the to[j] (for j < b) should equal i, but the C[j]'s are already chained to the already initialized cells.

Implementation of that can be found in the link above.
This solution has a big flaw - the 2n extra memory words.
It's a major flaw since we only use this algorithm on big arrays (as small ones might be faster initialized by memset/for-loop).

There is an improved solution that does the same O(1) fill/read/write with only O(1) extra space (explained in the article above), and can also be improved to using only 1 extra bit (as my implementation does).