Ruby shuffle 的效率真让人惊讶~~

zw963 · 2012年08月15日 · 最后由 zw963 回复于 2012年08月16日 · 3818 次阅读
a = (1..10000).to_a

Benchmark.bm(30) do |x|
  x.report("random a 10000 element array 100 times") do
    100.times { a.sort_by { rand } }
  end
end

Benchmark.bm(30) do |x|
  x.report("shuffle a 10000 element array 100 times") do
    100.times { a.shuffle }
  end
end

输出结果:

                                           user      system     total      real
random a 10000 element array 100 times  1.600000   0.000000   1.600000 (  1.602049)
                                          user       system     total      real
shuffle a 10000 element array 100 times  0.030000   0.010000   0.040000 (  0.041415)

两个算法不一样啊

挺有意思啊

sort_by 是先给每个元素生成一个用于排序的值,然后再调用 sort,将该值做 x <=> y 的比较得出结果,而 shuffle 直接用 Fisher Yates 洗牌算法,效率差很多的。

#3 楼 @quakewang

恩,so 上也是这么说的。虽然我不知道Fisher Yates算法 是个嘛玩意儿~~

需要 登录 后方可回复, 如果你还没有账号请 注册新账号