Initializing an array in Java in O(1) time-CodePudding

Is it possible to initialize an array in java in O(1) time. In C\C it is possible because the language doesn't automatically initialize the array to 0. In Java, as far as I know, there's no way to skip the automatic initializing step. To clarify, what I mean is using a specialized data structure that has all array functionality with the addition of the capability of initializing all array elements to a certain value (like zero) in constant time (in O(1) complexity). This is usually done using 3 uninitialized arrays and a counter. For More info about this method https://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time

CodePudding user response：

In Java you cannot allocate an uninitialized array.

You can allocate uninitialized memory with the Unsafe.allocateMemory method, which will return a pointer, but this is a private API that may become unavailable at any time and it is already partially unavailable JEP 403.

CodePudding user response：

T[] arr = new T[n]; will initialize the array with the defaults: null (Object, false (boolean), 0 (int) and so on.

You could do T[] arr = {a, b, c}; or T[] arr = new T[]{a, b, c};. Which might have been implemented better - but is not.

Now consider:

int[] arr = new int[100_000];
Arrays.fill(arr, 13);

The jave byte code instruction for a new array anewarray will normally zero the many elements, despite being overwritten by Arrays.fill. Though a JIT or AOT compiler might optimize the combined code in real machine instructions.

The speed loss is relative, as the execution is still fast, and normally array elements should be processed further on.

For sparse arrays there are other data structures, like Map<Integer, Integer>. Boolean arrays can use the more compact and faster BitSet.

In C an array allocation does not necessarily zero the elements: the data may be unitialized or - even worse - reclaimed memory. For that reason java initializes arrays: better code quality.

There are some unsafe memory features in java, but it would be senseless to use them. However you can use non-java-heap memory in the newest java version. With calculations in java, that would even be more slow normally. So better use C in very critical cases.

CodePudding user response：

In Java, C, and C , you could create a data structure that gives the functionality of an array, without allocating memory for an element until it is actually needed. This is sometimes done for very large arrays in which most of the elements will not be used. A sparse array and sparse matrix are examples. It reduces the initialization time at the cost of increasing the time needed to access elements. I'll consider a sparse array for the rest of this post.

Suppose a SparseNode has int index, double value, and possibly other instance variables. The index indicates where it would be if it were in a normal array. The SparseArray class might include these methods: public void setValue (int index, double value) and public double getValue (int index). I'll ignore the possibility of throwing exceptions.

If the SparseArray is backed by a LinkedList, use of either of those methods could involve a sequential search of the elements until an element with matching index is found or it is determined the element is not in the array.

If the element is not found, the getValue method would return the default value, which would be zero for most sparse array applications. The set method would add the element to the list.

In a linked list, you could specify a location of a new element in order to keep them in order. If an array element is not in the list, the search would terminate earlier, although the search would still be O(n) time complexity.

There are ways to improve performance over using a sequential search for every call to getValue or setValue. If the elements are kept in order, there is the possibility of using a binary search. Another possibility is the use of a search tree, or as another answer suggested, a structure using hash functions.