Главная | Обратная связь | Поможем написать вашу работу!

Построение модели задачи. Процедурная абстракция и абстракция данных.

Структуры данных и эффективность алгоритмов.

Любой алгоритм (хороший или плохой) требует одной или более структур данных для представления элементов проблемы, которую нужно решить, и информации, вычисляемой в процессе решения. Структура данных - это набор данных, связанных специальным образом. Хотя понятие «структура данных» (прежде всего) означает определенный способ организации взаимосвязей между компонентами (и способ представления этих взаимосвязей), но по существу подразумевает и набор операций для работы с ее компонентами.

Для одних и тех же данных различные структуры могут занимать неодинаковое пространство памяти. Одни и те же операции с различными структурами данных дают алгоритмы неодинаковой эффективности по времени и памяти. Простые алгоритмы могут порождать сложные структуры данных и наоборот, сложные алгоритмы могут использовать простые структуры данных. Программисты постоянно изыскивают способы повышения быстродействия или экономии пространства памяти за счет оптимального выбора организации данных и управления ими. При решении достаточно простых задач выбор того или иного подхода вряд ли имеет особое значение, если только выбранный подход приводит к правильному решению. Однако, при решении сложных задач (или в приложениях, в которых приходится решать очень большое количество простых задач) мы немедленно сталкиваемся с необходимостью разработки методов, при которых время или память используются с максимальной эффективностью.

Пример 1.Построение ряда Фарея.

Построить ряд Фарея F_n порядка n - последовательность всех несократимых дробей:

§ из интервала [0,1] в порядке возрастания,

§ знаменатели которых не превосходят n.

Например, для n=6: 0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1.

Можно конечно сначала построить последовательность всех дробей со знаменателем, не превосходящим n, потом отсеять сократимые и упорядочить оставшиеся. Но остается неприятный осадок – а насколько обоснована необходимость такого, в общем-то, окольного пути с не ясно насколько нужными и обременительными промежуточными вычислениями.

Можно попробовать строить последовательность сразу в требуемом порядке. Но быстро проясняется, что построение очередных элементов этого ряда связано с подбором нужного из возрастающего количества кандидатов.

В теории чисел доказано, что ряд Фарея F_n можно строить, используя рекуррентное соотношение:

§ F₁ = 0/1, 1/1.

§ для n>1 F_n можно построить по F_n-1: если для пары соседних элементов, назовём их (a/b, c/d), выполнено соотношение (b+d)=n, то вставляем между ними новый (a+c)/(b+d).

А это уже почти программа. При этом, поскольку речь идет о конечной последовательности, представляется естественным для хранения элементов ряда использовать структуру данных массив:

VAR f:ARRAY[0..?] OF RECORD p,q:INTEGER END;

BEGIN READ(n);

//Строим F1:

f[0].p:=0;f[0].q:=1;f[1].p:=1;f[1].q:=1;k:=2;

//k число элементов ряда

FOR i:=2 TO n DO

BEGIN

//Строим Fi по Fi-1, просматривая все пары соседних элементов:

j:=0;

WHILE j<=(k-2) DO

BEGIN

IF (f[j].q+f[j+1].q)=i THEN

BEGIN //вставляем новый;

j:=j+1;k:=k+1

END;

j:=j+1

END

END.

Из приведенной реализации хорошо видно, что использование обычного массива приводит к появлению операций сдвига сегментов этого массива, количество которых возрастает, т.к. «вставляем новый» предполагает следующие действия:

§ сдвинуть: f[j+1..k-1] → f[j+2..k]

§ положить: f[j+1].p:=f[j].p+f[j+1].p; f[j+1].q:=i

...причём один и тот же элемент придется перемещать (на одну позицию) многократно, а точнее ровно столько раз, сколько вставок до него понадобиться сделать (знать бы «сколько», можно было бы сразу положить «куда надо»!).

Можно ли устранить «повторное вычисление»? Проанализируем ситуацию, попытаемся понять причину появления этого «повторного вычисления», возможно яснее станет, как устранить причину, а тогда возможно пропадут и последствия...

Алгоритм в явном виде использует два отношения порядка:

§ порядок возрастания элементов ряда Фарея - он необходим для проверки условия вставки и для вычисления значения нового элемента;

§ порядок появления новых элементов ряда Фарея - он есть, он отличается от порядка возрастания, при этом надо как-то где-то сохранять появляющееся.

