Weighted round robin
In computer science, a sparse array is an array in which most of the elements have the same value (known as the default value—usually 0 or null). The occurrence of zero elements in a large array is inefficient for both computation and storage. An array in which there is a large number of zero elements is referred to as being sparse.
In the case of sparse arrays, one can ask for a value from an "empty" array position. If one does this, then for an array of numbers, a value of zero should be returned, and for an array of objects, a value of null should be returned.
A naive implementation of an array may allocate space for the entire array, but in the case where there are few non-default values, this implementation is inefficient. Typically the algorithm used instead of an ordinary array is determined by other known features (or statistical features) of the array. For instance, if the sparsity is known in advance or if the elements are arranged according to some function (e.g., the elements occur in blocks).
A heap memory allocator in a program might choose to store regions of blank space in a linked list rather than storing all of the allocated regions in, say a bit array.
Representation
Sparse Array can be represented as
Sparse_Array[{pos1 -> val1, pos2 -> val2,...}] or
Sparse_Array[{pos1, pos2,...} -> {val1, val2,...}]
which yields a sparse array in which values appear at positions .
Sparse Array as Linked List
An obvious question that might be asked is why we need a linked list to represent a sparse array if we can represent it easily using a normal array. The answer to this question lies in the fact that while representing a sparse array as a normal array, a lot of space is allocated for zero or null elements. For example, consider the following array declaration:
- double arr[1000][1000];
When we define this array, enough space for 1,000,000 doubles is allocated. As each double requires 8 bytes of memory, this array will require 8 million bytes of memory. Because this is a sparse array, most of its elements will have a value of zero (or null). Hence, defining this array will soak up all this space which will result in wastage of memory. An effective way to overcome this problem is to represent the array using a linked list which requires less memory as only elements having non-zero value are stored. Also, when a linked list is used, the array elements can be accessed through fewer iterations than in a normal array.
A sparse array as a linked list contains nodes linked to each other. In a one-dimensional sparse array, each node consists of an "index" (position) of the non-zero element and the "value" at that position and a node pointer "next" (for linking to the next node), nodes are linked in order as per the index. In the case of a two-dimensional sparse array, each node contains a row index, a column index (which together give its position), a value at that position and a pointer to the next node.