Ruby China

新手问题 散列和集合，为如下目的使用，哪个速度快？

czj · 2019年05月05日 · 最后由 jzlikewei 回复于 2019年05月10日 · 1488 次阅读

为了大批快速判断数组 A 中是否包含某元素：

hash = {}
A.each {|i| hash[i] = 1}
B.each do |x|
  if hash[x]
...
end

set = Set.new
A.each {|i| set.add(i)}
B.each do |x|
  if set.include?(x)
 ....
end

上面两种方法哪个速度快，为什么？

IChou #1 2019年05月05日

Set 是用 Hash 做存储的，你说谁会更快

fangxing204 #2 2019年05月05日 
require 'benchmark'
require 'set'

Benchmark.bm do |x| 
  x.report 'Hash' do
    hash = {}
    (1..50000).each {|i| hash[i] = 1}
    (25000..52500).each do |x| 
      if hash[x]
      end 
    end 
  end 

  x.report 'Set' do
    set = Set.new
    (1..50000).each {|i| set.add(i)}
    (25000..52500).each do |x| 
      if set.include?(x)
      end 
    end 
  end 
end

Set 确实慢一点，应该是慢在调用Object#hash上

       user     system      total        real 
Hash  0.010000   0.000000   0.010000 (  0.012221)
Set  0.020000   0.000000   0.020000 (  0.015573)
darksky #3 2019年05月05日

Redis 数据量大可以使用

IChou #4 2019年05月06日
对 fangxing204 回复

成功人士跑 benchmark 👍 👍

Set 更慢是因为 Set 的 add 和 include? 方法本就是 Hash 的 hash[i] = true 和 hash[i], 是在 Ruby 层面上套了个壳

czj #5 2019年05月06日
对 IChou 回复

谢谢

我用 hash = {}在做 leecode 上一个题目提交遇到错误了，然后换了 set=Set.new 提交通过了。让我以为 Set 使用的是和 Hash 不同的结构，才问了最初的问题。看了你们的回复，我又用 hash = Hash.new 代替 hash = {} ,提交就通过了。 是否 hash = {} 和 hash = Hash.new 背后是不同的？

ecnelises #6 2019年05月06日

原来 Ruby 的 Set 是用 Hash 实现的…我以为像 C++ 一样是用红黑树实现的

jzlikewei #7 2019年05月10日
对 ecnelises 回复

文档上写了“Set uses Hash as storage, so you must note the following points:”

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