这是这个系列的第二部分!请确保你已经阅读过第一部分, 在那里我们讨论了什么是 Seq, 并且怎么来缓存它们。
今天, 我们把 Seq 单独拎出来, 看看里面到底有什么; 是什么驱动的它; 并且怎样让它实现我们的想法。
第二部分: 快速迭代
使 Seq 做事情的主要部分是遵循 Iterator 角色的对象。 这个对象知道如何生成下一个值,什么时候从 Seq 中提取一个值,或者将其所有值推送到某个地方,或者简单地丢弃所有剩余的值。
请记住,当使用 Seq 作为值的来源时,您不需要直接使用 Iterator 的方法。 它们被间接称为各种 Raku 结构。 自己调用这些方法的场景通常是我们制作一个由另一个 Iterator 提供的迭代器的时候,就像我们会看到的那样。
Pull my finger
在最基本的形式中, 一个 Iterator 对象需要提供的只有一个方法: .pull-one
my $seq := Seq.new: class :: does Iterator {
method pull-one {
return $++ if $++ < 4;
IterationEnd
}
}.new;
.say for $seq;
输出:
# OUTPUT:
# 0
# 1
# 2
# 3
上面的例子中, 我们使用 Seq 的 .new
方法创建了一个 Seq
, 该方法需要一个实例化的 Iterator,我们使用一个匿名类来行使 Iterator 角色,并提供一个使用一对匿名状态变量生成4个数字的单个 .pull-one
方法 ,每个调用一个,然后返回 IterationEnd 常量来表示该 Interator 没有任何更多的值产生。
Iterator 协议一旦生成了 IterationEnd 值,就禁止从 Iterator 获取更多的值,所以你的迭代器的方法可能会假定它们永远不会再被调用。
认识其它帮派
Iterator 角色定义了更多的方法,所有这些方法都是可选实现的,其中大部分都有某种默认实现。 额外的方法是为了优化目的,让您根据序列如何迭代来获取快捷方式。
我们来使用 Crypt::Bcrypt 模块(运行 zef install Crypt::Bcrypt 来安装它)构建一个能哈希一堆数据的 Seq。 我们将从提供了 .pull-one
方法的最基本的 Iterator 开始,然后我们将优化它,以在不同的情况下表现更好。
use Crypt::Bcrypt;
sub hash-it (*@stuff) {
Seq.new: class :: does Iterator {
has @.stuff;
method pull-one {
@!stuff ?? bcrypt-hash @!stuff.shift, :15rounds
!! IterationEnd
}
}.new: :@stuff
}
my $hashes := hash-it <foo bar ber>;
for $hashes {
say "Fetched value #{++$} {now - INIT now}";
say "\t$_";
}
# OUTPUT:
# Fetched value #1 2.26035863
# $2b$15$ZspycxXAHoiDpK99YuMWqeXUJX4XZ3cNNzTMwhfF8kEudqli.lSIa
# Fetched value #2 4.49311657
# $2b$15$GiqWNgaaVbHABT6yBh7aAec0r5Vwl4AUPYmDqPlac.pK4RPOUNv1K
# Fetched value #3 6.71103435
# $2b$15$zq0mf6Qv3Xv8oIDp686eYeTixCw1aF9/EqpV/bH2SohbbImXRSati
在上面的例子中, 我们把所有的 Seq 制作原料都包裹在一个叫做 hash-it 的 sub 中。我们吞噬了所有传递给该 sub 的位置参数并使用一个匿名类作为 Iterator 实例化出一个新的 Seq。 我们使用属性 @!stuff
存储我们需要哈希的东西。 在 .pull-one
方法中,我们检查我们是否仍然有 @!stuff
来进行哈希; 如果我们确实有,那么我们就从 @!stuff
中移除一个值,并对它使用哈希算法,使用15个回合来使散列算法花费一些时间。 最后,我们添加了一个 say
语句来测算程序在每次迭代中的运行时间,使用两个 now 调用,其中一个运行 INIT phaser。 从输出中,我们看到哈希单个字符串大约需要 2.2 秒。
不吃早餐
使用 for
循环,不是使用散列例程返回的 Seq
的唯一方法。 如果一些用户不关心前几个哈希怎么办? 例如,他们可以编写一段这样的代码:
my $hash = hash-it(<foo bar ber>).skip(2).head;
say "Made hash {now - INIT now}";
say bcrypt-match 'ber', $hash;
# OUTPUT:
# Made hash 6.6813790
# True
我们已经使用了 Crypt::Bcrypt 模块的 bcrypt-match
来确保我们得到的哈希匹配我们的第三个输入字符串,并且它的确如此,但是看看它输出的时间。光输出单个哈希就花费了 6.7s
。
事实上, 用户要跳过的条目越多, 事情就会变得越来越糟糕。如果用户用 一吨
条目来调用我们的 hash-it
并且尝试跳过前 1,000,000 个元素以在第 1,000,001st 个哈希上获得元素, 它们将会等待大约 25 天以产生单个哈希!!
原因是我们这个基本 Iterator 只知道怎么拉取一个(.pull-one, 所以 skip 操作仍然生成哈希, 然后丢弃它们。因为我们的 Iterator 生成的值不依赖于之前的值, 我们可以实现其中的优化过的方法之一以廉价地跳过迭代。
use Crypt::Bcrypt;
sub hash-it(*@stuff) {
Seq.new: class :: does Iterator {
has @.stuff;
method pull-one {
@!stuff ?? bcrypt-hash @!stuff.shift, :15rounds
!! IterationEnd
}
method skip-one {
return False unless @!stuff;
@!stuff.shift;
True
}
}.new: :@stuff
}
my $hash = hash-it(<foo bar ber>).skip(2).head;
say "Made hash {now - INIT now}";
say bcrypt-match 'ber', $hash;
# OUTPUT:
# Made hash 2.2548012
# True
我们给 Iterator 添加了一个 .skip-one 方法, 不是哈希化一个值, 仅仅丢弃这个值。它需要返回一个真值, 如果它能跳过一个值(例如:如果我们有值我们会在 .pull-one 中生成一个值, 但是我们跳过了它), 或者返回 false 如果没有要跳过的值。
现在,在我们的 Seq 上调用的 .skip 方法使用我们的新的 .skip-one 方法来便宜地跳过 2 个项目,然后使用 .pull-one 生成第三个哈希值。 看现在的耗时:2.2s; 即生成单个散列所需的时间。
但是,我们可以踢起来一下。 虽然我们不会注意到与我们的 3-item Seq 有差异,但试图跳过 1,000,000 项目的用户将无法获得 2.2 秒的时间来生成第 1,000,000 个散列。 他们还必须等待 1,000,000个 .skip-one 调用和 @!stuff.shift。 为了优化跳过一堆项目,我们可以实现 .skip-at-least 方法(简而言之,只显示我们的 Iterator 类):
class :: does Iterator {
has @.stuff;
method pull-one {
@!stuff
?? bcrypt-hash(@!stuff.shift, :15pounds)
!! IterationEnd
}
method skip-one {
return False unless @!stuff;
@!stuff.shift;
True
}
method skip-at-least(Int \n) {
n == @!stuff.splice: 0, n
}
}
.skip-at-least 方法接收一个 Int 类型的参数, 表示要跳过的条目。它应该尽可能多地跳过指定数量的元素。如果它能够跳过那么多的条目, 则返回真, 如果跳过的条目数少于指定的数量则返回 false。现在, 用户要跳过 1,000,000 个条目时只会有一次 .splice
调用。
为了完整性, Iterator 定义了另外一个跳过方法: .skip-at-least-pull-one。它和 .skip-at-least 遵守相同的语义, 除了 .pull-one
语义是为了返回值。它的默认实现仅仅调用那俩个方法, 并且是短路的, 并且返回 IterationEnd 如果 .skip-at-least
返回一个假值, 并且默认实现很可能对所有 Iterators 就足够了。这个方法的存在便于 Iterator 用户调用 Iterator 上的方法(此时)它没有用在 Rakudo Raku 的核心代码中的任何调用 Seq 的方法中。
A so, so count…
还有俩个优化方法-.bool-only
和 .count-only
- 这俩方法没有默认实现。第一个方法返回 True
或 False
, 根据 Iterator 是否仍能生成条目(如果能就返回 True)。第二个方法返回 Iterator 还能生成的元素数。重要的是这些方法必须能够在不穷尽 Iterator 的情况下做到。换句话说, 在发现这些方法被实现之后, 我们 Iterator 的用户能够调用它们, 以后, 应该仍能拉取(.pull-one
) 所有的条目, 就像所有的方法从未调用过一样。
我们来制造一个接收 Iterable
和 .rotate
的 Iterator, 它每次迭代一次我们的 Iterator 直到它的尾变为它的头。基本上, 我们想这样:
.say for rotator 1,2,3,4;
# OUTPUT:
# [2 3 4 1]
# [3 4 1 2]
# [4 1 2 3]
这个迭代器将用于研究两种迭代器方法。 对于较少的“made-up”示例,请尝试在 Raku 编译器的源代码中查找迭代器的排列组合子例程的实现。
下面有一个子例程,它与我们的闪亮的迭代器一起创建了 Seq,还有一些代码可以运行在程序的不同阶段:
sub rotator (*@stuff) {
Seq.new: class :: does Iterator {
has int $!n;
has int $!steps = 1;
has @.stuff is required;
submethod TWEAK { $!n = @!stuff − 1 }
method pull-one {
if $!n-- > 0 {
LEAVE $!steps = 1;
[@!stuff .= rotate: $!steps]
}
else {
IterationEnd
}
}
method skip-one {
$!n > 0 or return False;
$!n--; $!steps++;
True
}
method skip-at-least (Int \n) {
if $!n > all 0, n {
$!steps += n;
$!n −= n;
True
}
else {
$!n = 0;
False
}
}
}.new: stuff => [@stuff]
}
my $rotations := rotator ^5000;
if $rotations {
say "Time after getting Bool: {now - INIT now}";
say "We got $rotations.elems() rotations!";
say "Time after getting count: {now - INIT now}";
say "Fetching last one...";
say "Last one's first 5 elements are: $rotations.tail.head(5)";
say "Time after getting last elem: {now - INIT now}";
}
# OUTPUT:
# Time after getting Bool: 0.0230339
# We got 4999 rotations!
# Time after getting count: 26.04481484
# Fetching last one...
# Last one's first 5 elements are: 4999 0 1 2 3
# Time after getting last elem: 26.0466234
首先,让我们来看看我们在迭代器中做了什么。我们接收一个 Iterable(在第37行的 sub 调用中,我们使用一个Range对象,在这种情况下我们可以加入5000个元素),将其克隆(使用[…]运算符),并将该克隆保存在@ !我们的迭代器的东西属性。在对象实例化过程中,我们还在TWEAK子方法内保存了多少个@!东西在$!n属性中。
对于每个pull - 迭代器之一,我们旋转我们的@!stuff属性,将旋转的结果存储在其中,以及对其进行浅克隆,这是我们返回的迭代。
我们还已经实现了.skip-one和.skip-at-least优化方法,其中我们使用私有的$!steps属性来改变下一个.pull-one将旋转我们的@!东西的步骤。每当调用.pull-one时,我们只需使用LEAVE移相器将$!步骤重置为默认值1。
我们来看看这个东西怎么样!我们将我们宝贵的Seq存储在$ rotations变量中,我们首先检查真实性,看看它是否具有任何元素;那么我们告诉世界我们可以从Seq中捞出多少轮?最后,我们获取Seq的最后一个元素(为了屏幕空间的原因)打印最后一个旋转的前5个元素。
所有三个步骤 - 检查.Bool,检查.elems和获取最后一个项目与.tail是定时的,结果不是很漂亮。而.Bool相对较快地完成,.elems通话花了很长时间(26s)!这实际上并不是所有的伤害。从本系列的第一部分回顾.Bool和.elems缓存Seq,除非在Iterator中实现了特殊的方法。这意味着我们所做的每一次旋转仍然在记忆中,无空间地使用空间!我们要做什么?我们来尝试实现这些特殊的方法.Bool和.elems正在寻找!
我们需要改变的只是为了给我们的迭代器添加两个额外的方法来确定我们可以生成多少个元素(.count),以及我们是否有任何元素来生成(.bool-only):
method count-only { $!n }
method bool-only { $!n > 0 }
为了完整起见,这里是我们前面的例子,将这两种方法添加到Iterator中:
sub rotator (*@stuff) {
Seq.new: class :: does Iterator {
has int $!n;
has int $!steps = 1;
has @.stuff is required;
submethod TWEAK { $!n = @!stuff − 1 }
method count-only { $!n }
method bool-only { $!n > 0 }
method pull-one {
if $!n-- > 0 {
LEAVE $!steps = 1;
[@!stuff .= rotate: $!steps]
}
else {
IterationEnd
}
}
method skip-one {
$!n > 0 or return False;
$!n--; $!steps++;
True
}
method skip-at-least (\n) {
if $!n > all 0, n {
$!steps += n;
$!n −= n;
True
}
else {
$!n = 0;
False
}
}
}.new: stuff => [@stuff]
}
my $rotations := rotator ^5000;
if $rotations {
say "Time after getting Bool: {now - INIT now}";
say "We got $rotations.elems() rotations!";
say "Time after getting count: {now - INIT now}";
say "Fetching last one...";
say "Last one's first 5 elements are: $rotations.tail.head(5)";
say "Time after getting last elem: {now - INIT now}";
}
# OUTPUT:
# Time after getting Bool: 0.0087576
# We got 4999 rotations!
# Time after getting count: 0.00993624
# Fetching last one...
# Last one's first 5 elements are: 4999 0 1 2 3
# Time after getting last elem: 0.0149863
代码几乎相同,但看看那些甜美的时光! 我们的整个程序运行速度大约是1733倍,因为我们的Seq可以弄清楚它是否和多少元素,而不必迭代或旋转任何东西。 .tail调用看到我们的优化(旁注:实际上是最近的),它也不必迭代任何东西,只能使用我们的.skip-at-least优化来跳过到最后。 最后但并非最不重要的是,我们的Seq不再被缓存,所以记忆中唯一的东西就是我们关心的事情。 这是一个非常少的额外的代码的双赢。
但等等…还有更多!
原文: https://rakudo.party/post/Perl-6-Seqs-Drugs-and-Rock-n-Roll--Part-2