算法中的 Ruby 枚举#计数性能问题

Question

我已经使用 Ruby 从 LeetCode 解决了这个问题，但我遇到了一些我不明白的性能问题。

这是我的代码：

def word_subsets(a, b)
occurrence_map = max_occurrences(b)
a.select do |w|
word_occurrence = letter_occurrence(w)
occurrence_map.all? { |k, v| v <= word_occurrence[k]  }
end
end
def letter_occurrence(word)
Hash.new(0).tap do |occurrences|
word.each_char { |c| occurrences[c] += 1 }
end
end
def max_occurrences(b)
Hash.new(0).tap do |occurrences|
b.each do |word|
word_occurrences = letter_occurrence(word)
word.each_char { |c| occurrences[c] = [occurrences[c], word_occurrences[c]].max }
end
end
end

这段代码有效，但它没有最好的运行时，我试图理解为什么。在阅读另一个 Ruby 解决方案时，我意识到最令人困惑的事情如下：如果我在 max_occurrences 方法中进行此更改：

def max_occurrences(b)
Hash.new(0).tap do |occurrences|
b.each do |word|
word.each_char { |c| occurrences[c] = [occurrences[c], word.count(c)].max }
end
end
end

它带来了重要的性能改进，我真的不明白为什么。我不明白为什么，因为我的原始编写方式并没有为每个字符调用计数方法。我认为调用此方法会迭代数组，因此我只计算一次所有出现次数，而不是这样做。但我的方法似乎更糟，我不知道为什么。

使用 count 方法确实提高了代码的性能，但我认为它仍然很糟糕，所以如果你能给我一些建议或线索，那就太好了。

Answer 1

在您的版本中，您确实不使用count.相反，你做了一些更糟糕的事情。您仍然迭代字符串(letter_occurrence)，并且您还在构建哈希(这是额外的工作)。

Ruby的String#count(另一个版本正在使用的)是用C实现的。这一点，以及它不构建临时哈希的事实可以解释性能的差异。

Answer 2

由于您的答案已经得到回答，我将提出一个我认为应该相对有效的替代解决方案。关键是我在b中为每个单词创建计数哈希值，然后再迭代a中的单词。

a = ["dangled", "glad", "gladden", "dogged"] 
b = ["gad", "lag", "dad"]
ba = b.map { |w| w.each_char.with_object(Hash.new(0)) { |c,h| h[c] += 1 } }
#=> [{"g"=>1, "a"=>1, "d"=>1}, {"l"=>1, "a"=>1, "g"=>1}, {"d"=>2, "a"=>1}]
a.select do |w|
ah = w.each_char.with_object(Hash.new(0)) { |c,h| h[c] += 1 }
ba.all? { |wh| wh.all? { |c,cnt| ah.fetch(c,0) >= cnt } }
end
#=> ["dangled", "gladden"]

当w = "dogged"a.select do |w|...时，我们得到以下ah：

ah = w.each_char.with_object(Hash.new(0)) { |c,h| h[c] += 1 }
#=> {"d"=>2, "o"=>1, "g"=>2, "e"=>1}

当wh = {"g"=>1, "a"=>1, "d"=>1}，

wh.all? { |c,cnt| ah.fetch(c,0) >= cnt }

首次执行

c = "g"
cnt = 1 
ah.fetch("g", 0) >= 1 #=> 2 >= 1 => true

由于"g"通过了测试，我们接下来计算

c = "a"
cnt = 1 
ah.fetch("a", 0) >= 1 #=> 0 >= 1 => false

ah.fetch("a", 0)返回0，因为ah没有密钥"a"。

由于h.fetch("a", 0) >= 1返回false，wh.all? { ... }返回false，因此不选择w = "dogged"。

可以通过对ba中的哈希重新排序(例如，通过减少单词长度)和/或对ba的每个元素中的键/值对重新排序(通过减少值或增加英语文本中的频率[例如，'z'第一个，'e'最后一个])来提高性能。