ruby - 如何解释这些 ruby​​ 代码的性能差异？

Question

我正在针对以下问题执行一些速度测试:

Given 2 strings, s1 and s2, that contain only lowercase alphabets, output if the letters of s1 can be re-arranged such that s2 becomes a substring of s1.

我在 ruby​​ 中获得了 2 个解决方案:

版本 1:

def scramble(s1,s2)
  if s1.length < s2.length
    return false
  end

  a = Array.new(26) { 0 }
  b = Array.new(26) { 0 }

  t1 = Time.now

  (0 ... s1.length).each do |x|
    a[s1[x].ord - 97] += 1
  end

  (0 ... s2.length).each do |x|
    b[s2[x].ord - 97] += 1
  end

  t2 = Time.now

  (0 ... 26).each do |x|
    if a[x] < b[x]
      return false
    end
  end

  puts t2 - t1

  return true
end

该版本将s1和s2中的字符数保存在一个直接寻址表中，并比较每个字符的计数。应该清楚，此代码执行大约 2 * (N + M) 次操作，其中 N 是 s1 的长度，M 是 s2 的长度。

版本 2:

def scramble(s1,s2)
  t1 = Time.now

  c = s2.chars
  c.uniq!
  t = c.all?{|x| s2.count(x)<=s1.count(x)}

  t2 = Time.now

  puts t2 - t1

  return t
end

此版本还使用 s1 和 s2 中的字符数，但不使用直接寻址表。据我了解，此版本应执行大约 26 * (N + M) 次操作，因为 count() 方法的复杂性与字符串中的字符数成线性关系，并且会针对字符串中的每个不同字符调用它。

当我表演时

scramble('abcdefghijklmnopqrstuvwxyz'*500000, 'abcdefghijklmnopqrstuvwxyz'*500000)

第一个版本需要 4.424207 秒，而第二个版本只需要 2.574269 秒。我用不同长度的 s1 和 s2 运行了几次测试，结果是一致的(版本 2 比版本 1 快得多)。由于它们的常数不同，我真的很困惑。为什么版本 2 中的代码运行速度比版本 1 快得多，尽管它具有更高的常量？

有人可以告诉我吗？

Answer 1

我认为这是因为像 String#count 这样的标准库方法是用 C 实现的，这比执行复杂的 Ruby 表达式 a[s1[x].ord - 97 ] += 1 循环 500000 次。

要明白我的意思，请尝试替换这些循环:

(0 ... s1.length).each do |x|
  a[s1[x].ord - 97] += 1
end

(0 ... s2.length).each do |x|
  b[s2[x].ord - 97] += 1
end

调用String#count:

(0 ... 26).each do |x|
  a[x] = s1.count((x + 97).chr)
  b[x] = s2.count((x + 97).chr)
end

通过此更改，它在我的机器上运行时间为 0.4 秒(与之前的 6.3 秒相比)!