Если хранить в порядке возрастания, то получаем проблему «сдвигов», а если хранить в порядке появления, то получаем проблему «как вычислить значение нового элемента» (проблему «подбора»).

Выбранная структура представления данных задает единственный вариант перебора её элементов – в порядке индексации. Можно ли модифицировать структуру данных для хранения информации об обоих порядках? - подобрать способ хранения, подходящий и для добавления новых элементов, и для просмотра в порядке возрастания. Ответ положительный, такой способ хранения имеется:

Будем хранить элементы ряда Фарея в массиве в порядке появления, это удобно при сохранении нового элемента.
А для хранения информации о порядке возрастания добавим специальное поле next, с помощью которого свяжем элементы ряда Фарея в цепочку в порядке возрастания.

Для n=6 – структура выглядит следующим образом:

Рис. 1. Иллюстрация порядка следования элементов ряда

С учетом выбранной структуры данных наша программа примет следующий вид:

VAR f:ARRAY[0..?] OF RECORD p,q,next:INTEGER END;

BEGIN READ(n); // Строим :

f[0].p:=0; f[0].q:=1; f[0].next:=1;

f[1].p:=1; f[1].q:=1; f[1].next:=0; k:=2;

FOR i:=2 TO n DO

// Строим ряд по , просматривая все пары соседних

// элементов в :

BEGIN j1:=0; j2:=f[j1].next;

WHILE j2<>0 DO // второй в этой паре имеется

BEGIN

IF (f[j1].q+f[j2].q)=i THEN

BEGIN //вставляем новый элемент ряда между ними:

//добавить в конец:

f[k].p:=f[j1].p+f[j2].p; f[k].q:=i;

//связать по возрастанию:

f[k].next:=j2; f[j1].next:=k;

//учесть новый:

k:=k+1

END;

//перейти к следующей паре элементов:

j1:=j2; j2:=f[j1].next

END

END.

Мы подобрали структуру данных, которая позволяет: хранить последовательность в порядке возрастания её элементов и эффективно выполнять для неё операцию «вставить» (элемент в текущую позицию) без обременительных расходов на «сдвиги». Это классическая структура данных – связанный список. Но вопросы ещё остались:

§ Для этой структуры данных требуется дополнительное пространство памяти для хранения значений поля next (ориентировочно 0.5 от первоначально использованной)[1].

§ Преимущество этой структуры данных в устранении расходов времени на «сдвиги» является очевидным, но как оценить, имеется ли реальный выигрыш по времени в сравнении, например, с первоначальным алгоритмом – построить, отсеять и упорядочить? и даже если он есть, то насколько он существенен.

§ К тому же, нельзя сказать, что последний алгоритм ничего не делает лишнего. Если бы на каждый выходной элемент ряда Фарея он выполнял не более C операций (для подходящей константы C), то его эффективность представлялась бы достаточно обоснованной. Однако дела обстоят не так – для каждого i при построении F_i алгоритм просматривает все соседние пары элементов, а добавляет новый элемент только для некоторых их них.

Чтобы конструктивно обсуждать эти вопросы и сравнивать различные подходы, нужна подходящая мера для используемых ресурсов - времени работы и объема памяти.

Пример 2. Лексикографическая сортировка [2 п.3.2.].

Упорядочить последовательность (длины n) слов (длины k) в алфавите a..z.

Обозначим через w_i[m..k] последовательность символов с номерами от m до k для слова w_i_. Проведем рассуждение, используя классический метод последовательных уточнений:

§ Пусть последовательность W=w₁w₂... w_n уже упорядочена в следующем смысле: i≤j Þ w_i[m..k]≤w_j[m..k]. Т.е. в сравнении слов принимали участие только символы, находящиеся в позициях от m до k, а символы в позициях 1..(m-1) игнорируются (смотрим на слово с правого конца, а символы после m-го просто не видны («находятся в тумане»)).

§ Распределим слова последовательности W по значению (m-1)-го символа на 26[2] последовательностей (карманов) Q[a..z]. Т.е. слово w попадает в карман Q[a], если (m-1)-й символ w[m-1]=’a’, в карман Q[b] - если w[m-1]=’b’ и далее в алфавитном порядке. После чего соберем последовательности Q[a..z] снова в последовательность W.

В итоге снова получим последовательность W, но уже упорядоченную в смысле: i≤j Þ w_i[(m-1)..k]≤w_j[(m-1)..k] (т.е. теперь видим подальше до (m-1)-го символа). При этом необходимо соблюдать следующие условия распределения и сборки:

