嘿大家好,让我们在 Raku 中实现一些算法。
第一个将是经典的冒泡排序。实质上,您从左到右扫描数据并交换两个相邻的项(如果它们尚未正确排序)。重复这个过程,直到整个数据列表被排序。
这是最初的直接实现:
sub bubble-sort(@data) {
my Bool $done = False;
while !$done {
$done = True;
for 1 .. @data.elems - 1 -> $n {
if @data[$n - 1] > @data[$n] {
(@data[$n - 1], @data[$n]) =
(@data[$n], @data[$n - 1]);
$done = False;
}
}
}
}
my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
bubble-sort @data;
say @data;
此实现执行就地排序,但您不需要将函数参数声明为 is rw
。实际上,编译器会告诉您这是多余的,并将停止进一步编译:
For parameter '@data', '@' sigil containers don't need 'is rw' to be writable
Can only use 'is rw' on a scalar ('$' sigil) parameter, not '@data'
另一个我想更精确地看一下的地方是交换两个数组元素:
(@data[$n - 1], @data[$n]) = (@data[$n], @data[$n - 1]);
现在,随着程序准备就绪,我们可以确认它是否正常工作,让我们对其进行转换以使其更具表现力(尽管效率可能稍低)。
$ raku bubble-sort.pl6
[1 1 2 2 4 5 7 9 10 46 78]
第一步是简化交换代码。在等号的两边,我们使用相同的两个元素,索引 $n
和 $n - 1
。可以在两个元素的列表上调用 reverse
方法并将其赋值给它:
(@data[$n - 1], @data[$n]).=reverse;
使用数组切片可以进一步简化:
@data[$n - 1, $n].=reverse;
如您所见,不再需要括号。你必须自己回答的唯一问题是,是否用空格包围 .=
运算符。一方面,这是一个方法调用(因此,没有空格),另一方面,它是一个赋值(因此,空格)。
好的,下一步是什么?当然,if
语句可以写为后缀条件,但 if
块中有两行代码。在这一点上,我可以决定在代码之美和效率之间进行权衡,并摆脱布尔 $done
标志。
sub bubble-sort(@data) {
for 1 .. @data.elems - 1 -> $n {
if @data[$n - 1] > @data[$n] {
@data[$n - 1, $n].=reverse;
}
}
bubble-sort(@data) unless [<=] @data;
}
此步骤还允许删除 while
块。在函数结束时,完成递归调用(再次,可能效率较低,但是谁在乎),并且检查数组是否已经排序的条件现在是显式的:
unless [<=] @data
毕竟,现在可以附加 if
后缀:
@data[$n - 1, $n].=reverse if @data[$n - 1] > @data[$n]
甚至 for
后缀:
@data[$_ - 1, $_].=reverse
if @data[$_ - 1] > @data[$_]
for 1 .. @data.elems - 1;
另外,为什么不像使用函数的其他部分那样使用切片和简化运算符来创建条件:
@data[$_ - 1, $_].=reverse
if [>] @data[$_ - 1, $_]
for 1 .. @data.elems - 1;
下一步是减小范围 1 .. @ data.elems - 1
,这是可行的,但包含的元素太多,可以删除。 -1
部分可以用开口范围代替:
for 1 ..^ @data.elems;
之后 elems
调用就不需要了,Raku 可以为我们做到这一点:
for 1 ..^ @data;
这是代码的当前状态:
sub bubble-sort(@data) {
@data[$_ - 1, $_] .= reverse
if [>] @data[$_ - 1, $_]
for 1 ..^ @data;
bubble-sort(@data) unless [<=] @data;
}
my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
bubble-sort @data;
say @data;
在我们暂停之前,下面是另一种可能的修改。通常,Raku 中的递归可以通过 multi-subs 实现。让编译器根据数据完成工作,而不是在函数内部进行分支:
multi sub bubble-sort(@data where [<=] @data) {}
multi sub bubble-sort(@data where ![<=] @data) {
@data[$_ - 1, $_] .= reverse
if [>] @data[$_ - 1, $_]
for 1 ..^ @data;
bubble-sort(@data);
}
如果您不喜欢 [<=]
检查(因为它应该扫描整个列表),这里是一个带有另一个循环层的暴力版本:
sub bubble-sort(@data) {
for ^@data {
@data[$_ - 1, $_] .= reverse
if [>] @data[$_ - 1, $_] for 1 ..^ @data;
}
}
可以使用交叉运算符连接两个 for
循环:
sub bubble-sort(@data) {
for ^@data X 1 ..^ @data {
my $n = $_[1];
@data[$n - 1, $n] .= reverse if [>] @data[$n - 1, $n];
}
}
我们邀请您进一步处理此代码。我真的好奇是否以及如何做得更短(例如,如何重用切片)。
GitHub 上提供了上述程序的源代码。
原文: https://raku.online/2019/06/21/100-bubble-sort-in-perl-6/