4.16. Реализация циклических списков 143

Компактная конструкция map/sort/map больше напоминает программирование на Lisp и Scheme, нежели обычное наследие Perl - С и awk. Впервые она была предложена Рэндалом Шварцем (Randal Schwartz) и потому часто называется «преобразованием Шварца».

t> Смотри также-

Описание функции sort в perlfunc(\y, описание операторов стр и <=> врег1ор({у, рецепт 4.14.

4.16. Реализация циклических списков

Проблема

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

Решение

Воспользуйтесь функциями unshift и pop (или push и shift) для обычного массива.

unshift(@circular, pop(@circular)), # Последний становится первым push (©circular, shift(@circular)), # И наоборот

Комментарий

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

sub grab and rotate (\@ ) { my Slistref = shift, my Selement = $listref->[0], push(@listref, shift ©Slistref), return Selement;

©processes =(1,2, 3, 4, 5 ), while (1) (

Sprocess = grab and rotate(@processes),

print Handling process Sprocess\n",

sleep 1,

t> Смотри также-

Описание функций unshift и push в perlfunc{\); рецепт 13.13.

4.17. Случайная перестановка элементов массива

Проблема

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

Решение

Каждый элемент массива меняется местом с другим, случайно выбранным элементом:

# fisher yates shuff1е ( \@array ) генерация случайной перестановки S массива @аггау на месте sub fisher yates shuffie {

my $array = shift,

my $1,

for ($1 = @$array, --$i, ) { my $j = int rand ($i+1), next If $1 == $], @$array[$i,$j] = @$array[$j,$i],

fisher yates shuffle( \@array ), ft Перестановка массива ©array на месте

Или выберите случайную переста1ювку, воспользовавшись кодом из примера 4.4:

Spermutations = factoriaK scalar ©array ),

©shuffle = ©array [ n2perm( 1+int(rand Spermutations), $#array) ],

Комментарий

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

sub naive shuffle { # Не делайте так

for (my $1 =0, $1 < © , $1++) (

my $j = int rand © , # Выбрать случайный элемент

($ [$i], $ [$j]) = ($ [$j], $ [$i]), n Поменять местами

Такой алгоритм является смещенным - одни перестановки имеют бо;шшую вероятность, чем другие. Это нетрудно доказать: предположим, мы получили список из 3 элементов. Мы генерируем 3 случайных числа, каждое из которых может принимать 3 возможных значения - итого 27 возможных комбинаций. Однако для списка из трех элементов существует всего 6 перестановок. Поскольку 27 не делится на 6, некоторые перестановки появляются с большей вероятностью, чем другие.

В примере 4.2 показано, как это делается. Пример 4.2. words

#/usr/bin/perl -w

# words - вывод данных no столбцам

use strict,

my ($item, $cols, $rows, Smaxlen), my (Sxpixel, $ypixel, $mask, @data),

getwinsizeO,

# Получить все строки входных данных

# и запомнить максимальную длину строки Smaxlen = 1,

while (о) { my Smylen, s/\s+S ,

Smaxlen = Smylen if ((Smylen = length) > Smaxlen) push(@data, S ),

Smaxlen += 1,

# Дополнительный пробел

# Определить границы экрана Scols = int($cols / Smaxlen)

В приведенном выше алгоритме Фишера-Йетса это смещение устраняется за счет изменения интервала выбираемых случайных чисел.

[> Смотри также-

Описание функции rand в peiljunc{\). Дополнительная информация о случайных числах приведена в Рецептах 2.7-2.9. В рецепте 4.19 показан другой способ построения случайных перестановок.

4.18. Программа: words

Описание

Вас когда-нибудь интересовало, каким образом программы типа /5 строят столбцы отсортированных выходных данных, расположенных по столбцам, а не по строкам? Например: