38 votos

El rendimiento de los Arrays y Hashes en Rubí

Tengo un programa que se va a almacenar el número de instancias de una clase, digamos hasta 10.000 o más. Las instancias de la clase tiene varias propiedades que necesito de vez en cuando, pero su más importante es el de la IDENTIFICACIÓN.

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

Ahora, ¿cuál es la manera más rápida de almacenar miles de estos objetos?

Yo solía poner a todos en una matriz de Documentos:

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

Ahora una alternativa sería que los almacene en un Hash:

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

En mi aplicación, que en su mayoría necesitan para averiguar si el documento existe en absoluto. Es el Hash de la has_key? función significativamente más rápido que una búsqueda lineal de la Matriz y la comparación de Document objetos? Ambos están dentro de O(n) o es has_key? incluso de O(1). Voy a ver la diferencia?

También, a veces tengo que añadir Documentos cuando ya existentes. Cuando yo uso una Matriz, tendría que consultar con include? antes, cuando yo uso un Hash, que acababa de uso has_key? de nuevo. Misma pregunta que el anterior.

¿Cuáles son tus pensamientos? ¿Cuál es el método más rápido de almacenar grandes cantidades de datos cuando el 90% del tiempo solo necesito saber si el ID existe (no el objeto en sí mismo!)

98voto

steenslag Puntos 29662

Los valores hash son mucho más rápidos para las búsquedas:

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)

5voto

Michael Kohl Puntos 33345

Ruby tiene un conjunto de la clase en su biblioteca estándar, tienen que considerar mantener un (adicional) conjunto de Identificadores de sólo?

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

A la cita de la documentación: "Este es un híbrido de la Matriz intuitiva de la inter-operación de las instalaciones y el Hash de la búsqueda rápida".

3voto

Ryan Puntos 11

Cuando se utilizan valores únicos, puede utilizar el Rubí Conjunto que ha sido mencionado anteriormente. Aquí están los resultados de referencia. Es ligeramente más lento que el hash aunque.

                 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)

Simplemente he añadido a @steenslag del código que se puede encontrar aquí https://gist.github.com/rsiddle/a87df54191b6b9dfe7c9.

He utilizado ruby 2.1.1p76 para esta prueba.

2voto

Rein Henrichs Puntos 3592
  1. El uso de un Conjunto de Documentos. Tiene la mayoría de las propiedades que desee (constante de tiempo de búsqueda y no permite duplicados),. Smalltalkers diría usted que el uso de una colección que ya tiene las propiedades que queremos es que la mayor parte de la batalla.

  2. Utilizar un Hash de Documentos por id de documento, con | a|= condicional de inserción (en lugar de has_key?).

Los valores hash son diseñados para una constante de tiempo de la inserción y búsqueda. Ruby juego usa un Hash internamente.

Ser consciente de que su Documento de objetos a la necesidad de implementar #hash y #eql? correctamente en orden para que puedan comportarse como cabría esperar como claves Hash o miembros de un conjunto, ya que estos son utilizados para definir el hash de la igualdad.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X