Разреженный массив
Шаблон:К объединению Разре́женный масси́в — абстрактное представление обычного массива, в котором данные представлены не непрерывно, а фрагментарно; большинство элементов его принимает одно и то же значение (значение по умолчанию, обычно 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 значений), что является неоправданной тратой памяти. В случае же связного списка пустые значения не хранятся, и место под новые значения выделяется автоматически при добавлении или удалении элементов (в этом случае можно говорить о динамическом выделении памяти).
См. также
Ссылки
- Boost sparse vector class
- {{#if:Buda R.|Buda R.
}}{{#if:http://portal.acm.org/citation.cfm?id=1363086&jmp=cit&coll=GUIDE&dl=GUIDE
| Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm | Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm
}}{{#if:en
| {{#ifexist: Шаблон:ref-en
| Шаблон:Ref-en
| (en)
}}
}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:Computational Economics|и}}
|аи= // {{{автор издания}}} Computational Economics
|а= // {{{автор издания}}}
|и= // Computational Economics
}}{{#if:| : {{{тип}}} }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:|и}}{{#if:2008|г}}
|миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 2008.
|ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
|мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2008.
|иг= — {{{издательство}}}, 2008.
|м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
|и= — {{{издательство}}}.
|г= — 2008.
}}{{#if:4 (May)| — В. 4 (May).
}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:31| — Т. 31.
}}{{#if:| — № {{{номер}}}.
}}{{#if:397—408| — С. 397—408. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.
}}{{#if:| — ISBN {{{isbn}}}. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if:
| [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.
}}{{#if:
|
}}{{#if:
|
}}
