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

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

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

Пример 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

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

END.

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

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

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

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

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

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

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

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

• Пусть последовательность =₁₂ ... _n уже упорядочена в следующем смысле: i≤j  _i[m..k]≤_j[m..k]. Т.е. в сравнении слов принимали участие только символы, находящиеся в позициях от m до k, а символы в позициях 1..(m-1) игнорируются (смотрим на слово с правого конца, а символы после m-го просто не видны («находятся в тумане»)).

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

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

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

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

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

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

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

• : ARRAY[1..n] OF STRING[k];

• : ARRAY[‘a’..’z’] OF ARRAY[1..n] OF STRING[k];

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

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

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

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

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

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

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

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

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

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

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

// :

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

READLN([n].w); [n].next:=0; first:=1; last:=n;

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

FOR m:=k DOWNTO 1 DO BEGIN

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

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

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

i:=first;

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

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

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

ELSE BEGIN j:=[s].last; [j].next:=i END;

[s].last:=i; i:=[i].next; [[s].last].next:=0

END;

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

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

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

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

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

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

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

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

first:=0; last:=0;

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

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

IF first=0 THEN first:=j ELSE [last].next:=j;

last:=[s].last

END

END END

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