§ при распределении по карманам Q[a..z] добавляем слова в конец, чтобы порядок, имеющийся в W, сохранился внутри каждого кармана;

§ при сборке карманов в исходную последовательность W сначала переписываем слова из Q[a], потом слова из Q[b] и т.д.

Таким образом, слова в W после сборки будут упорядочены по символу в (m-1)-й позиции, а внутри пачки с одинаковым символом в этой позиции слова будут упорядочены как в W до распределения.

Любая исходная последовательность является упорядоченной в вышеописанном смысле при m=k+1 (т.е. в начальной ситуации, когда мы совсем плохо видим...), а на каждом шаге мы получаем более точную упорядоченность, неумолимо приближаясь к решению задачи при m=1.

Какие структуры данных потребуются для реализации этого алгоритма:

§ W: ARRAY[1..n] OF STRING[k];

§ Q: ARRAY[‘a’..’z’] OF ARRAY[1..n] OF STRING[k];

Использование в Q такого массива строк представляется изначально избыточным. Просчитать заранее, сколько строк должен содержать один карман не удается, это определяется исходной последовательностью. В самом деле, каждый карман может оказаться пустым в результате текущего распределения, а с другой стороны – все слова из последовательности W могут попасть в один из карманов. Однако предложенный вариант опять оставляет неприятный осадок – для хранения n слов приходится резервировать пространство памяти, способное хранить 26*n слов.

Устранить этот необоснованный перерасход памяти можно с помощью структуры данных «связанный список».

// Здесь будем хранить последовательность W:

W: ARRAY[1..n] OF RECORD w:STRING[k]; next:0..n END;

// В случае связного представления последовательности

// нет необходимости перемещать её элементы, достаточно

// изменять только связи между ними. Поэтому в Q будем

// хранить не элементы, а только номера позиций первого и

// последнего элемента каждого кармана. Сами элементы будут // оставаться в W на своих местах, но связи между ними надо // будет аккуратно корректировать в соответствии с порядком, // определяемым внутри каждого из карманов:

Q: ARRAY[‘a’..’z’] OF RECORD first,last:0..n END;

// Сохраним входную последовательность в связанном списке

// W:

FOR i:=1 TO n-1 DO BEGIN READLN(W[i].w);W[i].next:=i+1 END;

READLN(W[n].w); W[n].next:=0; Wfirst:=1; Wlast:=n;

// Выполним k распределений-сборок:

FOR m:=k DOWNTO 1 DO BEGIN

// Очистим карманы:

FOR s:=’a’ TO ’z’ DO BEGIN Q[s].first:=0;Q[s].last:=0 END;

// Распределим слова последовательности W по карманам:

i:=Wfirst;

WHILE i<>0 DO BEGIN s:=W[i].w[m];

IF Q[s].first=0 THEN {карман был пустой:}

BEGIN Q[s].first:=i; Q[s].last:=i END

ELSE BEGIN j:=Q[s].last; W[j].next:=i END;

Q[s].last:=i; i:=W[i].next; W[Q[s].last].next:=0

END;

// Теперь вместо одной последовательности, начинающейся

// в позиции с номером Wfirst, имеем несколько

// последовательностей, начинающихся в позициях

// Q[s].first (для s: a..z)

// Проведем сборку W, причем учтем, что нет необходимости

// корректировать все связи, достаточно только связать

// последний элемент каждого кармана с первым элементом

// следующего кармана:

Wfirst:=0; Wlast:=0;

FOR s:=‘a’ TO ’z’ DO BEGIN j:=Q[s].first;

IF j<>0 THEN BEGIN {карман не пустой:}

IF Wfirst=0 THEN Wfirst:=j ELSE W[Wlast].next:=j;

Wlast:=Q[s].last

END

END END

Мы подобрали структуру данных, которая позволяет устранить вышеотмеченный необоснованный перерасход памяти, правда дополнительное пространство памяти для организации связного спискового представления последовательностей всё же потребуется.

Построение модели задачи. Процедурная абстракция и абстракция данных.

Хороший подход к разработке эффективного алгоритма для данной задачи - изучить ее сущность. Часто задачу можно сформулировать на языке основных математических понятий, таких, как множество, и тогда алгоритм для нее можно изложить в терминах основных операций над основными объектами.

Преимущество такой точки зрения в том, что можно проанализировать несколько различных структур данных и выбрать из них ту, которая лучше всего подходит для задачи в целом. Таким образом, разработка хорошей структуры данных идет рука об руку с разработкой хорошего алгоритма.

