为什么从基于大阵列的大散列中选择值太慢？

我有一个大约150k元素的散列和25k元素的数组。我需要创建一个新的散列或修改现有的散列，以删除所有键不在数组上的元素。这是我现在有的：为什么从基于大阵列的大散列中选择值太慢？

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

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

来源

2013-04-02 MurifoX

(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}

的一点是避免数组操作和哈希尽一切尽可能的。

来源

2013-04-02 18:16:24 sawa

让我试试看。 – MurifoX

哦，男人......超级快，thx。 – MurifoX

我又增加了一个。请尝试一下。 – sawa

@ sawa的答案很好，但速度很快，但它确实会让你比Hash#select笨拙地表达你的意图。如果数组是并且带有O（1）查找而不是带有O（N）查找的数组，那么您的初始方法就可以正常工作。

require 'set' 

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

This microbenchmark演示集快速，这种做法是略高于@sawa建议当设置为预建的，只是或多或少地更慢，如果集必须在飞行中进行的关键减法删除方法更快。

      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)

来源

2013-04-02 21:26:04 dbenhur

真的很好的答案。我不知道'Set'性能。 – MurifoX

为什么从基于大阵列的大散列中选择值太慢？

回答

相关问题