Ruby China

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

czj · May 05, 2019 · Last by jzlikewei replied at May 10, 2019 · 1485 hits

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

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

fangxing204 #2 May 05, 2019 
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 May 05, 2019

Redis 数据量大可以使用

IChou #4 May 06, 2019
Reply to fangxing204

成功人士跑 benchmark 👍 👍

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

czj #5 May 06, 2019
Reply to IChou

谢谢

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

ecnelises #6 May 06, 2019

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

jzlikewei #7 May 10, 2019
Reply to ecnelises

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

You need to Sign in before reply, if you don't have an account, please Sign up first.