Разреженный массив - История изменений

Patarakin в 09:41, 19 октября 2022

2022-10-19T09:41:38Z

← Предыдущая версия		Версия от 12:41, 19 октября 2022
Строка 1:		Строка 1:
	~~{{К объединению\|8 декабря 2021\|Разреженная матрица}}~~
	'''Разре́женный масси́в''' — абстрактное представление обычного [[Массив (программирование)\|массива]], в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимает одно и то же значение (значение по умолчанию, обычно 0 или null). Причём хранение большого числа нулей в массиве неэффективно как для хранения, так и для обработки массива.		'''Разре́женный масси́в''' — абстрактное представление обычного [[Массив (программирование)\|массива]], в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимает одно и то же значение (значение по умолчанию, обычно 0 или null). Причём хранение большого числа нулей в массиве неэффективно как для хранения, так и для обработки массива.

Строка 27:		Строка 26:
	* [[Разреженный файл]]		* [[Разреженный файл]]

	~~== Ссылки ==~~
	* [https://web.archive.org/web/20080225013226/http://www.boost.org/libs/numeric/ublas/doc/vector_sparse.htm Boost sparse vector class]
	* {{статья\|автор=Buda R. \|заглавие=Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm\|издание=Computational Economics\|год=2008\|том=31\|выпуск=4 (May)\|страницы=397—408\|ссылка=http://portal.acm.org/citation.cfm?id=1363086&jmp=cit&coll=GUIDE&dl=GUIDE\|doi=\|arxiv=\|язык=en}}

	~~{{computer-sci-stub}}~~
	~~{{rq\|sources\|wikify}}~~

	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]

Patarakin: 1 версия импортирована

2022-10-19T07:30:50Z

1 версия импортирована

← Предыдущая версия	Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>Gromolyak в 11:16, 4 октября 2022

2022-10-04T11:16:25Z

Новая страница

{{К объединению|8 декабря 2021|Разреженная матрица}}
'''Разре́женный масси́в''' — абстрактное представление обычного [[Массив (программирование)|массива]], в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимает одно и то же значение (значение по умолчанию, обычно 0 или null). Причём хранение большого числа нулей в массиве неэффективно как для хранения, так и для обработки массива.

В разреженном массиве возможен доступ к неопределенным элементам. В этом случае массив вернет некоторое значение по умолчанию.

Простейшая реализация этого массива выделяет место под весь массив, но когда значений, отличных от значений по умолчанию, мало, такая реализация неэффективна. К этому массиву не применяются функции для работы с обычными массивами в тех случаях, когда о разреженности известно заранее (например, при блочном хранении данных).

== Способы представления ==

=== В виде ассоциативного массива ===
Разреженный массив обычно представляется как [[ассоциативный массив]]:

: <code>Sparse_Array[{pos1 -> val1, pos2 -> val2,…}]</code> или
: <code>Sparse_Array[{pos1, pos2,…} -> {val1, val2,…}]</code>,

где каждой позиции pos<sub>i</sub> соответствует значение val<sub>i</sub>. Данный способ используется для экономии памяти (и ключ, и значение несут информацию).

=== В виде связного списка ===
[[Связный список]] здесь используется вместо обычного массива потому что, во-первых, обычный массив требует место для хранения неопределенных значений. Например, при объявлении:

: <code>double arr[1000][1000];</code>

будет выделено сразу 8 Мб памяти (8 байт на одно значение × 1 000 000 значений), что является неоправданной тратой памяти. В случае же связного списка пустые значения не хранятся, и место под новые значения выделяется автоматически при добавлении или удалении элементов (в этом случае можно говорить о [[Динамическое выделение памяти|динамическом выделении памяти]]).

== См. также ==
* [[Разреженная матрица]]
* [[Разреженный файл]]

== Ссылки ==
* [https://web.archive.org/web/20080225013226/http://www.boost.org/libs/numeric/ublas/doc/vector_sparse.htm Boost sparse vector class]
* {{статья|автор=Buda R. |заглавие=Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm|издание=Computational Economics|год=2008|том=31|выпуск=4 (May)|страницы=397—408|ссылка=http://portal.acm.org/citation.cfm?id=1363086&jmp=cit&coll=GUIDE&dl=GUIDE|doi=|arxiv=|язык=en}}

{{computer-sci-stub}}
{{rq|sources|wikify}}

[[Категория:Структуры данных]]