Ахо А., Хопкрофт Дж., Ульман Дж.

Построение и анализ вычислительных алгоритмов. [2]

В любой задаче имеются определенные информационные связи между данными и структура данных должна в определенной степени эти связи отображать. Если в структуре данных это соответствие представлено не адекватно (недостаточно полно), то соответствующее приведение придется делать на уровне алгоритма, что увеличит время его работы.

Снова вернемся к задаче о ряде Фарея, а точнее к алгоритму ее решения, основанному на рекуррентном соотношении построения этого ряда. Видимо мы слишком поторопились с выбором конкретной структуры данных, слишком банально сделан вывод – раз уж речь идет о конечной последовательности, значит необходимо использовать векторы ARRAY[0..?] OF RECORD p,q:INTEGER END.

Но информационные связи между элементами этой последовательности более сложны, чем между элементами просто вектора, с одной стороны они связаны в последовательность по определению - в порядке возрастания, а с другой стороны рекуррентное соотношение связывает их порядком порождения. Алгебраический взгляд на модель задачи позволяет зафиксировать операциональную составляющую (а может быть и сущность) имеющихся информационных связей между данными.

И все-таки в этом алгоритме речь идет о (конечной) последовательности и об операциях с нею:

§ об операции последовательного просмотра последовательности, т.е. начиная от первого, к следующему и т.д.

§ об операции вставки элемента в текущую позицию просмотра.

Такова модель этой задачи, в терминах которой рекуррентным соотношением собственно и описан алгоритм ее решения. Если мы знакомы с проблематикой структур данных, то видимо, знаем – в случае представления последовательности массивом операция вставки реализуется плохо, а хорошо она реализуется именно в случае представления связанным списком, причем для данного случая достаточен односторонний список (с понятием «текущая позиция»), так как необходим только последовательный просмотр.

Аналогичная ситуация и со второй задачей - о лексикографической сортировке. Можно по-разному формулировать причину перерасхода памяти в первой версии представления данных:

§ Массив – статическая структура данных (размер области памяти определяется описанием массива). А последовательности, на которые разбивается текущая последовательность, имеют динамический (вычисляемый в процессе работы алгоритма) размер. Отсюда и происходит необходимость резервировать память с избытком.

Но при более детальном анализе ситуации становится ясно, что это скорее следствие другой, более глубокой причины.

§ Работа алгоритма состоит в разбиении текущей последовательности на подпоследовательности и последующей сборке этих подпоследовательностей опять в одну - общую. Эти операции не изменяют число элементов последовательности - тогдазачем дополнительная память?

Но если попытаться решать эту задачу «разбить-собрать», например, перестановками элементов внутри массива, то мы сразу столкнемся с проблемой «тесноты»: надо положить элемент в сегмент массива, запланированный для соответствующего кармана, но там лежит другой (еще не квалифицированный элемент), сначала его куда-то надо перемещать.

Фактически, причину возникающей проблемы можно сформулировать ровно так же, как и в предыдущей задаче – у текущей последовательности свой порядок, у каждой подпоследовательности (в кармане) свой, а собираемая последовательность будет иметь свой - как и где хранить информацию обо всех этих порядках, ведь ими надо пользоваться в процессе обработки.

И все-таки причины (видимо всегда) лежат в информационных связях между данными задачи, а вскрывать и описывать их можно по-разному...

С алгебраической точки зрения, модель этой задачи, в терминах которой собственно и было проведено рассуждение методом последовательных уточнений - мы работаем с набором последовательностей, с которыми выполняются операции: последовательного просмотра, исключения и включения элементов, а также операции сцепления последовательностей. Но приведенная формулировка операций излишне грубовата и приведет к выбору структуры данных с излишними возможностями и излишними расходами на их реализацию.

Аккуратный анализ рассуждения, обоснования алгоритма лексикографической сортировки, дает более детальную формулировку операций:

§ Каждый шаг просмотра связан с удалением просматриваемого элемента из последовательности, как в известной структуре данных «очередь» - реально просматривается всегда только первый элемент, после чего он удаляется.

§ Включение элементов выполняется всегда в конец последовательности (причем другой), тоже как в структуре данных «очередь».

§ При сцеплении вторая из сцепляемых последовательностей не сохраняется, а становится частью результата.

Связное представление последовательностей позволяет реализовать такой набор операций эффективно как по времени, так и по памяти, причем с учетом особенностей алгоритма решения задачи ясно, что объем используемой памяти будет оставаться фиксированным и (почти) равным объему исходной последовательности.

