Sparse array

Sparse array

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).

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).

As an example, a spreadsheet containing 100x100 mostly empty cells might be more efficiently stored as a linked list rather than an array containing ten thousand array elements.

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.

See also

* Sparse matrix

External links

* [http://boost.org/libs/numeric/ublas/doc/vector_sparse.htm Boost sparse vector class]

* [http://portal.acm.org/citation.cfm?id=1363086&jmp=cit&coll=GUIDE&dl=GUIDE| Rodolphe Buda, "Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm", "Computational Economics", 31(4), May, pp.397--408, 2008.]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • sparse array — retas masyvas statusas T sritis informatika apibrėžtis Duomenų ↑masyvas, kurio dauguma elementų yra nuliai arba nuliui ekvivalenčios reikšmės. atitikmenys: angl. sparse array ryšiai: dar žiūrėk – masyvas dar žiūrėk – retas …   Enciklopedinis kompiuterijos žodynas

  • Sparse matrix — A sparse matrix obtained when solving a finite element problem in two dimensions. The non zero elements are shown in black. In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros (Stoer Bulirsch 2002,… …   Wikipedia

  • Array — In computer science an array [Paul E. Black, array , in Dictionary of Algorithms and Data Structures , Paul E. Black, ed., U.S. National Institute of Standards and Technology. 26 August 2008 (accessed 10 September 2008).… …   Wikipedia

  • Array data type — Not to be confused with Array data structure. In computer science, an array type is a data type that is meant to describe a collection of elements (values or variables), each selected by one or more indices that can be computed at run time by the …   Wikipedia

  • Dynamic array — Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for expansion. Most insertions are fast (constant time), while some are slow due to the need for reallocation (Θ(n) time,… …   Wikipedia

  • Associative array — In computer science, an associative array (also called a map or a dictionary) is an abstract data type composed of a collection of (key,value) pairs, such that each possible key appears at most once in the collection. Operations associated with… …   Wikipedia

  • Thinned array curse — The thinned array curse (sometimes, sparse array curse ) is a theorem in electromagnetic theory of transmitters. It states that a transmitting aperture which is synthesized by a coherent phased array of smaller apertures that are spaced apart… …   Wikipedia

  • Bit array — A bit array (or bitmap, in some cases) is an array data structure which compactly stores individual bits (boolean values). It implements a simple set data structure storing a subset of {1,2,..., n } and is effective at exploiting bit level… …   Wikipedia

  • Judy array — In computer science and software engineering, a Judy array is a complex but very fast associative array data structure for storing and looking up values using integer or string keys. Unlike arrays, Judy arrays may be sparse; that is, they may… …   Wikipedia

  • Global array — Global Arrays, or GA, is the library developed by scientists at Pacific Northwest National Laboratory for parallel computing. GA provides a friendly API for shared memory programming on distributed memory computers for multidimensional arrays.… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”