perl - 使用闭包作为迭代器

Question

我最近一直在研究马尔可夫链，试图从一个大型语料库中生成文本，只是为了看看我得到了什么(其中一些非常有趣)。

构建文本生成所需的数据结构的很大一部分是创建 n-grams .给定一个小样本文本:“今天是三月六日，星期四”，一个 n-gram 示例，其中 n = 3 将是:

Today is Thursday
is Thursday March 
Thursday March the
March the sixth
# skipped lines that have < 3 words because is isn't enough for a 3-gram

根据文本的大小，我的代码生成的 n-gram 列表可能非常大，在某些语言中有 generator 的概念它包含一个生成自定义迭代器的 yield 语句，但不幸的是 Perl 不是其中之一。

相反，在 Perl 中我们可以对词法变量使用闭包来创建 Iterators ，但我在理解使用它们时真正获得的东西时遇到了一些麻烦。

这是我创建的用于创建 n-gram 的迭代器(假设 n 保存在 $self->order 中):

sub _ngrams {
   my ($self, @words) = @_; 

   return sub {
      while(@words) {
         my @ngram = @words[0 .. $self->order]; # get $order + 1 words
         shift @words;                          # drop the first word

         return @ngram;
      }

      return; # nothing left to do
  };
}

我真的能从这段代码中获得任何效率方面的好处吗？单词列表仍然完全保存在 @words 的内存中。是否有替代实现可以减少我的内存占用？

这里是如何使用迭代器生成字典的:

sub seed { 
   my $self = shift; 

   my $ngram_it = $self->_ngrams(split /\s+/, $self->text); 
GRAM:
   while (my @gram = $ngram_it->()) {
      next GRAM unless @gram == scalar grep { $_ } @gram;

      my $val = pop @gram; 
      my $key = join ' ', @gram; 

      if (exists $self->lexicon->{$key}) {
         push @{$self->lexicon->{$key}}, $val;
      }
      else {
         $self->lexicon->{$key} = [$val];
      }
   }
}

任何输入都会非常有帮助。

Answer 1

首先，您的迭代器实现有在最后几个值中返回 undef 项的不良趋势。我会把它改成

sub _ngrams {
   my ($self, @words) = @_; 
   my $order = $self->order;

   return sub {
      if (@words > $order) {
         my @ngram = @words[0 .. $order]; # get $order + 1 words
         shift @words;                          # drop the first word

         return @ngram;
      }

      return; # nothing left to do
  };
}

接下来，这个迭代器是一个很好的抽象。它并不意味着以任何方式提高性能，它只是使您的主要代码更简单有用。在这里，如果您不分离迭代并在主代码中完成所有操作，您的代码会更短(但不会更简单)。

但是，迭代器可以处理有趣的事情，例如惰性求值或无限流。为了使它有用，我们必须完全切换到流:

# contract: an iterator returns a list of things
# or an empty list when depleted

sub _ngrams {
   my ($self, $source) = @_; 
   my $order = $self->order;

   my @ngram = (undef, map { $source->() } 1 .. $order);

   return sub {
      if (my ($next) = $source->()) {
          (undef, @ngram) = (@ngram, $next);  # or instead: shift/push
          return @ngram;
      }
      return;
  };
}

会像这样初始化

my $text = $self->text;
my $iter = $self->_ngrams(sub {
    return $1 if $text =~ /\G\s*(\S+)/gc;
    return;
});

这在这里有用吗？不，因为您立即从迭代器中获取所有元素。 最简单 的解决方案不使用花哨的抽象，只是这样:

sub seed { 
   my $self = shift; 

   my @words = split /\s+/, $self->text;
   my $order = $self->order;
   while (@words > $order) {
      my @gram = @words[0 .. $order];  # get the next n-gram
      shift @words;

      my $val = pop @gram; 
      push @{$self->lexicon->{join ' ', @gram}}, $val;
   }
}

我敢打赌它也是(时间)性能最高的变体。

注意:不需要测试 exists，因为 Perl 散列 autovivify。 (或者您正在使用奇怪的扩展程序？)