Как быстрее всего найти элемент в массиве используя руби?

Question

[Ord EO]

Есть массив вида

arr = [
{key: 1, value: some_value441},
{key: 2, value: some_value212},
{key: 3, value: some_value33},
{key: 4, value: some_value44},
]

Нужно по значению key найти значение value, причем алгоритм должен быть наиболее оптимальным, кто может подсказать в какую сторону двигатсья?

Comments

[Даша Циклаури]

ну только за O(N) в цикле, а если массив сортирован по key, то за O(logN)-бинарным поиском

[Ord EO]

Даша Циклаури, ну что б его отсортировать все равно нужно будет O(n) правильно я понимаю?

[longclaps]

Ord EO, оптимист, однако )

[Ord EO]

longclaps, почему оптимист?

[longclaps]

Ord EO, оптимист и невежда.

[Ord EO]

longclaps, попросил бы вас быть или более конструктивным, или проявлять свое ЧСВ в других местах.

[longclaps]

Ord EO, попросил бы вас читать ответы, раз уж задаёте вопросы, да еще и с привлечением О-нотации.

[Даша Циклаури]

Ord EO, его не нужно сортировать, имелось в виду, что данные в массив поступают последовательно относительно поля key, я же не знаю что там хранится, если к примеру timestamp и пушатся в реалтайме, то считай в сортированном виде.
А так просто за линейное время.

[Ord EO]

Даша Циклаури, а можно как-то этот многомерный массив перевести в хеш?

[Даша Циклаури]

Ord EO, можно, но тебе чтобы перевести его в хэш нужно пройтись по всем элементам, то есть O(N), или делать это в момент вставки, то есть заменить массив на словарь.

[Ord EO]

Даша Циклаури, в моем случае перевод массива в хэш будет достаточно, вот только не совсем понимаю как это сделать, т.е. ключ будет key: 1 а значение value: some_value441?
Или как это работает, не подскажете какой-нибудь ресурс где можно посмотреть как делаются подобные переводы?

[longclaps]

Как быстрее всего найти элемент в массиве

Ord EO, если это однократное действие, то перевести его в хэш - это пустая трата времени.

[Даша Циклаури]

Ord EO, ruby-for-beginners.rubymonstas.org/built_in_classe...

[Ord EO]

longclaps, нет действие многократное, возможно нужно будет совершать до нескольких миллионов поисков значения по ключу. Поэтому посчитал оптимальным перевести массив в хеш со сложностью O(n) а потом искать по нему много раз по O(1). Идея в этом, вот теперь ломаю голову как этот массив перевести в хеш.

[NaName]

Ord EO, в питоне есть словарь для этого (сложность поиска по ключу О(1)). может в руби есть такая же структура данных и не надо будет велосипедить?

[Ord EO]

NaName, так вот я не знаю, новичек в программировании, особенно в руби

[NaName]

Ord EO, https://docs.ruby-lang.org/en/2.0.0/Hash.html не читал?
по мотивам https://www.google.ru/search?q=ruby+dictionary&oq=...

[longclaps]

arr = [
    {key: 1, value: 'some_value441'},
    {key: 2, value: 'some_value212'},
    {key: 3, value: 'some_value33'},
    {key: 4, value: 'some_value44'},
]
p Hash[arr.reduce([]) {|r, d| r << [d[:key], d[:value]]}]

[Ord EO]

longclaps, то что нужно, правда синтаксис для моего уровня не понятен, но решение идеальное

Answer 1

[Сергей Блохин]

Array#find
Array#detect

items = [
  { name: :sergey, value: :qa },
  { name: :boris, value: :c_plus_plus_dev },
  { name: :vlad, value: :analytic },
  { name: :eugene, value: :marketer }
].detect { |item| item[:name] == :boris }[:value]

Comments

[h8nor]

Немного проще, - автор может не понимать :symbol. Видимо, поэтому N. Bekseitov удалил свой ответ.

k = 2
v = arr.detect { |item| item[:key] == k }[:value]