Разреженный массив: различия между версиями
Patarakin (обсуждение | вклад) м (1 версия импортирована) |
Patarakin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
'''Разре́женный масси́в''' — абстрактное представление обычного [[Массив (программирование)|массива]], в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимает одно и то же значение (значение по умолчанию, обычно 0 или null). Причём хранение большого числа нулей в массиве неэффективно как для хранения, так и для обработки массива. | '''Разре́женный масси́в''' — абстрактное представление обычного [[Массив (программирование)|массива]], в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимает одно и то же значение (значение по умолчанию, обычно 0 или null). Причём хранение большого числа нулей в массиве неэффективно как для хранения, так и для обработки массива. | ||
| Строка 27: | Строка 26: | ||
* [[Разреженный файл]] | * [[Разреженный файл]] | ||
[[Категория:Структуры данных]] | [[Категория:Структуры данных]] | ||
Текущая версия на 12:41, 19 октября 2022
Разре́женный масси́в — абстрактное представление обычного массива, в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимает одно и то же значение (значение по умолчанию, обычно 0 или null). Причём хранение большого числа нулей в массиве неэффективно как для хранения, так и для обработки массива.
В разреженном массиве возможен доступ к неопределенным элементам. В этом случае массив вернет некоторое значение по умолчанию.
Простейшая реализация этого массива выделяет место под весь массив, но когда значений, отличных от значений по умолчанию, мало, такая реализация неэффективна. К этому массиву не применяются функции для работы с обычными массивами в тех случаях, когда о разреженности известно заранее (например, при блочном хранении данных).
Способы представления
В виде ассоциативного массива
Разреженный массив обычно представляется как ассоциативный массив:
Sparse_Array[{pos1 -> val1, pos2 -> val2,…}]илиSparse_Array[{pos1, pos2,…} -> {val1, val2,…}],
где каждой позиции posi соответствует значение vali. Данный способ используется для экономии памяти (и ключ, и значение несут информацию).
В виде связного списка
Связный список здесь используется вместо обычного массива потому что, во-первых, обычный массив требует место для хранения неопределенных значений. Например, при объявлении:
double arr[1000][1000];
будет выделено сразу 8 Мб памяти (8 байт на одно значение × 1 000 000 значений), что является неоправданной тратой памяти. В случае же связного списка пустые значения не хранятся, и место под новые значения выделяется автоматически при добавлении или удалении элементов (в этом случае можно говорить о динамическом выделении памяти).
