Ruby中数组和哈希的性能

Question

我有一个程序可以存储一个类的许多实例,比方说高达10.000或更多.类实例有不时需要的几个属性,但最重要的属性是ID.

class Document
  attr_accessor :id
  def ==(document)
    document.id == self.id
  end
end

现在,存储数千个这些对象的最快方法是什么？

我曾经将它们全部放入一个文档数组中:

documents = Array.new
documents << Document.new
# etc

现在另一种方法是将它们存储在Hash中:

documents = Hash.new
doc = Document.new
documents[doc.id] = doc
# etc

在我的应用程序中,我主要需要找出文档是否存在.哈希的has_key?函数是否明显快于数组的线性搜索和Document对象的比较？都在O(n)内或has_key?甚至是O(1).我会看到区别吗？

此外,有时我需要在文档已经存在时添加它.当我使用数组时,我必须先检查include?,当我使用哈希时,我只是has_key?再次使用.与上述问题相同.

你的想法是什么？什么是存储大量数据的最快方法,90%的时间我只需要知道ID是否存在(而不是对象本身!)

Answer 1

哈希的查找速度要快得多:

require 'benchmark'
Document = Struct.new(:id,:a,:b,:c)
documents_a = []
documents_h = {}
1.upto(10_000) do |n|
  d = Document.new(n)
  documents_a << d
  documents_h[d.id] = d
end
searchlist = Array.new(1000){ rand(10_000)+1 }

Benchmark.bm(10) do |x|
  x.report('array'){searchlist.each{|el| documents_a.any?{|d| d.id == el}} }
  x.report('hash'){searchlist.each{|el| documents_h.has_key?(el)} }
end

#                user     system      total        real
#array       2.240000   0.020000   2.260000 (  2.370452)
#hash        0.000000   0.000000   0.000000 (  0.000695)

Answer 2

使用唯一值时，可以使用前面提到的Ruby Set 。以下是基准测试结果。但它比哈希稍微慢一些。

                 user     system      total        real
array        0.460000   0.000000   0.460000 (  0.460666)
hash         0.000000   0.000000   0.000000 (  0.000219)
set          0.000000   0.000000   0.000000 (  0.000273)

我只是添加了 @steenslag 的代码，可以在这里找到https://gist.github.com/rsiddle/a87df54191b6b9dfe7c9。

我使用 ruby​​ 2.1.1p76 进行此测试。

Answer 3

Ruby在其标准库中有一个set类,您是否考虑过只保留一组(附加)ID？

http://stdlib.rubyonrails.org/libdoc/set/rdoc/index.html

引用文档:"这是Array的直观互操作设施和Hash快速查找的混合体".