ruby - 为什么从基于大数组的大哈希中选择值这么慢？

Question

我有一个包含大约 150k 个元素的散列和​​一个包含 25k 个元素的数组。我需要创建一个新的散列，或修改现有的散列，以删除其键不在数组上的所有元素。这是我现在拥有的：

hash.select {|k,v| array.include?(k)}
new_hash = hash.delete_if {|k,v| !array.include?(k)}

由于比较复杂，这两种方法非常慢。有没有办法可以加快速度？

Answer 1

(hash.keys - array).each{|k| hash.delete(k)}

或者，这可能会更快：

keys_to_be_removed = {}
hash.each{|k, _| keys_to_be_removed[k] = true}
array.each{|k| keys_to_be_removed[k] = false}
keys_to_be_removed.each{|k, v| hash.delete(k) if v}

关键是要避免数组操作，并尽可能在哈希中做所有事情。

Answer 2

@sawa 的回答在提高速度方面很好，但它确实让你表达你的意图比Hash#select. 如果数组是Set使用 O(1) 查找而不是使用 O(N) 查找的数组，那么您的初始方法将工作得很好。

require 'set'

set = array.to_set
hash.select { |k,v| set.include?(k) }

这个微基准测试表明集合速度很快，并且这种方法比预建集合时推荐的键减删除方法略快，如果必须动态创建集合，则速度略慢。

                          user     system      total        real
noop                    0.600000   0.020000   0.620000 (  0.614905)
keys_minus_arr_delete   1.190000   0.020000   1.210000 (  1.213376)
select_set_include      1.050000   0.010000   1.060000 (  1.084079)
select_set_include_fly  1.350000   0.020000   1.370000 (  1.361623)
sawa2                   1.860000   0.020000   1.880000 (  1.870162)