Энциклопедия Turbo Pascal. Главы 1-4 - Выбор метода реализации разряженных матриц
ОГЛАВЛЕНИЕ
Выбор метода реализации разряженных матриц
При выборе связанного списка, двоичного дерева или массива указателей в качестве основы реализации разряженное матрицы следует учитывать эффективность использования оперативной памяти и время доступа.
Если разряженность очень большая, то память наиболее эффективно будет использоваться при применении связанного списка и двоичного дерева, поскольку в данном случае в памяти будут располагаться только требуемые элементы. Связи требуют небольшого дополнительного расхода памяти и обычно на расход памяти влияют незначительно. При использовании массива указателей необходимо предусмотреть место для указателя вне зависимости от наличия элемента. Здесь необходимо предусмотреть не только размещение в памяти всего массива указателей, но обеспечить память для других целей, определяемых конкретной задачей. В одних случаях это вызовет серьезные трудности, хотя в других случаях этих трудностей может не быть. Обычно приходится делать расчет требуемой памяти, чтобы понять, достаточно ли ее будет для вашей программы.
Метод хеширования занимает промежуточное место между методом, построенным на базе массива указателей, и методом, построенным на базе связанного списка или двоичного дерева. Хотя в данном случае требуется размещение в памяти всего физического массива несмотря на то, что часть элементов не будет использована, его размеры все -же будут меньше размеров массива указателей, для которого требуется предусмотреть по крайней мере один указатель для каждого логического элемента.
Однако при почти полном заполнении массива память будет использоваться более эффективно, когда применяется массив указателей. В связанных списках в двоичных деревьях как правило используется два указателя, в то время как массив указателей требует только одного указателя на каждый элемент. Например, полный массив из тысячи элементов, когда каждый указатель занимает два байта, потребует для реализации связанного списка или двоичного дерева 4000 байт для хранения указателей. Для массива указателей в этом случае потребуется 2000 байт, т.е. экономия составляет 2000 байт.
Наименьшее время доступа обеспечивает подход с применением массива указателей. Как в примере с электронной таблицей этот метод часто обеспечивает простой доступ к массиву указателей и просто обеспечивается связь с разреженной матрицей. Этот метод обеспечивает доступ к элементам разреженной матрицы почти со скоростью работы обычного массива. Поиск в связанном списке осуществляется очень медленно, поскольку здесь выполняется последовательный просмотр элементов списка. Даже при добавлении данных в связанный список, обеспечивающих более быстрый поиск элементов, поиск будет выполняться медленней, чем прямой доступ к элементам массива указателей. При использовании двоичного дерева быстродействие повышается, но все-же оно меньше, чем при прямом доступе к элементам массива указателей.
При правильном выборе алгоритма хеширования этот метод часто дает лучшее время доступа, чем время доступа при использовании двоичных деревьев. Однако он никогда не достигнет быстродействия метода массива указателей.
Если возможно применение метода массива указателей, то этот метод является наилучшим из-за очень хорошего быстродействия. Однако, если решающее значение имеет эффективность использования памяти, то остается использовать лишь связанный список или двоичное дерево.