Лексикографическим порядком на множестве векторов различной длины, построенных над конечным алфавитом называется такая последовательность, для которой выполнение условия , , означает, что выполнено одно из условий:

1) существует такое целое число , что и для всех справедливо

2) и при .

Например, обычно основы слов в словарях расположены в лексикографическом порядке.

Задача: Используя идею лексикографической сортировки для слов одинаковой длины, написать алгоритм лексикографической сортировки цепочек в общем случае

Пример 3. Связность [3 гл.1.].[3]

Предположим, что имеется последовательность пар целых чисел, в которой каждое целое число представляет объект некоторого типа, а пара p-q интерпретируется в значении «р связано с q». Мы предполагаем, что отношение «связано с» является симметричным [4] и транзитивным [5] (т.е. это отношение эквивалентности).

Задача состоит в написании программы исключения лишних пар:

§ Когда программа вводит пару р-q, она должна вывести её, если полученные до этого момента пары не позволяют утверждать, что р связано с q, даже через промежуточные связи (т.е. р,q – пока не эквивалентны).

§ Если же в соответствии с ранее полученными парами следует, что р уже связано с q, возможно через промежуточные связи (т.е. р,q – эквивалентны), то эту пару программа должна игнорировать.[6]

ввод	вывод	Существующая связь
3-4	3-4
4-9	4-9
8-0	8-0
2-3	2-3
5-6	5-6
2-9		2-3-4-9
5-9	5-9
7-3	7-3
4-8	4-8
5-6		5-6
0-2		0-8-4-3-2
6-1	6-1

Кстати, такая постановка задачи называется вычислением в префиксном (on-line) режиме (или «в реальном времени», в несколько более жестком варианте определения).

Пример решения задачи показан на рис.2.

Таким образом, задача состоит в разработке программы, которая может запомнить достаточный объем информации о просмотренных парах, чтобы решить, связана ли новая пара объектов.

Рис 2. ПРИМЕР СВЯЗНОСТИ Для заданной последовательности пар целых чисел, представляющих связь между объектами (слева), задача алгоритма связности заключается в выводе тех пар, которые обеспечивают новые связи (в центре). Например, пара 2-9 не должна выводиться, поскольку связь 2-3-4-9 определяется ранее полученными связями (подтверждение этого показано справа).

Подобная задача возникает в ряде важных приложений. Например, числа р и q могли бы представлять номера компьютеров в большой сети, а пары могли бы представлять соединения в сети. Тогда такая программа могла бы использоваться для определения того, нужно ли устанавливать новое прямое соединение между р и q, чтобы иметь возможность обмениваться информацией, или же можно было бы использовать существующие соединения для установки коммуникационного пути.

Отметим, уже в формулировке задачи мы абстрагировались от конкретного содержания объектов (и способа их представления), ограничившись тем, что нам известны идентифицирующие их ключи (р,q...). От конкретного содержания связей между объектами мы тоже абстрагировались, например, от пропускной способности соединений в той самой сети компьютеров. Возможно, это не помешает применению нашего алгоритма в соответствующем приложении, а возможно потребуется его соответствующая адаптация к более детальным условиям приложения.

Рассмотрим модель для нашей задачи.

При получении каждой новой пары вначале необходимо определить, представляет ли она новое соединение, и если представляет, то внедрить информацию об обнаруженном соединении в общую картину о связности объектов для проверки соединений, которые будут наблюдаться в будущем. Эту текущую «общую картину о связности» можно описать семейством множеств, каждое множество включает все связанные (между собой) объекты (возможно через промежуточные связи) и никакая пара множеств в семействе не пересекается (т.е. множество – это класс эквивалентности, а семейство – разбиение универсума всех элементов на классы эквивалентности).

Таким образом, модель нашей задачи задается:

§ Семейством непересекающихся множеств целых чисел.

§ Набором операций:

§ Найти множество (find), содержащее данный элемент.

§ Объединить (union) два множества, при этом в семействе появляется результат объединения, а объединяемые множества не сохраняются, а становятся частью результата.

Решение задачи связности в терминах этой модели описывается так:

§ После ввода новой пары p-q мы выполняем операцию find для каждого члена пары.

§ Если члены пары находятся в одном множестве, мы переходим к следующей паре; если нет, то выполняем операцию union, объединяем множества, которым они принадлежат, и выводим пару (т.е. поступление дополнительных сведений о связности-эквивалентности приводит к объединению классов эквивалентности).

