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

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

为了大批快速判断数组 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 

上面两种方法哪个速度快,为什么?

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

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)

Redis 数据量大可以使用

fangxing204 回复

成功人士跑 benchmark 👍 👍

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

IChou 回复

谢谢

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

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

ecnelises 回复

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

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