Выполнение массивов и хэшей в Ruby

У меня есть программа, которая будет хранить много экземпляров одного класса, пусть говорят до 10.000 или более. У экземпляров класса есть несколько свойств, которые мне нужны время от времени, но их наиболее важным является идентификатор.

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

В моем приложении мне в основном нужно выяснить, существует ли вообще документ. Является ли функция Hash has_key? значительно быстрее, чем линейный поиск массива и сравнение объектов Document? Оба внутри O (n) или равно has_key? даже O (1). Я увижу разницу?

Кроме того, иногда мне нужно добавлять документы, когда они уже существуют. Когда я использую Array, мне нужно будет проверить с помощью include? раньше, когда я использую Hash, я бы просто использовал has_key? снова. Тот же вопрос, что и выше.

Каковы ваши мысли? Какой самый быстрый способ хранения больших объемов данных, когда 90% времени мне нужно знать только, существует ли идентификатор (а не сам объект!)

Ответ 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)

Ответ 2

Ruby имеет класс набора в своей стандартной библиотеке, считаете ли вы, что у вас есть (дополнительный) набор идентификаторов?

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

Чтобы процитировать документы: "Это гибрид интуитивно понятных средств взаимодействия с массивами и быстрый поиск Hashs".

Ответ 3

При использовании уникальных значений вы можете использовать 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 для этого теста.

Ответ 4

Используйте набор документов. Он имеет большинство свойств, которые вы хотите (постоянный поиск и не допускает дубликатов). Smalltalkers расскажут вам, что использование коллекции, которая уже имеет нужные вам свойства, - это большая часть битвы.
Использовать хеш документов по идентификатору документа, где || = для условной вставки (а не has_key?).

Хеши предназначены для вставки и поиска по постоянному времени. Ruby Set использует хэш внутри.

Имейте в виду, что для объектов Document необходимо реализовать #hash и #eql? правильно, чтобы они вели себя так, как вы ожидали бы в качестве ключей хэша или членов набора, поскольку они используются для определения хэш-равенства.