Быстрая перестановка

Как отмечалось при анализе полосковой диаграммы для оценки затрат машинного времени, на процедуру перестановки может затрачиваться значительная доля времени при выполнении программы расчета спектров. Традиционный медленный алгоритм перестановки использует процедуру изменения порядка следования символов последовательности на обратный (см. разд. «Ячеистая структура перестановочной диаграммы» в гл. 7) и требует для его реализации число операций, пропорциональное . Следовательно, даже для длинных последовательностей данных доля времени, затрачиваемая на перестановку элементов, никогда не становится пренебрежимо малой. Процедуру перестановки целесообразно осуществлять и иллюстрировать с помощью кристаллической структуры, упомянутой выше при рассмотрении перестановочной диаграммы. Сначала определим координаты ячеек с помощью следующих равенств:

где - число ячеек, укладывающихся вдоль одной координаты, или в зависимости от того, является ли величина Р четной (семейство I) или нечетной (семейство II), a - перестановочная функция для N элементов.

Так как общее число ячеек N о пропорционально N, время, затрачиваемое на вычисление координат ячеек, возможно, окажется просто пропорциональным N. Если должно быть удовлетворено именно данное требование, то доля в суммарных затратах времени будет незначительной. Для асимптотической оценки сложности процедуры, предусматривающей подсчет числа операций в пределе для больших N, считается, что так как перестановка предполагает выполнение (Р — 1) этапов для каждой из N операций, время вычисления для будет асимптотически стремиться к Однако был предложен интересный способ преодоления этого

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

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

Описанный здесь метод иллюстрируется в программе вычислений FASTPERMUTE, приведенной в приложении 1. В эту программу в качестве подпрограммы включен сегмент, реализующий перестановку элементов с целью получения в прежпие времена мы бы использовали термин definitio in circulo, теперь же мы употребим термин «уплотненная упаковка». Парадоксально, но факт: вся программа реализуется быстрее, чем ее отдельный сегмент. При этом можно представить себе реккурентную процедуру в виде операции, осуществляющей перестановку элементов укороченной последовательности с дальнейшим уменьшением ее размеров. Вскоре окажется, что результирующая последовательность будет состоять из двух элементов, вследствие чего не потребуется дальнейшая перестановка элементов.