按多个标准进行惯用懒惰排序

Question

在Ruby中，按多个标准排序的最常用方法是使用sort_by和排序函数，按照重要性降低的顺序返回与每个排序标准相对应的值的数组，例如：

Dir["*"].sort_by { |f| [test(?s, f) || 0, test(?M, f), f] }

将按大小排序目录条目，然后按mtime排序，最后按文件名排序。这是有效的，因为它使用Schwartzian transform只计算每个文件的大小和mtime一次，而不是每次比较一次。然而，它并不是真正的懒惰，因为它计算每个文件的mtime，但是如果（比方说）目录中的每个文件都有不同的大小，则不需要计算任何mtimes。

在这种情况下，这不是一个大问题，因为在查找大小后立即查找mtime应该是高效的，因为内核级别的缓存（例如Linux上的IIRC它们都来自stat(2)系统调用），我不会如果Ruby也有自己的优化，那就会感到惊讶。但是想象一下，如果第二个标准不是mtime，而是（比方说）文件中字符串的出现次数，并且所讨论的文件很大。在这种情况下，你真的想要懒惰的评估，以避免阅读所有这些巨大的文件，如果按大小排序就足够了。

在撰写本文时，Algorithm Implementation/Sorting/Schwartzian transform的Wikibooks条目提出了这个解决方案：

sorted_files =
  Dir["*"].                         # Get all files
    # compute tuples of name, size, modtime
    collect{|f| [f, test(?s, f), test(?M, f)]}.
    sort {|a, b|                    # sort
      a[1] <=> b[1] or              #   -- by increasing size
      b[2] <=> a[2] or              #   -- by age descending
      a[0] <=> b[0]                 #   -- by name
    }.collect{|a| a[0]}             # extract original name

这种方法是从Perl复制而来的

sort {
       $a->[1] <=> $b->[1] # sort first numerically by size (smallest first)
    or $b->[2] <=> $a->[2] # then numerically descending by modtime age (oldest first)
    or $a->[0] cmp $b->[0] # then stringwise by original name
  }

因为Perl有一个怪癖，0 or $foo评估为$foo，所以效果很好。但在Ruby中，由于0 or foo评估为0，因此它被打破了。实际上，Wikibooks实现完全忽略了mtimes和文件名，并且只按大小排序。我已经删除了我的Wikibooks帐户以便我可以解决这个问题，但我想知道：在Ruby中组合多个<=>太空飞船运营商比较结果的最简洁方法是什么？

我将举一个具体的例子来澄清这个问题。假设我们有两种类型的评估，在排序过程中可能需要作为标准。第一个相对便宜：

def size(a)
    # get the size of file `a`, and if we're feeling keen,
    # memoize the results
    ...
end

第二个是昂贵的：

def matches(a)
    # count the number of occurrences of a string
    # in file `a`, which could be a large file, and
    # memoize the results
    ...
end

我们希望先按大小升序排序，然后按匹配数降序排序。我们不能使用Schwartzian变换，因为这会非常懒惰地在每个项目上调用matches()。

我们可以定义一个帮助器

def nil_if_equal(result)
  result == 0 ? nil : result
end

然后做：

sort {|a, b|
  nil_if_equal(size(a) <=> size(b)) or
  matches(b) <=> matches(a)
}

如果有排序的n标准，那么你需要n-1在这里调用nil_if_equal，因为只有最后的排序标准不需要它。

那么有没有比这更习惯的方式可以避免需要nil_if_equal？

Answer 1

不知道它是多么惯用，但这是一种再次使用sort_by的方法。而不是例如

['bab', 'foo', 'so', 'bar'].sort_by { |s| [s.size, count_a(s), count_b(s)] }

这样做使count_a(s)和count_b(s)懒惰和记忆：

['bab', 'foo', 'so', 'bar'].sort_by { |s| [s.size, lazy{count_a(s)}, lazy{count_b(s)}] }

我的lazy使该块表现得像它产生的价值的懒惰和记忆版本。

演示输出，显示我们只计算必要的数量（即，不计入'so'，因为它具有独特的大小，并且不计算'b'中的'foo'，因为它的'a'计数在3号字符串中是唯一的）：

Counting 'a' in 'bab'.
Counting 'a' in 'foo'.
Counting 'a' in 'bar'.
Counting 'b' in 'bab'.
Counting 'b' in 'bar'.
["so", "foo", "bar", "bab"]

演示代码：

def lazy(&block)
  def block.value
    (@value ||= [self.yield])[0]
  end
  def block.<=>(other)
    value <=> other.value
  end
  block
end

def count_a(s)
  puts "Counting 'a' in '#{s}'."
  s.count('a')
end

def count_b(s)
  puts "Counting 'b' in '#{s}'."
  s.count('b')
end

p ['bab', 'foo', 'so', 'bar'].sort_by { |s| [s.size, lazy{count_a(s)}, lazy{count_b(s)}] }

使value记忆的另一种方法：如果它被调用，它会立即用一个只返回存储值的方法替换它自己：

  def block.value
    def self.value; @value end
    @value = self.yield
  end