Perl编程中的实用技巧与算法实现

### Perl 编程中的实用技巧与算法实现 #### 1. 累积求和函数 在 Perl 中，我们可以实现一个累积求和的函数。以下是一个普通的实现方式： ```perl my @numbers = <2 5 7 6 5 3 6 8>; say cumul-sum(@numbers); # -> [2 7 14 20 25 28 34 42] sub cumul-sum (@array) { my @cumulative; my $partial_sum = 0; for @array -> $element { $partial_sum += $element; push @cumulative, $partial_sum; } return @cumulative; } ``` 不过，使用函数式编程可以让代码更简洁。利用归约元运算符可以得到部分结果的列表： ```perl my @numbers = <2 5 7 6 5 3 6 8>; say [\+] @numbers; # -> (2 7 14 20 25 28 34 42) ``` #### 2. 数组操作练习 - **Exercise 9 - 3: Middle**：生成一个不包含给定列表首尾元素的新列表，最简单的方法是使用切片： ```perl say middle(5..10); # -> (6 7 8 9) sub middle (@array) { return @array[1..*-2] } ``` 这里`*-1`表示数组最后一个元素的索引，为了丢弃最后一个元素，我们将范围限制为`*-2`。 - **Exercise 9 - 4: Chop**：与上一个练习的基本区别是，数组应该在原地修改，而不是从函数中返回。以下是两种实现方式： ```perl # 方法一：使用 shift 和 pop 函数 my @nums = 5..10; chop-it(@nums); say @nums; # -> [6 7 8 9] sub chop-it (@array) { shift @array; pop @array; return; } # 方法二：使用切片 sub chop-it (@array) { @array = @array[1..*-2]; return; } ``` #### 3. 列表排序检查 - **Exercise 9 - 5: Subroutine is - sorted**：检查列表是否已排序，有几种不同的实现方式： ```perl # 方法一：迭代比较 sub is-sorted (@array) { my $previous = @array[0]; for @array -> $current { return False if $current < $previous; $previous = $current; } return True; } # 方法二：与排序后的列表比较 sub is-sorted (@array) { return @array eqv @array.sort; } # 方法三：使用函数式编程 sub is-sorted (@array) { return [<=] @array; } ``` 方法三使用函数式编程，代码更短，且不会产生额外排序的成本，还能实现短路操作，一旦发现值的顺序不正确就会返回`False`。 #### 4. 变位词检查 - **Exercise 9 - 6: Subroutine is - anagram**：检查两个单词是否为变位词，先判断长度是否相同，然后对字母排序后进行比较： ```perl sub is-anagram (Str $word1, Str $word2) { return False if $word1.chars != $word2.chars; return False if $word1.comb.sort ne $word2.comb.sort; True; } # 更简洁的写法 sub is-anagram (Str $word1, Str $word2) { return $word1.comb.sort eq $word2.comb.sort; } ``` #### 5. 列表重复元素检查 - **Exercise 9 - 7: Subroutine has - duplicates**：有几种方法可以检查列表中是否有重复元素： ```perl # 方法一：排序后比较相邻元素 sub has-duplicates (@array) { my @sorted = sort @array; for [email protected] -> $i { return True if @sorted[$i] eq @sorted[$i - 1]; } False; } # 方法二：迭代排序后的元素并记录前一个元素 sub has-duplicates (@array) { my @sorted = sort @array; my $previous = shift @sorted; for @sorted -> $item { return True if $item eq $previous; $previous = $item; } False; } # 方法三：使用 unique 函数 sub has-duplicates (@array) { my @unique-items = unique @array; return False if @unique-items.elems == @array.elems; True; } # 更简洁的写法 sub has-duplicates (@array) { @array.unique.elems != @array.elems; } # 方法四：使用 repeated 函数 sub has-duplicates (@array) { [email protected] } ``` #### 6. 生日悖论模拟 - **Exercise 9 - 8: Simulating the Birthday Paradox**：模拟生日悖论，需要生成 1 到 365 之间的随机整数（为了简单起见，生成 0 到 364 之间的随机整数），并运行 1000 次模拟： ```perl sub has-duplicates (@array) { return [email protected] } sub check-birthdays (Int $num-students) { my @blist; for 1..$num-students { push @blist, 365.rand.Int; # random numbers between 0 and 364 } return has-duplicates(@blist); } my $dupl-count = 0; my $nb-tests = 1000; for 1..$nb-tests { $dupl-count++ if check-birthdays 23; # 23 students } say "On $nb-tests tests, $dupl-count had at least one duplicate birthday"; ``` 使用`roll`函数可以让`check - birthdays`子例程更简洁： ```perl sub check-birthdays (Int $num-students) { has-duplicates( (^365).roll($num-students) ) } ``` #### 7. 数组填充性能比较 - **Exercise 9 - 9: Comparing push and unshift**：比较使用`push`和`unshift`填充数组的运行时间： ```perl my $start_push = now; my @push_array; for 'words.txt'.IO.lines -> $line { push @push_array, $line; } say "push took " ~ now - $start_push ~ " seconds."; @push_array = (); my $start_unsh = now; my @unsh_array; for 'words.txt'.IO.lines -> $line { unshift @unsh_array, $line; } say "unshift took " ~ now - $start_unsh ~ " seconds."; ``` 通常`push`比`unshift`更快，因为`unshift`在数组开头插入元素时，Perl 需要多次移动数据来重新组织整个数组，而`push`在数组末尾插入元素则需要较少的内部管理。如果只是将输入文件的每一行插入数组而不做任何更改，直接将数据读入数组会更简单、更快： ```perl my $start_slurp = now; my @slurp_array = 'words.txt'.IO.lines; say "slurp took " ~ now - $start_slurp ~ " seconds."; ``` #### 8. 二分查找 - **Exercise 9 - 10: Bisection Search in a List**：以下是递归二分查找算法的实现： ```perl sub bisect (@word_list, Str $word) { my $index = (@word_list.elems / 2).Int; return False if $index == 0 and @word_list[$index] ne $word; my $found = @word_list[$index]; if $word lt $found { # search the first half return bisect @word_list[0..$index-1], $word; } elsif $word gt $found { # search the second half return bisect @word_list[$index+1..*-1], $word; } True; # if we get there, we've found the word } ``` 不过这个实现有一些弱点，每次递归调用时会传递一个可能很大的数组，在内存使用和 CPU 周期方面可能效率不高，并且不知道目标单词在原数组中的下标。更好的方法是利用 Perl 6 中子例程是闭包的特性： ```perl sub bisect (Str $word, @word_list) { ```