In a sparse array, most elements are zero or empty.
A two-dimensional array of dimension n takes O(n2) storage; that gets expensive fast as n increases. However, a sparse array might have only O(n) nonzero elements.
What we would like to do is to store only the nonzero elements in a lookup structure; if we look up an element and don't find it, we can return zero.
For example, we could have an array of size n for the first index; this could contain pointers to a linked list or tree of values using the second index as the search key.
(defun sparse-aref (arr i j) (or (second (assoc j (aref arr i))) 0))
(setq myarr (make-array '(10) :initial-contents '(nil nil ((3 77) (2 13)) nil ((5 23)) nil nil ((2 47) (6 52)) nil nil))) >(sparse-aref myarr 7 6) 52 >(sparse-aref myarr 7 4) 0
Contents Page-10 Prev Next Page+10 Index