Raku 慢混合排序
Raku slow Mixes sorting
更新
在同一台计算机上，使用 Rakudo 编译器“rakudo-moar-2021.06-01-macos-x86_64-clang.tar”与时间相比，我得到 3-10 倍 speed-ups我的计算原来是post.
.elems: 100000
.head(3): (id.20444 => 81.95246687507492 id.81745 => 34.859323339828464 id.79973 => 97.33816856420829)
time of .sort({-$_.value}) : 0.764283216
time of .sort(-*.value) : 0.618963783
time of .sort.reverse : 0.584477656
time of .values.sort : 1.68912663
请注意，这些时序接近于 R 时序。因此，在这些类型的计算上，Raku 具有我期望的性能。
原版post
我最近观看了 Elizabeth Mattijsen 的 FOSDEM 演示，标题为
"Raku - Sets without Borders"
并决定在我的一些计算工作流程中采用 Raku Mix objects。
我注意到 Mix object 的排序（成对）非常慢——我会说比我预期的慢 100 到 1000 倍。请参阅下面的 Raku 代码和输出。 （我也在同一台电脑上提供了相关的R代码和输出。）
这种缓慢是预期的吗？有没有解决方法可以加快计算速度？
（更具体地说，我对快速 reverse-sort 和快速检索 Mix 中最大的 top-K 元素感兴趣。）
（时间是几年前的 Mac Book Pro，Mac OS 10.15.7，使用最新的 Rakudo 编译器“rakudo-moar-2021.02。1-01-macos-x86_64-clang.tar.gz" .)
乐
#!/usr/bin/env perl6
my @words = Array(1 .. 100_000).map({ 'id.' ~ $_.Str });
my $m0 = Mix(@words.map({ $_ => 100.rand() }));
say '.elems: ', $m0.elems;
say '.head(3): ', $m0.head(3);
my $start = now;
my $m1 = $m0.sort({-$_.value});
say 'time of .sort({-$_.value}): ', now - $start;
$start = now;
my $m2 = $m0.sort(-*.value);
say 'time of .sort(-*.value) : ', now - $start;
$start = now;
my $m3 = $m0.sort.reverse;
say 'time of .sort.reverse : ', now - $start;
$start = now;
my $m4 = $m0.values.sort;
say 'time of .values.sort : ', now - $start;
# .elems: 100000
# .head(3): (id.96239 => 87.89629474533156 id.89110 => 11.661698290245525 id.24795 => # 64.80528155838671)
# time of .sort({-$_.value}): 3.64936396
# time of .sort(-*.value) : 4.0388654
# time of .sort.reverse : 4.5783556
# time of .values.sort : 4.3461059
R
这是R中类似的数据和排序代码：
words <- paste0( 'id.', 1:100000)
m <- setNames( runif(n = length(words), min = 0, max = 100), words)
cat( "length(m) : ", length(m), "\n")
cat( "m[1:3]:\n"); print(m[1:3]); cat("\n")
cat( "system.time( sort(m) ) : ", system.time( sort(m) ), "\n")
cat( "system.time( m[order(-m)] ) : ", system.time( m[order(-m)] ), "\n")
cat( "system.time( rev(sort(names(m))) ) : ", system.time( rev(sort(names(m))) ), "\n")
# length(m) : 100000
# m[1:3]:
# id.1 id.2 id.3
# 89.99714 54.31701 11.57415
#
# system.time( sort(m) ) : 0.011 0 0.011 0 0
# system.time( m[order(-m)] ) : 0.011 0 0.011 0 0
# system.time( rev(sort(names(m))) ) : 0.298 0.001 0.3 0 0
以下是@raith 对问题的回答：
"R代码中的m是否可变？"
不，R object 大部分是不可变的。
“sort(m) 是构建一个新的数据结构，还是只是对现有 m 结构的一个新索引？”
创建了一个新的数据结构。 R 是 LISP 的后代，因此它在精神上主要遵循函数式编程范式。
“m[order(-m)] 的相同问题？”
order(-m) 给出一个（索引的）整数向量。该索引向量用于将 m 的元素检索到新的 object.
“然后 rev(sort(names(m)))？”
names(m) 获取 m 元素的“键”。这些键被排序并放入一个字符向量中，然后该字符向量被反转。 （即创建了一个新的 object。）
“大概只建立一个索引可能会快得多。也许 Raku 可以为元组提供一个排序变体，它产生一个依赖于
那种方法？
我想我不适合对此发表评论，但我想提一下：
- Julia——也是 LISP 的后代——对其数据结构做了类似的事情。 Julia 的创建者和开发者声称，一般来说，比 R 和 Mathematica 快（多）。 （这是用于数学计算的其他 LISP 后代。）
- 我更喜欢并期望函数式范式风格的 Raku 代码很快。
更新的 R 基准测试
一些人要求更详细的 R 基准测试：
library(microbenchmark)
set.seed(32)
words <- paste0( 'id.', 1:100000)
m <- setNames( runif(n = length(words), min = 0, max = 100), words)
cat( "length(m): ", length(m), "\n")
cat( "m[1:3]:\n"); print(m[1:3]); cat("\n")
microbenchmark::microbenchmark(
sort(m, decreasing = T),
sort(-m),
m[order(-m)],
rev(sort(m)),
rev(sort(names(m))),
unit = "s", times = 100
)
# length(m) : 100000
#
# m[1:3]:
# id.1 id.2 id.3
# 50.58405 59.48084 80.87471
#
# Unit: seconds
# expr min lq mean median uq max neval cld
# sort(m, decreasing = T) 0.006246853 0.007789205 0.009215613 0.008263348 0.009002414 0.02450786 100 a
# sort(-m) 0.006857755 0.008376058 0.010292145 0.008939605 0.010069702 0.02469324 100 a
# m[order(-m)] 0.006658089 0.008257555 0.009726704 0.008718414 0.009811200 0.02294023 100 a
# rev(sort(m)) 0.008975013 0.010939122 0.014965756 0.011692480 0.012571979 0.22022085 100 b
# rev(sort(names(m))) 0.256036106 0.268526455 0.278385866 0.277794917 0.288586351 0.31160492 100 c
#
[编辑 2021-03-06：由于过去 ~ 天的一系列提交（谢谢 Liz！），这种放缓现在主要集中在 HEAD;这些性能提升应该会在下个月的发布中体现出来。我将下面的答案作为如何深入研究此类问题的示例，但它诊断出的具体问题已基本解决。]
基于@Elizabeth Mattijsen 的评论：这里的缓慢性能主要是 由于 Rakudo 编译器未正确优化生成的代码（截至 2021 年 3 月 5 日）。随着编译器的不断改进，您上面编写的（惯用的）代码应该会表现得更好。
但是，今天我们可以使用一些解决方法来加快此计算。虽然 Raku 的性能在这方面确实不会与 R 相比特别有竞争力，但一些分析驱动的重构可以使这段代码几乎 快一个数量级。
我们是这样做的：
首先，我们从分析代码开始。如果您 运行 您的脚本带有 raku --profile=<filename>，那么您将获得一个写入 <filename> 的配置文件。默认情况下，这将是一个 HTML 文件，允许您在浏览器中查看配置文件。然而，我的偏好是指定一个 .sql 扩展，它生成一个 SQL 配置文件。然后我查看此配置文件 MoarProf, the revised profiler that Timo Paulssen is building.
查看此配置文件恰好显示了 Liz 提到的问题：应该内联的调用没有。为了解决这个问题，让我们创建自己的排序函数，JIT 编译器会很乐意对其进行优化：
sub my-reverse($a, $b) {
$a.value > $b.value ?? Order::Less !! Order::More
}
使用此功能（使用 $m0.sort(&my-reverse)）可立即将 运行 时间减少 25%，但仍然太高了。返回分析器！
接下来让我突然想到的是，我们对 Bool 的调用仍然太多。特别是，Rakudo 目前似乎正在将 Ordering 转换为 Bool。我认为这是一个错误，并计划在发布后进行调查，但无论如何，我们可以节省 Rakudo 的精力：
sub my-reverse1($a, $b) {
$a.value > $b.value ?? False !! True
}
在我的机器上，这再次将执行时间缩短了一半，使我们达到了 .sort({-$_.value}) 原始 运行 时间的 ~28%。这越来越不错了，将是一个停下来的好地方。
不过，让我们继续：再次检查探查器表明我们仍然将大量时间用于调用 Bool（即使我们调用的频率是原来的一半）。目前要解决此问题，我们需要下拉到 NQP 来比较数字，而无需构建 Bool:
sub nqp-reverse($a, $b) {
use nqp;
nqp::isge_n($a.value, $b.value) ?? False !! True
}
这又将我们的执行时间缩短了一半，让我们达到了我想要的 Raku 性能。
这是我得到的计时结果，包括我添加的函数和您问题中的函数，报告格式与您使用的格式相同：
.elems: 100000
.head(3): (id.195 => 80.81458886131459 id.31126 => 84.25690944480021 id.60237 => 45.63311676798485)
time of .sort(&nqp-reverse): 0.3226533
time of .sort(&my-reverse1): 0.76803384
time of .sort(&my-reverse) : 1.4643238
time of .sort({-$_.value}) : 2.6780952
time of .sort(-*.value) : 1.8549689
time of .sort.reverse : 2.5862973
time of .values.sort : 2.078715
与.sort进行比较的方式存在缺陷，导致大量调用Mu.Bool方法，在某些情况下会占[的50%左右。 =16=]用过。今天，我更改了 .sort 的非标准比较处理方式，不再调用 Mu.Bool。这导致问题的代码 运行 比以前快 2 倍，尽管 @codesections 报告速度提高了 4 倍。这应该在2020.03版本中。
顺便提一下，有一些乐语成语可以精简一点...
my @words = Array(1 .. 100_000).map({ 'id.' ~ $_.Str });
my $m0 = Mix(@words.map({ $_ => 100.rand() }));
至
my $m0 = .map(* => 100.rand).Mix given 'id.' X~ 1..100_000;
这使用 'given' formulation and the X metaoperator 和 '~' 字符串连接。
更新
在同一台计算机上，使用 Rakudo 编译器“rakudo-moar-2021.06-01-macos-x86_64-clang.tar”与时间相比，我得到 3-10 倍 speed-ups我的计算原来是post.
.elems: 100000
.head(3): (id.20444 => 81.95246687507492 id.81745 => 34.859323339828464 id.79973 => 97.33816856420829)
time of .sort({-$_.value}) : 0.764283216
time of .sort(-*.value) : 0.618963783
time of .sort.reverse : 0.584477656
time of .values.sort : 1.68912663
请注意，这些时序接近于 R 时序。因此，在这些类型的计算上，Raku 具有我期望的性能。
原版post
我最近观看了 Elizabeth Mattijsen 的 FOSDEM 演示，标题为
"Raku - Sets without Borders"
并决定在我的一些计算工作流程中采用 Raku Mix objects。
我注意到 Mix object 的排序（成对）非常慢——我会说比我预期的慢 100 到 1000 倍。请参阅下面的 Raku 代码和输出。 （我也在同一台电脑上提供了相关的R代码和输出。）
这种缓慢是预期的吗？有没有解决方法可以加快计算速度？
（更具体地说，我对快速 reverse-sort 和快速检索 Mix 中最大的 top-K 元素感兴趣。）
（时间是几年前的 Mac Book Pro，Mac OS 10.15.7，使用最新的 Rakudo 编译器“rakudo-moar-2021.02。1-01-macos-x86_64-clang.tar.gz" .)
乐
#!/usr/bin/env perl6
my @words = Array(1 .. 100_000).map({ 'id.' ~ $_.Str });
my $m0 = Mix(@words.map({ $_ => 100.rand() }));
say '.elems: ', $m0.elems;
say '.head(3): ', $m0.head(3);
my $start = now;
my $m1 = $m0.sort({-$_.value});
say 'time of .sort({-$_.value}): ', now - $start;
$start = now;
my $m2 = $m0.sort(-*.value);
say 'time of .sort(-*.value) : ', now - $start;
$start = now;
my $m3 = $m0.sort.reverse;
say 'time of .sort.reverse : ', now - $start;
$start = now;
my $m4 = $m0.values.sort;
say 'time of .values.sort : ', now - $start;
# .elems: 100000
# .head(3): (id.96239 => 87.89629474533156 id.89110 => 11.661698290245525 id.24795 => # 64.80528155838671)
# time of .sort({-$_.value}): 3.64936396
# time of .sort(-*.value) : 4.0388654
# time of .sort.reverse : 4.5783556
# time of .values.sort : 4.3461059
R
这是R中类似的数据和排序代码：
words <- paste0( 'id.', 1:100000)
m <- setNames( runif(n = length(words), min = 0, max = 100), words)
cat( "length(m) : ", length(m), "\n")
cat( "m[1:3]:\n"); print(m[1:3]); cat("\n")
cat( "system.time( sort(m) ) : ", system.time( sort(m) ), "\n")
cat( "system.time( m[order(-m)] ) : ", system.time( m[order(-m)] ), "\n")
cat( "system.time( rev(sort(names(m))) ) : ", system.time( rev(sort(names(m))) ), "\n")
# length(m) : 100000
# m[1:3]:
# id.1 id.2 id.3
# 89.99714 54.31701 11.57415
#
# system.time( sort(m) ) : 0.011 0 0.011 0 0
# system.time( m[order(-m)] ) : 0.011 0 0.011 0 0
# system.time( rev(sort(names(m))) ) : 0.298 0.001 0.3 0 0
以下是@raith 对问题的回答：
"R代码中的m是否可变？"
不，R object 大部分是不可变的。“sort(m) 是构建一个新的数据结构，还是只是对现有 m 结构的一个新索引？”
创建了一个新的数据结构。 R 是 LISP 的后代，因此它在精神上主要遵循函数式编程范式。“m[order(-m)] 的相同问题？”
order(-m)给出一个（索引的）整数向量。该索引向量用于将m的元素检索到新的 object.“然后 rev(sort(names(m)))？”
names(m)获取m元素的“键”。这些键被排序并放入一个字符向量中，然后该字符向量被反转。 （即创建了一个新的 object。）“大概只建立一个索引可能会快得多。也许 Raku 可以为元组提供一个排序变体，它产生一个依赖于 那种方法？
我想我不适合对此发表评论，但我想提一下：- Julia——也是 LISP 的后代——对其数据结构做了类似的事情。 Julia 的创建者和开发者声称，一般来说，比 R 和 Mathematica 快（多）。 （这是用于数学计算的其他 LISP 后代。）
- 我更喜欢并期望函数式范式风格的 Raku 代码很快。
更新的 R 基准测试
一些人要求更详细的 R 基准测试：
library(microbenchmark)
set.seed(32)
words <- paste0( 'id.', 1:100000)
m <- setNames( runif(n = length(words), min = 0, max = 100), words)
cat( "length(m): ", length(m), "\n")
cat( "m[1:3]:\n"); print(m[1:3]); cat("\n")
microbenchmark::microbenchmark(
sort(m, decreasing = T),
sort(-m),
m[order(-m)],
rev(sort(m)),
rev(sort(names(m))),
unit = "s", times = 100
)
# length(m) : 100000
#
# m[1:3]:
# id.1 id.2 id.3
# 50.58405 59.48084 80.87471
#
# Unit: seconds
# expr min lq mean median uq max neval cld
# sort(m, decreasing = T) 0.006246853 0.007789205 0.009215613 0.008263348 0.009002414 0.02450786 100 a
# sort(-m) 0.006857755 0.008376058 0.010292145 0.008939605 0.010069702 0.02469324 100 a
# m[order(-m)] 0.006658089 0.008257555 0.009726704 0.008718414 0.009811200 0.02294023 100 a
# rev(sort(m)) 0.008975013 0.010939122 0.014965756 0.011692480 0.012571979 0.22022085 100 b
# rev(sort(names(m))) 0.256036106 0.268526455 0.278385866 0.277794917 0.288586351 0.31160492 100 c
#
[编辑 2021-03-06：由于过去 ~ 天的一系列提交（谢谢 Liz！），这种放缓现在主要集中在 HEAD;这些性能提升应该会在下个月的发布中体现出来。我将下面的答案作为如何深入研究此类问题的示例，但它诊断出的具体问题已基本解决。]
基于@Elizabeth Mattijsen 的评论：这里的缓慢性能主要是 由于 Rakudo 编译器未正确优化生成的代码（截至 2021 年 3 月 5 日）。随着编译器的不断改进，您上面编写的（惯用的）代码应该会表现得更好。
但是，今天我们可以使用一些解决方法来加快此计算。虽然 Raku 的性能在这方面确实不会与 R 相比特别有竞争力，但一些分析驱动的重构可以使这段代码几乎 快一个数量级。
我们是这样做的：
首先，我们从分析代码开始。如果您 运行 您的脚本带有 raku --profile=<filename>，那么您将获得一个写入 <filename> 的配置文件。默认情况下，这将是一个 HTML 文件，允许您在浏览器中查看配置文件。然而，我的偏好是指定一个 .sql 扩展，它生成一个 SQL 配置文件。然后我查看此配置文件 MoarProf, the revised profiler that Timo Paulssen is building.
查看此配置文件恰好显示了 Liz 提到的问题：应该内联的调用没有。为了解决这个问题，让我们创建自己的排序函数，JIT 编译器会很乐意对其进行优化：
sub my-reverse($a, $b) {
$a.value > $b.value ?? Order::Less !! Order::More
}
使用此功能（使用 $m0.sort(&my-reverse)）可立即将 运行 时间减少 25%，但仍然太高了。返回分析器！
接下来让我突然想到的是，我们对 Bool 的调用仍然太多。特别是，Rakudo 目前似乎正在将 Ordering 转换为 Bool。我认为这是一个错误，并计划在发布后进行调查，但无论如何，我们可以节省 Rakudo 的精力：
sub my-reverse1($a, $b) {
$a.value > $b.value ?? False !! True
}
在我的机器上，这再次将执行时间缩短了一半，使我们达到了 .sort({-$_.value}) 原始 运行 时间的 ~28%。这越来越不错了，将是一个停下来的好地方。
不过，让我们继续：再次检查探查器表明我们仍然将大量时间用于调用 Bool（即使我们调用的频率是原来的一半）。目前要解决此问题，我们需要下拉到 NQP 来比较数字，而无需构建 Bool:
sub nqp-reverse($a, $b) {
use nqp;
nqp::isge_n($a.value, $b.value) ?? False !! True
}
这又将我们的执行时间缩短了一半，让我们达到了我想要的 Raku 性能。
这是我得到的计时结果，包括我添加的函数和您问题中的函数，报告格式与您使用的格式相同：
.elems: 100000
.head(3): (id.195 => 80.81458886131459 id.31126 => 84.25690944480021 id.60237 => 45.63311676798485)
time of .sort(&nqp-reverse): 0.3226533
time of .sort(&my-reverse1): 0.76803384
time of .sort(&my-reverse) : 1.4643238
time of .sort({-$_.value}) : 2.6780952
time of .sort(-*.value) : 1.8549689
time of .sort.reverse : 2.5862973
time of .values.sort : 2.078715
与.sort进行比较的方式存在缺陷，导致大量调用Mu.Bool方法，在某些情况下会占[的50%左右。 =16=]用过。今天，我更改了 .sort 的非标准比较处理方式，不再调用 Mu.Bool。这导致问题的代码 运行 比以前快 2 倍，尽管 @codesections 报告速度提高了 4 倍。这应该在2020.03版本中。
顺便提一下，有一些乐语成语可以精简一点...
my @words = Array(1 .. 100_000).map({ 'id.' ~ $_.Str });
my $m0 = Mix(@words.map({ $_ => 100.rand() }));
至
my $m0 = .map(* => 100.rand).Mix given 'id.' X~ 1..100_000;
这使用 'given' formulation and the X metaoperator 和 '~' 字符串连接。