WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

См. также

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии