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

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

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

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

Ссылки[править | править вики-текст]