Чтобы понять, зачем нужны разреженные массивы, вспомните следующие два факта:
- При описании обычного массива в языке С вся память, требуемая для размещения массива, выделяется сразу после его создания.
- Большие массивы, особенно многомерные, могут занимать огромные объемы памяти.
Тот факт, что память для массива выделяется при его создании, означает, что размер самого большого массива, который вы сможете описать в своей программе, ограничен (в частности) объемом доступной памяти. Если вам понадобится массив большего размера, чем позволяют возможности компьютера, придется реализовывать его каким-то другим образом. (Например, для работы с полностью заполненными большими массивами обычно применяется та или иная форма виртуальной памяти.) Даже если большой массив разместится в памяти, создание его может существенно уменьшить доступные ресурсы системы, поскольку память, занятая большим массивом, оказывается недоступной для остальной части программы и других процессов, работающих в системе. А это в свою очередь может отрицательно сказаться на общей производительности программы или компьютера в целом. В тех ситуациях, когда будут использоваться не все элементы массива, выделение памяти под весь массив представляется особенно расточительной тратой системных ресурсов.
Чтобы избавиться от проблем, вызванных потребностью в памяти для больших редко заполненных массивов, были придуманы некоторые приемы работы с разреженными массивами. Все они характеризуются одной общей чертой: память для элементов массива выделяется только при необходимости. Поэтому преимущество разреженного массива состоит в том, что для его хранения требуется ровно столько памяти, сколько нужно для хранения только тех элементов, которые действительно используются. При этом остальная память может использоваться для других целей. Кроме того, эти приемы позволяют создавать очень большие массивы, размер которых значительно больше, чем допускаемый системой размер обычных массивов.
Существуют многочисленные примеры приложений, требующих обработки разреженных массивов. Многие из них относятся к работе с матрицами или к научным и инженерным задачам, которые понятны лишь экспертам в соответствующих областях. Однако есть одно очень популярное приложение, в котором обычно применяется разреженный массив — электронная таблица. Несмотря на то, что матрица в средней электронной таблице очень большая, в любой момент времени используется лишь некоторая ее часть. В ячейках электронных таблиц хранятся формулы, значения и строки. При использовании разреженного массива память для каждого элемента выделяется только при необходимости. Поскольку фактически используется лишь небольшая часть элементов массива, весь он (то есть электронная таблица) кажется очень большим, но занимает минимально необходимую память.
В этой главе будут часто повторяться два термина: логический массив и физический массив. Логический массив — это массив, который мыслится как существующий в системе. Например, если матрица электронной таблицы имеет размер 1`000×1`000, то логический массив, реализующий матрицу, также будет иметь размер 1`000×1`000 — даже несмотря на то, что физически такой массив не существует в компьютере. Физический массив — это массив, который реально существует в памяти компьютера. Так, если используются только 100 элементов матрицы электронной таблицы, то для хранения физического массива требуется память, необходимая для хранения лишь этих 100 элементов. Методы обработки разреженных массивов, раскрытые в данной главе, обеспечивают связь между логическими и физическими массивами.
Ниже будут рассмотрены четыре различных способа создания разреженного массива: связанный список, двоичное дерево, массив указателей и хеширование. Несмотря на то, что программа работы с электронными таблицами не разрабатывается целиком, все примеры ориентируются на матрицу электронной таблицы, показанную на рис. 23.1. На этом рисунке элемент X расположен в ячейке В2.
---A--- ---B--- ---C---
1
2 X
3
4
5
6
7
.
.
.
Рис. 23.1. Организация простой электронной таблицы