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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Разряжённый масси́в — абстрактное представление обычного массива, в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимают одно и то же значение (значение по умолчанию, обычно 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 значений), что является пустой тратой памяти. В случае же связанного списка пустые значения не хранятся, и место под новые значения выделяется автоматически при добавлении или удалении элементов (в этом случае можно говорить о динамическом выделении памяти).

См. также[править | править исходный текст]

Источники[править | править исходный текст]