Представление массивов и хэшей в Ruby

Question

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

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

Теперь, какой самый быстрый способ хранения тысяч этих объектов?

Раньше я помещал их все в массив документов:

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

Теперь альтернативой было бы хранить их в хеше:

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

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

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

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

Answer 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)

Answer 2

В стандартной библиотеке Ruby есть класс set. Вы рассматриваете вопрос о сохранении только (дополнительного) набора идентификаторов?

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

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

Answer 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 для этого теста.

Answer 4

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

2. Использование хеша документов по идентификатору документа с || = для условной вставки (вместо has_key?).

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

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