Sparse array
Encyclopedia
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 inconvenient for both computation and storage. An array in which there is large number of zero elements is referred to as being sparse.
In case of sparse arrays, we can ask for a value from an "empty" array position. If we do this, then for array of numbers, it should return zero and for array of objects,
it should return null.
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. occur in blocks).
A heap memory allocator
inside a program might choose to store regions of blank space inside a linked list rather than storing all of the allocated regions in, say a bit array.
Sparse_Array[{pos1 -> val1, pos2 -> val2,...}] or
Sparse_Array[{pos1, pos2,...} -> {val1, val2,...}]
which yields a sparse array in which values
appear at positions 
.
When we define this array an enough space of 1,000,000 doubles is allocated. As each double requires 8 bytes of memory, this array will require 8 million bytes of memory. Now this being a sparse array, most of its elements will have a zero(or null) value. 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 linked list which requires less memory as elements having non-zero value only are stored. Also, the array elements can be accessed through less number of iterations than normal array when linked lists are used.
A sparse array as linked list contains nodes linked to each other. In one-dimensional sparse array each node consist 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 case of two-dimensional sparse array each node contains row index, column index(together gives us position), value at that position and a node pointer next.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, 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 inconvenient for both computation and storage. An array in which there is large number of zero elements is referred to as being sparse.
In case of sparse arrays, we can ask for a value from an "empty" array position. If we do this, then for array of numbers, it should return zero and for array of objects,
it should return null.
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. occur in blocks).
A heap memory allocator
Malloc
C dynamic memory allocation refers to performing dynamic memory allocation in the C via a group of functions in the C standard library, namely malloc, realloc, calloc and free....
inside a program might choose to store regions of blank space inside a linked list rather than storing all of the allocated regions in, say a bit array.
Representation
Sparse Array can be represented asSparse_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 might be asked that why we need linked list to represent sparse array if we can represent it using normal array easily. The answer to this question lies in the fact that while representing sparse array as normal array, a lot of space is allocated for zero or null elements. For example, consider following array declaration:- double arr[1000][1000];
When we define this array an enough space of 1,000,000 doubles is allocated. As each double requires 8 bytes of memory, this array will require 8 million bytes of memory. Now this being a sparse array, most of its elements will have a zero(or null) value. 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 linked list which requires less memory as elements having non-zero value only are stored. Also, the array elements can be accessed through less number of iterations than normal array when linked lists are used.
A sparse array as linked list contains nodes linked to each other. In one-dimensional sparse array each node consist 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 case of two-dimensional sparse array each node contains row index, column index(together gives us position), value at that position and a node pointer next.