为什么 array.min 这么慢？

Question

我注意到 array.min 看起来很慢，所以我针对我自己的天真实现做了这个测试：

require 'benchmark'
array = (1..100000).to_a.shuffle

Benchmark.bmbm(5) do |x|
  x.report("lib:") { 99.times { min = array.min } }
  x.report("own:") { 99.times { min = array[0]; array.each { |n| min = n if n < min } } }
end

结果：

Rehearsal -----------------------------------------
lib:    1.531000   0.000000   1.531000 (  1.538159)
own:    1.094000   0.016000   1.110000 (  1.102130)
-------------------------------- total: 2.641000sec

            user     system      total        real
lib:    1.500000   0.000000   1.500000 (  1.515249)
own:    1.125000   0.000000   1.125000 (  1.145894)

我很震惊。我自己的实现如何通过 each 实现运行块来击败内置的？还打了这么多？

我是不是搞错了？或者这在某种程度上是正常的？我很困惑。

我的 Ruby 版本，运行 Windows 8.1 Pro：

C:\>ruby --version
ruby 2.2.3p173 (2015-08-18 revision 51636) [i386-mingw32]

Answer 1

如果你使用它会更快：

def my_min(ary)
  the_min = ary[0]
  i = 1
  len = ary.length
  while i < len
    the_min = ary[i] if ary[i] < the_min
    i += 1
  end
  the_min
end

注意

我知道这不是答案，但我认为它值得分享，将这段代码放在评论中会非常难看。

Answer 2

看看 Enumerable#min. It might use each eventually to loop through the elements and get the min element, but before that it does some extra checking to see if it needs to return more than one element, or if it needs to compare the elements via a passed block. In your case the elements will get to be compared via min_i 函数的实现，我怀疑这就是速度差异的来源 - 该函数比简单地比较两个数字要慢。

数组没有额外的优化，所有的枚举都是一样的遍历。

Answer 3

对于那些喜欢升级到更新版本软件的人

require 'benchmark'
array = (1..100000).to_a.shuffle

Benchmark.bmbm(5) do |x|
  x.report("lib:") { 99.times { min = array.min } }
  x.report("own:") { 99.times { min = array[0]; array.each { |n| min = n if n < min } } }
end

Rehearsal -----------------------------------------
lib:    0.021326   0.000017   0.021343 (  0.021343)
own:    0.498233   0.001024   0.499257 (  0.499746)
-------------------------------- total: 0.520600sec

            user     system      total        real
lib:    0.018126   0.000000   0.018126 (  0.018139)
own:    0.492046   0.000000   0.492046 (  0.492367)

RUBY_VERSION # => "2.7.1"

如果您正在研究以真正高效的方式解决此问题：O(log(n)) 或 O(n)，请查看 https://en.wikipedia.org/wiki/Selection_algorithm#Incremental_sorting_by_selection and https://en.wikipedia.org/wiki/Heap_(data_structure)

为什么 array.min 这么慢？

Why is array.min so slow?

ruby

performance

min

built-in