ЭЛЕКТРОННАЯ БИБЛИОТЕКА КОАПП |
Сборники Художественной, Технической, Справочной, Английской, Нормативной, Исторической, и др. литературы. |
4.16. Реализация циклических списковПроблемаТребуется создать циклический список и организовать работу с ним.РешениеВоспользуйтесь функциями unshift и pop (или push и shift) для обычного массива.unshift(@circular, pop(@circular)); # Последний становится первым
КомментарийЦиклические списки обычно применяются для многократного выполнения одной и той же последовательности действий - например, обработки подключений к серверу. Приведенный выше фрагмент не является полноценной компьютерной реализацией циклических списков с указателями и настоящей цикличностью. Вместо этого мы просто перемещаем последний элемент на первую позицию, и наоборот.sub grab_and_rotate (\@ ) {
> Смотри также --------------------------------
4.17. Случайная перестановка элементов массиваПроблемаТребуется случайным образом переставить элементы массива. Наиболее очевидное применение - тасование колоды в карточной игре, однако аналогичная задача возникает в любой ситуации, где элементы массива обрабатываются в произвольном порядке.РешениеКаждый элемент массива меняется местом с другим, случайно выбранным элементом:# fisher_yates_shuffle ( \@аггау ) : генерация случайной перестановки
$permutations = factorial^ scalar @array );
КомментарийСлучайные перестановки на удивление коварны. Написать плохую программу перестановки очень просто:sub naive_shuffle { # Не делайте так!
Такой алгоритм является смещенным - одни перестановки имеют большую вероятность, чем другие. Это нетрудно доказать: предположим, мы получили список из 3 элементов. Мы генерируем 3 случайных числа, каждое из которых может принимать 3 возможных значения - итого 27 возможных комбинаций. Однако для списка из трех элементов существует всего 6 перестановок. Поскольку 27 не делится на 6, некоторые перестановки появляются с большей вероятностью, чем другие. В приведенном выше алгоритме Фишера-Йетса это смещение устраняется за счет изменения интервала выбираемых случайных чисел. > Смотри также --------------------------------
4.18. Программа: wordsОписаниеВас когда-нибудь интересовало, каким образом программы типа Is строят столбцы отсортированных выходных данных, расположенных но столбцам, а не по строкам? Например:awk cp
ed login
mount rmdir
sum
В примере 4.2 показано, как это делается. Пример 4.2. words
Наиболее очевидный способ вывести отсортированный список по столбцам
- последовательно выводить каждый элемент списка, выравнивая его пробелами
до определенной ширины. Когда вывод достигает конца строки, происходит
переход на следующую строку. Но такой вариант хорош лишь тогда, когда строки
читаются слева направо. Если данные должны читаться по столбцам, сверху
вниз, приходится искать другое решение. Программа words представляет собой
фильтр, который генерирует выходные данные по столбцам. Она читает все
входные данные и запоминает максимальную длину строки. После того как все
данные будут прочитаны, ширина экрана делится на длину самой большой входной
записи - результат равен ожидаемому количеству столбцов. Затем программа
входит в цикл, который выполняется для каждой входной записи. Однако порядок
вывода неочевиден. Предположим, имеется список из девяти элементов:
> Смотри также -------------------------------
4.19. Программа: permuteПроблемаВам никогда не требовалось сгенерировать все возможные перестановки массива или выполнить некоторый фрагмент для всех возможных перестановок? Например: % echo man bites dog | permute dog bites man bites dog man dog man bites man dog bites bites man dog man bites dog Количество возможных перестановок для множества равно факториалу числа элементов в этом множестве. Оно растет чрезвычайно быстро, поэтому не стоит генерировать перестановки для большого числа элементов:Размер множества Количество перестановок
Соответственно, выполнение операции для всех возможных перестановок занимает много времени. Сложность факториальных алгоритмов превышает количество частиц во Вселенной даже для относительно небольших входных значений. Факториал 500 больше, чем десять в тысячной степени! use Math::BigInt;
Два решения, приведенных ниже, отличаются порядком возвращаемых перестановок. Решение из примера 4.3 использует классический алгоритм списковых перестановок, используемый знатоками Lisp. Алгоритм относительно прямолинеен, однако в нем создаются ненужные копии. Кроме того, в решении жестко закодирован простой вывод перестановок без каких-либо дополнительных действий. Пример 4.3. tdc-permute
Решение из примера 4.4, предложенное Марком-Джейсоном Доминусом (Mark-Jason Dominus), более элегантно н работает примерно на 25 % быстрее. Вместо того чтобы рассчитывать все перестановки, программа генерирует н-ю конкретную перестановку. Элегантность проявляется в двух аспектах. Во-первых, в программе удается избежать рекурсии, кроме как при вычислении факториала (который алгоритмом перестановок обычно не используется). Во-вторых, вместо перестановки реальных данных генерируется перестановка целых чисел. В программе для экономии времени использована методика запоминания. Ее суть заключается в том, что функция, которая всегда возвращает конкретный ответ для конкретного набора аргументов, запоминает этот ответ. При следующем вызове с теми же аргументами дальнейшие вычисления уже не потребуются. Функция factorial сохраняет ранее вычисленные значения факториала в закрытом массиве @fact ( 10.3). Функция n2perm вызывается с двумя аргументами: номером генерируемой перестановки (от 0 до N!, где N - размер массива) и индексом последнего элемента массива. Функция n2perm для расчета шаблона перестановки вызывает нодпр01Т)ам-му n2pat. Затем шаблон преобразуется в перестановку целых чисел подпрограммой pat2perm. Шаблон представляет собой список вида (02010), что означает: "Вырезать нулевой элемент, затем второй элемент оставшегося списка, затем нулевой, первый и снова нулевой". Пример 4.4. mjd-permute
#!/usr/bin/perl -w
> Смотри также ---------------------
|