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