Сжатие - путь
Cтраница 2
Верхняя и нижняя границы совпадают также и для алгоритмов union-find, использующих указатели. В 1975 г. Тарьян ( Tarjan) показал, что алгоритм взвешенного быстрого объединения со сжатием пути требует следования по менее, чем 0 ( % V) указателям в случае низкой производительности, и что любой алгоритм с указателями должен следовать более, чем по постоянному числу указателей в случае низкой производительности для некоторых входных данных. На практике эта разница очень мала, поскольку lg V очень мало, тем не менее, нахождение простого линейного алгоритма для этой задачи было темой исследования в течение долгого времени, и найденная Та-рьяном нижняя граница направила усилия исследователей на другие задачи. Более того, история показывает, что нельзя обойти функции наподобие сложной функции log, поскольку они присущи этой задаче. [16]
Рейнгольд [1972] приводит оптимальные алгоритмы для многих основных преобразований множеств, таких, как объединение и пересечение. Алгоритм 4.3 для задачи ОБЪЕДИНИТЬ - НАЙТИ был, по-видимому, впервые применен Мак-Илроем и Моррисом. Кнут [1969] приписывает сжатие путей Триттеру. Приложение к приравниванию идентификаторов и вычислению смещения, обсуждавшиеся в разд. [17]
Существует множество других способов реализации сжатия пути. Этот метод несколько проще реализовать, чем полное сжатие пути ( см. упражнение 1.16), но он дает тот же конечный результат. Оправдывает ли достигаемая экономия время, требующееся для реализации сжатия пути. Существует ли какая-либо иная технология, применение которой следовало бы рассмотреть. Чтобы ответить на эти вопросы, следует внимательнее присмотреться к алгоритмам и реализациям. [18]
 |
Результаты экспериментального исследования. [19] |
Конечный результат применения рассмотренных алгоритмов решения задачи связности приближается к наилучшему, на который можно было бы рассчитывать в любом практическом случае. Мы имеем алгоритмы, которые легко реализовать и время выполнения которых гарантировано связано с затратами времени на сбор данных постоянным коэффициентом. Более того, алгоритмы являются оперативными, рассматривающими каждое ребро только один раз и использующими объем памяти, который пропорционален количеству объектов; поэтому какие-либо ограничения на количество обрабатываемых ими ребер отсутствуют. Результаты экспериментального исследования, приведенные в табл. 1.1, подтверждают вывод, что программа 1.3 и ее варианты с использованием сжатия пути полезны даже в очень больших практических приложениях. [20]
Немедленно возникает вопрос, можно ли найти алгоритм, обеспечивающий гарантированную линейную производительность. Существует множество способов дальнейшего совершенствования алгоритма взвешенного быстрого объединения. В идеале было бы желательно, чтобы каждый узел указывал непосредственно на корень своего дерева, но за это не хотелось бы расплачиваться изменением большого количества указателей, как это делалось в случае алгоритма быстрого объединения. К идеалу можно приблизиться, просто делая все проверяемые узлы указывающими на корень. На первый взгляд этот шаг кажется весьма радикальным, но его легко реализовать, а в структуре этих деревьев нет ничего неприкосновенного: если их можно изменить, чтобы сделать алгоритм более эффективным, это следует сделать. Этот метод, названный сжатием пути ( path compression), можно легко реализовать, добавляя еще один проход по каждому пути во время выполнения операции union и устанавливая запись id, соответствующую каждой встреченной вершине, указывающей на корень. [21]
Однако при анализе низкой производительности существуют и некоторые трудности. Для определенных алгоритмов может существовать весомая разница между временем, необходимым для решения задачи в случае худших входных данных, и временем, необходимым в случае данных, которые встречаются на практике. Например, быстрое объединение в случае низкой производительности требует времени выполнения, пропорционального N, и пропорционального лишь logW для обычных данных. Часто не удается доказать, что существуют входные данные, для которых время выполнения алгоритма достигает определенного предельного значения; можно лишь доказать, что время выполнения будет ниже этого предела. Иногда возникает ситуация, когда алгоритм с хорошими характеристиками низкой производительности при работе с практическими данными оказывается медленнее, чем более простые алгоритмы, или же при незначительной разнице в скорости он требует дополнительных усилий для достижения хороших характеристик низкой производительности. Для многих приложений другие соображения - переносимость и надежность - являются более важными, чем гарантии, даваемые в случае низкой производительности. Например, как было показано в главе 1, взвешенное быстрое объединение со сжатием пути обеспечивает лучшие гарантии производительности, чем взвешенное быстрое объединение, но для типичных данных, встречающихся на практике, алгоритмы имеют почти одинаковое время выполнения. [22]
Страницы: 1 2