Теперь рассмотрим несколько вариантов выбора структур данных для представления таких семейств множеств, а для них соответствующие варианты реализации интересующих нас операций и варианты программ решения нашей задачи о связности. Для устранения деталей, отвлекающих от основных целей, будем считать, что на вход могут поступать только целые числа из полуинтервала [0,N).

Программа 3.1.Решение задачи связности методом быстрого поиска.

§ Структура данных для представления семейства непересекающихся множеств целых чисел.

Вспомним классическое представление множеств с помощью характеристических 0-1-векторов и воспользуемся подходящим его обобщением:

id: ARRAY[0..N-1] OF INTEGER;

Каждому числу p из [0,N) соответствует в этом массиве p-я позиция, а значение id[p] – представляет имя множества, которому p принадлежит (т.е. p Î id[p]). Множества мы будем идентифицировать одним из чисел, ему принадлежащих (т.е. представителем класса эквивалентности, в соответствии с общематематической терминологией).

§ Реализация операций:

find(p)=id[p] – операция «найти» реализуется очень хорошо, именно поэтому этот вариант и назван методом «быстрого поиска».

Но операцию union(t,s) эффективно реализовать не удается, придется просмотреть весь id. Будем интерпретировать union(t,s) как t:=tÈs, требуемый результат мы получим, если во всех позициях id, в которых id[i]=s (что означает iÎs), проставим t (что означает - теперь iÎt).

// Обозначим именем i одноэлементное множество {i} и

// инициализируем id семейством всех одноэлементных множеств:

FOR i:=0 TO N-1 DO id[i]:=i;

// Приступаем к обработке входной последовательности:

WHILE NOT EOF(input) DO BEGIN READLN(p,q);

t:=id[p]; // t:=find(p)

IF t<>id[q] THEN{p,q – пока не связаны} BEGIN WRITELN(p,q);

// А теперь пополним текущую «общую картину о связности»:

// union(id[q],id[p]): id[q]:=id[q]Èid[p]:

FOR i:=0 TO N-1 DO IF t=id[i] THEN id[i]:=id[q]

END

Причина больших затрат времени на выполнение операции «объединить» была заложена изначально в структуре данных, выбранной для представления семейства множеств, она запредельно ориентирована на быстрый поиск, явно в ущерб для операции «объединить».

Массив, как известно, это (таблично заданная хранимая) функция. Прямой доступ к элементам этой структуры данных обеспечивает «быстрый поиск». С другой стороны, в способе представления этой функции заложена необходимость тиражировать имя множества для каждого элемента этого множества. Отсюда и проистекает необходимость массовых корректировок, когда имя множества меняется.

В структуре данных этого алгоритма множество p определяется как p={iÎ[0..N)/id[i]=p}, т.е. можно сказать и так – каждый элемент (i) множества указывает на элемент (p), представляющий это множество. Если иметь в виду такую трактовку, то полезно посмотреть рис 3, где приведено графическое представление состояний массива id в процессе выполнения программы 3.1.

Рис 3. Представление быстрого поиска в виде дерева для примера, приведенного на рис 2.

Рис 4. Представление быстрого объединения в виде дерева для примера, приведенного на рис 2.

Рисунок наглядно иллюстрирует: почему время поиска хорошее – потому что путь от элемента к множеству предельно короткий (одно ребро), а почему время объединения плохое – потому что всем элементам одного из множеств надо изменить указатель на представителя множества – результата объединения (это не считая того, что эти элементы надо еще найти).

Программа 3.2.Решение задачи связности методом быстрого объединения.

Этот алгоритм основан на методе двойственном предыдущему, теперь акцентируем основное внимание именно на быстром объединении. В основе этого алгоритма лежит та же структура данных – массив, индексированный по именам объектов. Но в нем используется иная интерпретация значений, что приводит к более сложной структуре данных. Иная интерпретация значений массива id означает иное представление той функции id, о которой говорилось выше. Ясно, что если бы имя множества, которому принадлежит элемент, не тиражировалось, то и не было бы проблемы массовой корректировки при выполнении операции объединения.

Вспомним решение задачи о лексикографической сортировке, в котором операция «сцепить» две последовательности выполнялась одним действием – связать последний элемент первой последовательности с первым элементом второй. Это хорошо известная типовая возможность связного представления данных, причем она применима при определенных условиях не только к связным спискам, а к любым связным структурам.

