Разреженный массив

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Разрежённый массив»)
Перейти к навигации Перейти к поиску

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

В разреженном массиве возможен доступ к неопределенным элементам. В этом случае массив вернет ноль (если это массив чисел) или null (массив объектов).

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

Способы представления[править | править код]

В виде ассоциативного массива[править | править код]

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

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

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

В виде связного списка[править | править код]

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

double arr[1000][1000];

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

См. также[править | править код]

Ссылки[править | править код]