Требуется создать циклический список и организовать работу с ним.
Решение
Воспользуйтесь функциями unshift и pop (или push и shift) для обычного массива.
unshift(@circular, pop(@circular)); # Последний становится первым
push (@circular, shift(@circular)); # И наоборот
Комментарий
Циклические списки обычно применяются для многократного выполнения одной и той же последовательности действий - например, обработки подключений к серверу. Приведенный выше фрагмент не является полноценной компьютерной реализацией циклических списков с ука
sub grab_and_rotate (\@ ) {
my $listref = shift;
my $element = $listref->[0];
push(@listref, shift @>$listref);
return $element;
}
@processes =(1,2, 3, 4, 5 );
while (1) {
$process = grab_and_rotate(@)processes);
print "Handling process $process\n";
sleep 1;
}
> Смотри также --------------------------------
Описание функций unshift и push в perlfunc(1); рецепт 13.13.
Требуется случайным образом переставить элементы массива. Наиболее очевидное применение - тасование колоды в карточной игре, однако аналогичная задача возникает в любой ситуации, где элементы массива обрабатываются в произвольном порядке.
Решение
Каждый элемент массива меняется местом с другим, случайно выбранным элементом:
# fisher_yates_shuffle ( \@аггау ) : генерация случайной перестановки
# массива @аггау на месте sub fisher_yates_shuffle { my $array = shift;
my $i;
for ($i = @$array; --$i; ) { my $j = int rand ($i+1);
next if $i == $j;
@$array[$i,$j] = @$array[$j,$i], }
}
fisher_yates_shuffle( \@array ); # Перестановка массива @array на месте Или выберите случайную перестановку, воспользовавшись кодом из примера 4.4:
Случайные перестановки на удивление коварны. Написать плохую программу перестановки очень просто:
sub naive_shuffle { # Не делайте так!
for (my $i = 0; $i < @_; $i++) {
my $j = int rand @_; # Выбрать случайный элемент
($_[$!], $_[$j]) = ($_[$Л, $_[$!]); # Поменять местами
}
}
Такой алгоритм является смещенным - одни перестановки имеют большую вероятность, чем другие. Это нетрудно доказать: предположим, мы получили список из 3 элементов. Мы генерируем 3 случайных числа, каждое из которых может принимать 3 возможных знач
В приведенном выше алгоритме Фишера-Йетса это смещение устраняется за счет изменения интервала выбираемых случайных чисел.
> Смотри также --------------------------------
Описание функции rand в perlfunc(1). Дополнительная информация о случайных числах приведена в Рецептах 2.7-2.9. В рецепте 4.19 показан другой способ построения случайных перестановок.
Вас когда-нибудь интересовало, каким образом программы типа Is строят столбцы отсортированных выходных данных, расположенных но столбцам, а не по строкам? Например:
awk cp ed login mount rmdir sum
basename csh egrep Is mt sed sync
cat date fgrep mail mv sh tar
chgrp dd gr-ep mkdir ps sort touch
chmod df kill mknod pwd stty vi
chown echo In more rm su
Наиболее очевидный способ вывести отсортированный список по столбцам - последовательно выводить каждый элемент списка, выравнивая его пробелами до определенной ширины. Когда вывод достигает конца строки, происходит переход на следующую строку. Но
Программа words представляет собой фильтр, который генерирует выходные данные по столбцам. Она читает все входные данные и запоминает максимальную длину строки. После того как все данные будут прочитаны, ширина экрана делится на длину самой большой входно
Затем программа входит в цикл, который выполняется для каждой входной записи. Однако порядок вывода неочевиден. Предположим, имеется список из девяти элементов:
Неправильно Правильно
123 147
456 258
789 369
Программа words производит все необходимые вычисления, чтобы элементы (1,4,7) выводились в одной строке, (2,5,8) - в другой и (3,6,9) - в последней строке.
Текущие размеры окна определяются вызовом ioctl. Этот вариант прекрасно работает - в той системе, для которой он был написан. В любой другой он не подойдет. Если вас это устраивает, хорошо. В рецепте 12.14 показано, как определить размер окна в вашей сист
> Смотри также -------------------------------
Рецепт 15.4.
Вам никогда не требовалось сгенерировать все возможные перестановки массива или выполнить некоторый фрагмент для всех возможных перестановок? Например:
% 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;
sub factorial {
my $n = shift;
my $s = 1;
$s *= $n-while $n > 0;
return $s;
}
print factorial(Math::BigInt->new("500"));
+1220136...(1035 digits total)
Два решения, приведенных ниже, отличаются порядком возвращаемых перестановок.
Решение из примера 4.3 использует классический алгоритм списковых перестановок, используемый знатоками Lisp. Алгоритм относительно прямолинеен, однако в нем создаются ненужные копии. Кроме того, в решении жестко закодирован простой вывод перестановок без
Решение из примера 4.4, предложенное Марком-Джейсоном Доминусом (Mark-Jason Dominus), более элегантно н работает примерно на 25 % быстрее. Вместо того чтобы рассчитывать все перестановки, программа генерирует н-ю конкретную перестановку. Элегантно
В программе для экономии времени использована методика запоминания. Ее суть заключается в том, что функция, которая всегда возвращает конкретный ответ для конкретного набора аргументов, запоминает этот ответ. При следующем вызове с теми же аргументами дал
Функция n2perm вызывается с двумя аргументами: номером генерируемой перестановки (от 0 до N!, где N - размер массива) и индексом последнего элемента массива. Функция n2perm для расчета шаблона перестановки вызывает нодпр01Т)ам-му n2pat. Затем шаблон преоб
Пример 4.4. mjd-permute
#!/usr/bin/perl -w
# mjd_permute: перестановка всех введенных слов
use strict;
while (о) {
my @>data = split;
my $num_permutations = factorial(scalar @data);
for (my $i=0; $i < $num_permutations; $i++) {
my (Spermutation = @data[n2perm($i, $ftdata)];
print "@permutation\n";
}
} # Вспомогательная функция: факториал с запоминанием
BEGIN { my Of act = (1);
sub factorial($) { my $n = shift;
return $fact[$n] if defined $fact[$n];
$fact[$n] = $n * factorial($n - 1);
}
}
# n2pat($N, $len) : построить $N-H шаблон перестановки длины $1еп sub n2pat {
my $i =1;
my $N = shift;
my $len = shift;
my (Spat;
while ($i <= $len + 1) { # На самом деле просто
while ($N) 'o push @)pat, $N % $i;
$N = int($N/$i);
$i++:
}
return @pat;
}
# pat2perm(@pat) : превратить шаблон, возвращаемый n2pat(),
# в перестановку целых чисел. sub pat2perm {
my @pat = @_;
my @source = (0 .. $#pat);
my @perm;
push @perm, splice(@source, (pop @pat), 1) while @>pat;
return @perm;
}
# n2perm($N, $len) : сгенерировать N-ю перестановку S объектов sub n2perm {
pat2perm(n2pat(@_));
}
> Смотри также ---------------------
Описание функций unshlft и splice в perlfunc(1); рецепты 2.7; 10.3.