§ Структура данных для представления семейства непересекающихся множеств целых чисел.

id: ARRAY[0..N-1] OF INTEGER;

Как и раньше, множества мы будем идентифицировать представителем - одним из чисел, которые ему принадлежат. Но теперь будем допускать, что элемент множества не обязательно сразу указывает на элемент, представляющий это множество, а возможно указывает на другой элемент, тоже принадлежащий этому множеству и т.д. вплоть до элемента, указывающего на себя, т.е. id[p]=p. Такой элемент p и используется в качестве представителя множества p.

Точнее, если:

i₀, id[i₀]=i₁, id[i₁]=i₂,... id[i_k]=p, id[p]=p

то i₀,i₁,i₂,... i_k,p Î p (как множеству с именем p), причем в таких цепочках по указателям естественно запрещены циклы (но есть петля в конце).

Отметим, что приведенное определение не означает, что множества представляются обязательно цепочками. В общем случае множество представляется деревом, а в этом определении речь идет только об одной из ветвей такого дерева (от вершины i₀ до корня p). Т.е. множество p определяется как

p={iÎ[0..N)/id[id[...id[i]...]]=p=id[p]}().

Теперь функция id (для элемента возвращающая имя множества, которому принадлежит этот элемент) будет иметь в какой-то части табличное представление, а в какой-то вычислимое. Отсюда прогнозируются частично выгоды (прямого доступа к данным), а частично и затраты (на вычисления).

§ Реализация операций:

Операция union(t,s), в трактовке t:=tÈs, теперь реализуется очень просто. Поскольку t,s – корни представляющих деревьев, t=id[t] и s=id[s], то оператор id[s]:=t заставит каждый путь от элемента множества s до корня s этого дерева продолжить (одним переходом) до t – корня дерева t.

Хуже дела обстоят с операцией find, согласно вышеприведенному определению: find(i)= id[id[...id[i]...]]=p=id[p], т.е. придется пройти путь от элемента до корня.

// Обозначим именем i одноэлементное множество {i} и

// инициализируем id семейством всех одноэлементных множеств:

FOR i:=0 TO N-1 DO id[i]:=i;

// Приступаем к обработке входной последовательности:

WHILE NOT EOF(input) DO BEGIN READLN(p,q);

t:=p; WHILE t<>id[t] DO t:=id[t]; // t:=find(p)

j:=q; WHILE j<>id[j] DO j:=id[j]; // j:=find(q)

IF t<>j THEN {p,q – пока не связаны} BEGIN WRITELN(p,q);

// А теперь пополним текущую «общую картину о связности»:

id[t]:=j // union(j,t): j:=jÈt

END

Полезно посмотреть рис 4, где приведено графическое представление состояний массива id в процессе выполнения программы 3.2, и сравнить с рис 3 для программы 3.1. Рис 3.2 наглядно иллюстрирует характерные особенности программы 3.2 в использовании ресурса времени. Почему время поиска не очень хорошее – потому что путь от элемента к множеству теперь может оказаться многошаговым (несколько ребер). А почему время объединения очень хорошее – потому что объединение теперь не требует массовых изменений данных, только одна корректировка указателя на представителя множества – результата объединения.

Интересно разобраться в двух вопросах: сравнить в целом эти два алгоритма в смысле эффективности по времени, и насколько в новом алгоритме могут быть велики затраты времени на выполнение операции «найти». Общие соображения и анализ графического представления типа рис. 3 - 4 для различных вариантов входной последовательности наводят на мысль, что новый алгоритм лучше, а экспериментальное тестирование этих программ может даже подтверждать такое заключение.

Но внимательный анализ позволяет показать, что гарантий для такого заключения нет. Например, если пары вводятся в следующем порядке: 1-2, 1-3, 1-4 и т.д., то все элементы будут попадать в одно множество связности, а операция «объединить» будет связывать эти элементы в дерево с одной ветвью (1®2®3®4®...), длина которой постоянно возрастает. А значит, для каждой входной пары 1-p будет выполняться find(1), проходящий эту ветвь от листа 1 до (все более далекого) корня. Можно подсчитать, что на этой входной последовательности длины t алгоритм будет выполнять примерно t² переходов по ребрам пути к корню дерева, а это реалистичная оценка времени работы алгоритма. Можно конечно сказать, что эта ситуация выправляется просто, надо запоминать, какому множеству принадлежит элемент 1. Но плохих, в аналогичном смысле, входных последовательностей можно построить сколько угодно, а сцепляя их в различных порядках можно полностью запутать картину – и придется это запоминать для каждого элемента, т.е. получается, что к новому представлению данных добавим предыдущее с вышерассмотренными проблемами его поддержания.

