Разрежённый масси́в — абстрактное представление обычного массива, в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимают одно и то же значение (значение по умолчанию, обычно 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 значений), что является пустой тратой памяти. В случае же связного списка пустые значения не хранятся, и место под новые значения выделяется автоматически при добавлении или удалении элементов (в этом случае можно говорить о динамическом выделении памяти).
См. также
Ссылки
- Boost sparse vector class
- Rodolphe Buda, «Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm», Computational Economics, 31(4), May, pp.397-408, 2008.
 |
Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её. |
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .