数组和Ruby的哈希值的性能

问题描述：

我有将存储一个类的实例，让我们说高达10.000以上的程序。该类的实例有几个属性，我需要不时，但其最重要的一条是ID。

I have a program that will store many instances of one class, let's say up to 10.000 or more. The class instances have several properties that I need from time to time, but their most important one is the ID.

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

现在，什么是存储这些对象的数以千计的最快方法是什么？

Now, what is the fastest way of storing thousands of these objects?

我曾经把他们都到文档的数组：

I used to put them all into an array of Documents:

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

现在的替代办法是将它们存储在一个Hash：

Now an alternative would be to store them in a Hash:

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

在我的申请，我主要是要找出一个文件是否都存在。是哈希的对象的has_key？功能显著快于线性搜索阵列和文件对象的比较？中都的 O（N）的或对象的has_key？连的 O（1）的。我会看看有什么区别？

In my application, I mostly need to find out whether a document exists at all. Is the Hash's has_key? function significantly faster than a linear search of the Array and the comparison of Document objects? Are both within O(n) or is has_key? even O(1). Will I see the difference?

此外，有时我需要添加文件时，它已经存在。当我使用数组，我会检查与包括哪些内容？之前，当我使用一个Hash，我只是用对象的has_key？一次。同样的问题之上。

Also, sometimes I need to add Documents when it is already existing. When I use an Array, I would have to check with include? before, when I use a Hash, I'd just use has_key? again. Same question as above.

你有什么想法？什么是存储大量数据时，90％的时间我只需要知道ID是否存在的最快速的方法（而不是对象本身！）

What are your thoughts? What is the fastest method of storing large amounts of data when 90% of the time I only need to know whether the ID exists (not the object itself!)

答

哈希是的多的更快查找：

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)

数组和Ruby的哈希值的性能

相关推荐