Нетрудно показать, что на этом и аналогично плохих входах, новый алгоритм работает не лучше, чем предыдущий – он затрачивает много времени на операции «найти», а предыдущий затратит такое же время на операции «объединить» (фактически по той же самой причине). Аккуратными расчетами можно показать, что новый алгоритм не лучше предыдущего по времени в худшем, но все же лучше – по времени в среднем (что обычно и проявляется в экспериментальном тестировании).

Обнаруженная причина возможно очень плохого времени выполнения операции «найти» заключена в возможности получить очень разбалансированное дерево. Если бы удалось гарантировать, что дерево постоянно ветвится, причем на поддеревья примерно одинакового объема (например, по количеству вершин), то очень длинных ветвей не могло бы быть из мощностных соображений (в ветвящемся дереве с очень длинными ветвями очень много элементов). Эту идею мы и попытаемся реализовать в следующем алгоритме.

Программа 3.3.Решение задачи связности методом взвешенного быстрого объединения.

Предыдущий алгоритм можно легко модифицировать, чтобы худшие случаи, подобные вышерассмотренному, гарантированно не могли появиться. Вместо того чтобы произвольным образом соединять второе дерево с первым при выполнении операции union, будем отслеживать количество вершин в каждом дереве и всегда присоединять меньшее дерево к большему, это позволит поддерживать приемлемую сбалансированность деревьев. Это изменение требует наличия еще одного массива для хранения количества вершин в деревьях, но оно ведет к существенному повышению эффективности, причем гарантированному, т.е. по времени в худшем.

Как было сказано выше, нам потребуется дополнительный массив

sz: ARRAY[0..N-1] OF INTEGER;

Для каждого i, у которого id[i]=i, т.е. i является корнем дерева (представителем класса эквивалентности), в sz[i] будем хранить количество вершин в дереве с корнем i (т.е. мощность множества – класса эквивалентности i).

// Инициализируем id семейством всех одноэлементных множеств,

// а sz – соответственно объемами этих множеств.

FOR i:=0 TO N-1 DO BEGIN id[i]:=i; sz[i]:=1 END;

// Приступаем к обработке входной последовательности:

WHILE NOT EOF(input) DO BEGIN READLN(p,q);

t:=p; WHILE t<>id[t] DO t:=id[t]; // t:=find(p)

j:=q; WHILE j<>id[j] DO j:=id[j]; // j:=find(q)

IF t<>j THEN {p,q – пока не связаны} BEGIN WRITELN(p,q);

// А теперь пополним текущую «общую картину о связности»:

IF sz[t]<sz[j] THEN // множество t меньше множества j

// union(j,t): j:=jÈt: к большему j подсоединяем меньшее t

BEGIN id[t]:=j; sz[j]:=sz[j]+sz[t] END

ELSE // множество j меньше множества t

// union(t,j): t:=tÈj: к большему t подсоединяем меньшее j

BEGIN id[j]:=t; sz[t]:=sz[t]+sz[j] END

END

Рис. 5 в сравнении с рис. 4 наглядно иллюстрирует характерные особенности деревьев, которые строит программа 3.3, для представления соответствующих множеств. Они явно лучше сбалансированы и длины путей, как правило, заметно меньше. А значит на выполнение операций «найти» будет заметно меньше расходоваться времени. И все же, что меньше и почему меньше, более или менее ясно, а насколько меньше?

Рис. 5 Представление взвешенного быстрого объединения в виде дерева

Характеризующая особенность деревьев, которые будет строить этот алгоритм, состоит в следующем:

§ Эти деревья – ветвящиеся, почти в каждой вершине оно ветвится, только внизу на уровне перед листьями могут появиться короткие не разветвляющиеся пути.

§ Его рост в высоту сбалансирован ростом в ширину [7].

На этой последовательности рисунков демонстрируется результат изменения алгоритма быстрого объединения для связывания корня меньшего из двух деревьев с корнем большего из деревьев. Расстояние от каждого узла до корня его дерева не велико, поэтому операция поиска выполняется эффективно.

Аккуратными расчетами можно показать, что у сбалансированных деревьев длина пути не может превосходить логарифма (двоичного) от количества вершин.

12 3 4 5 6 7 8 9 10 Следующая ⇒