Performances des tableaux et des hachages dans Ruby

Question

J'ai un programme qui permettra de stocker de nombreuses instances d'une classe, disons jusqu'à 10.000 ou plus. Les instances de classes ont plusieurs propriétés que j'ai besoin de temps à autre, mais leur plus important est l'ID.

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

Maintenant, quel est le moyen le plus rapide de stocker des milliers de ces objets?

J'ai utilisé de toutes les mettre dans un tableau de Documents:

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

Maintenant une autre solution serait de les stocker dans une table de Hachage:

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

Dans mon application, j'ai surtout besoin de savoir si un document existe. Est la valeur de Hachage de l' has_key? fonction significativement plus rapide qu'une recherche linéaire de la Matrice et la comparaison des Document objets? Sont à la fois dans O(n) ou est - has_key? même O(1). Vais-je voir la différence?

Aussi, parfois, j'ai besoin d'ajouter des Documents quand il est déjà existants. Lorsque j'utilise un Tableau, je voudrais vérifier avec include? avant, quand j'utilise une table de Hachage, j'aimerais utiliser has_key? de nouveau. Même question que ci-dessus.

Quelles sont vos pensées? Quelle est la méthode la plus rapide de stocker de grandes quantités de données lorsque 90% du temps, j'ai seulement besoin de savoir si l'ID existe (et non l'objet lui-même!)

Answer 1

Les hachages sont beaucoup plus rapides pour les recherches:

 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 a une classe d'ensemble dans sa bibliothèque standard, avez-vous envisagé de conserver un ensemble (supplémentaire) d'ID uniquement?

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

Pour citer les documents: "Il s'agit d'un hybride des fonctionnalités d'interaction intuitive d'Array et de la recherche rapide de Hash".

Answer 3

Lors de l'utilisation de valeurs uniques, vous pouvez utiliser le Ruby Ensemble de ce qui a été mentionné précédemment. Voici les résultats d'un benchmark. Il est légèrement plus lent que le hachage bien.

                 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)

J'ai simplement ajouté à @steenslag du code qui peut être trouvé ici https://gist.github.com/rsiddle/a87df54191b6b9dfe7c9.

J'ai utilisé ruby 2.1.1p76 pour ce test.

Answer 4

1. L'utilisation d'un Ensemble de Documents. Il a la plupart des propriétés que vous souhaitez (constante de temps de recherche et ne permettent pas de doublons),. Smalltalkers vous dirais qu'à l'aide d'une collection qui a déjà les propriétés que vous voulez est plus de la bataille.

2. Utiliser une table de Hachage de Documents par l'id du document, avec ||= conditionnelle d'insertion (plutôt que has_key?).

Les hachages sont conçus pour une constante de temps de l'insertion et de la recherche. Ruby Jeu utilise un Hachage interne.

Sachez que vos objets de Document devra mettre en œuvre les #hash et #eql? de la bonne façon pour eux de se comporter comme vous vous attendriez à ce que les clés de Hachage ou de membres d'un ensemble, comme ils sont utilisés pour définir de hachage de l'égalité.