在Ruby中计算子字符串列表出现次数的最快方法

Question

我的问题很简单，我有一组子字符串，需要计算这些子字符串在一个特定字符串中出现的次数。以下是我的代码：

string = "..."
substrings = ["hello", "foo", "bar", "brol"]
count = 0
substrings.each do |sub|
    count += 1 if string.include?(sub)
end

在这个例子中，我们对整个字符串进行了4次运算，这是相当耗费资源的。你应该如何优化这个过程？

- Jérôme Boé

Answer 1

这个方法利用Regexp.union仅运行一次来处理字符串：

string = 'hello there! this is foobar!'
substrings = ["hello", "foo", "bar", "brol"]

string.scan(Regexp.union(substrings)).count
# => 3

虽然这个解决方案在输入较小的情况下速度明显较慢，但它具有更低的复杂度-对于长度为n的字符串和长度为m的子字符串，原始解决方案的复杂度为O(m*n)，而此解决方案的复杂度为O(m+n)。

---

更新
重新阅读问题和我的答案后，我得出结论，不仅这是一种过早的优化（正如@Max所指出的那样），而且我的答案与OP在语义上是不同的。

让我解释一下-OP代码计算有多少个子字符串在字符串中至少出现一次，而我的解决方案计算任何一个子字符串出现了多少次：

op_solution('hello hello there', ["hello", "foo", "bar", "brol"])
# => 1
uri_solution('hello hello there', ["hello", "foo", "bar", "brol"])
# => 2

这也解释了为什么我的解决方案对于长字符串也非常慢——虽然它只在输入字符串上进行一次遍历，但必须通过全部的字符，而原始代码在第一次单词出现时就停止了。

我的结论是——采用@Arup的解决方案。它不会比您的更快，只是更简洁，但我想不出更好的方法 :)

- Uri Agassi

---

我很好奇看看在什么时候这个算法开始超越朴素的O(mn)算法。这有点像过早进行优化。 - Max

也许可以对字符串进行排序并使用二分法？ - Jérôme Boé

你假设你的子字符串是单个完整的单词？ - Uri Agassi

Answer 2

write as :-

substrings.count { |sub| string.include?(sub) }

- Arup Rakshit

---

这段代码实际上并没有比原始代码运行得更快（尽管它写得更漂亮）。 - Uri Agassi

这比 string.scan 更快运行（根据基准测试）... string.scan 的速度大约慢了18倍。 - SteveTurczyn

@SteveTurczyn - 这里的问题更多是关于复杂度 - 随着字符串变得越来越长，子字符串变得越来越大，这个解决方案的时间复杂度为O(m*n)，而扫描解决方案的复杂度为O(m+n)。 - Uri Agassi

@UriAgassi 你觉得 substrings.count { |sub| string[sub] } 怎么样？ - Arup Rakshit

这完全相同 - 对于每个子字符串（m 次），它都遍历整个字符串（长度为 n），这给出了复杂度为 O(m*n)。这比您原来的答案更简洁，非常符合 Ruby 的习惯用法，但运行时间（本质上）是相同的。 - Uri Agassi

@UriAgassi 哦 :( :( - Arup Rakshit

Answer 3

subtrings.collect { |i| string.scan(i).count }.sum

优雅。

- Rich_F