Ruby 中数组和哈希的性能 [英] Performance of Arrays and Hashes in 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

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

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

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

在我的应用程序中，我主要需要找出一个文档是否存在.Hash 的 has_key? 函数是否比数组的线性搜索和 Document 对象的比较快得多?两者都在 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?

另外，有时我需要添加已经存在的文档.当我使用数组时，我之前必须使用 include? 进行检查，当我使用哈希时，我再次使用 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 中数组和哈希的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！