How to reset an array in O(1)?

There is one cheater method of zeroing out. It is widely used at the Olympics. Sample code (pseudo-style, purely for the sake of principle). For example, the array cannot be expanded (this is not so important).

class MyArray<T>{
     private Array<T> value;
     private Array<int> mask;
     private int current;

     public MyArray(int size){
         value = new Array<T>(size);
         mask  = new Array<int>(size);  //we hope new array fill 0. If not - fill
         current = 0;
     }  

     public  T get(int pos){
          //ToDO validate pos
          if (mask[pos] != current) 
             return null;  //or any default value for clean. 
                           //So you can "clean" different value
          return value[pos];
     }

     public void set(int pos, T val){
         //ToDO validate pos
         mask[pos] = current;
         value[pos] = val;
     }

     public void cleanAll(){
          current++;
     }

}

I think the idea needs no further explanation.

It is easy to see that the access time is still O (1). In this case, "reset" - 1 operation.

The time will always be O (n). But you can reset the array using multiple threads. In Java 8, there is a method

Arrays.parallelSetAll()

It is possible to reset O(1) in the time to a discharged array , which is usually implemented either through a hash table or through a balanced tree.

Details

To begin with, let's try to abstract from the implementation of the array, and talk about its interface. The array stores elements of the same type that are accessible by integer indexes. We can find out the length of the array length, and the indexes can take values from 0 to length - 1.

Usually the implementation of an array is simple: we allocate memory in a row, enough to store length elements of a given type. If double requires 8 bytes, then an array of 1000 double-precision numbers will require 8000 bytes in a row, and the i th element will be located at an offset of 8 * i bytes from the beginning.

Let's imagine that our array is quite large, for example, it contains a billion elements. 80% of these elements have the value 0. Such an array is called is empty, because there are few significant elements in it, and there are many empty ones.

For such arrays, it is a pity to allocate the entire memory, because for the most part it will store the default value. We could store indexes and values of significant elements:

103 => 145000.3
457 => 267000.5
732 => 197500.2

Here 103, 457 and 732 are the indexes of the significant elements of the array, all other elements are equal to 0.0. If it is an array of 1000 elements, the memory savings are obvious.

The array interface must be implemented as follows: the length of the array length is set initially, and the list of pairs индекс => значение is empty. The read operation on the specified index should check whether this index is in the list. If there is an index, the operation returns the associated value, and if there is no index, it returns zero.

The write operation looks at the value. If this value is zero, the pair with the specified index should be removed from the list, and if it is non - zero, it should be added.

It remains to solve the question of the effectiveness of searching for a pair with the specified index. If you store pairs in any order, the speed of working with such an array will be depressingly low - O (M) for reading/writing an element instead of O(1) . Here M is the number of significant elements in the array.

The pairs can be organized into a binary tree, then the speed increases to O(log N). You can also use a hash table, then the speed will approach the usual array O(1).

A hash table is essentially an internal array with the classic implementation. It contains pairs of indexes and values, and its size must be one and a half to two times larger than the number of significant elements to work effectively.

Specifically: we want to store a billion double-precision numbers, which would take up 8 gigabytes of RAM. There are only 5% or fifty million significant numbers in this array. To work effectively with so many pairs, we need space to store a hundred million pairs. Each pair consists of an integer index (4 bytes) and double-precision values (8 bytes). The total size of the hash table will be 1.2 gigabytes, which is almost 7 times less than 8 gigabytes. In this case, reading and writing an element with an arbitrary index i will be O(1) , as in a classic array.

Back to the main question: how to clear such an array in time O (1) ? To do this, we need to clear the internal hash table. This is a continuous array, the space for which we have allocated in the heap. To clear it, it is enough return this memory to the heap, which can be considered a fixed-time operation.

I'll digress here. In general, the time may not be fixed, but it is a topic for deep discussion. In modern environments where garbage collection works, we can talk about the release time within O (1) .

Store the bit mask of non-zero elements. For her to store another mask and so on. Here only access (check for not 0) will become in O (log?(N)).