Разреженный массив — Википедия

Разрежённый масси́в — абстрактное представление обычного массива, в котором данные представлены не непрерывно, а фрагментарно; большинство его элементов принимает одно и то же значение (значение по умолчанию, обычно 0 или null). Причём хранение большого числа нулей в массиве неэффективно как для хранения, так и для обработки массива.

В разрежённом массиве возможен доступ к неопределенным элементам. В этом случае массив вернет некоторое значение по умолчанию.

Простейшая реализация этого массива выделяет место под весь массив, но когда значений, отличных от значений по умолчанию, мало, такая реализация неэффективна. К этому массиву не применяются функции для работы с обычными массивами в тех случаях, когда о разрежённости известно заранее (например, при блочном хранении данных).

Способы представления

В виде ассоциативного массива

Разрежённый массив обычно представляется как ассоциативный массив:

Sparse_Array[{pos1 -> val1, pos2 -> val2,…}] или

Sparse_Array[{pos1, pos2,…} -> {val1, val2,…}],

где каждой позиции pos_i соответствует значение val_i. Данный способ используется для экономии памяти (и ключ, и значение несут информацию).

В виде связного списка

Связный список здесь используется вместо обычного массива потому что обычный массив требует места для хранения неопределенных значений. Например, при объявлении:

double arr[1000][1000];

будет выделено сразу 8 Мб памяти (8 байт на одно значение × 1 000 000 значений), что является неоправданной тратой памяти. В случае же связного списка пустые значения не хранятся, и место под новые значения выделяется автоматически при добавлении или удалении элементов (в этом случае можно говорить о динамическом выделении памяти).

См. также

Ссылки

Boost sparse vector class
Buda R. Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm (англ.) // Computational Economics. — 2008. — Vol. 31, iss. 4 (May). — P. 397—408.