Преобразование массива в хэш индекса в Ruby
У меня есть массив, и я хочу сделать хеш, чтобы я мог быстро спросить "есть X в массиве?".
В perl существует простой (и быстрый) способ сделать это:
my @array = qw( 1 2 3 );
my %hash;
@hash{@array} = undef;
Это генерирует хэш, который выглядит так:
{
1 => undef,
2 => undef,
3 => undef,
}
Лучшее, что я придумал в Ruby, это:
array = [1, 2, 3]
hash = Hash[array.map {|x| [x, nil]}]
который дает:
{1=>nil, 2=>nil, 3=>nil}
Есть ли лучший способ Ruby?
РЕДАКТИРОВАТЬ 1
Нет, Array.include? это не очень хорошая идея. Его медленный. Он выполняет запрос в O (n) вместо O (1). В моем массиве примеров было три элемента для краткости; предположим, что у фактического есть миллион элементов. Позвольте сделать небольшой бенчмаркинг:
#!/usr/bin/ruby -w
require 'benchmark'
array = (1..1_000_000).to_a
hash = Hash[array.map {|x| [x, nil]}]
Benchmark.bm(15) do |x|
x.report("Array.include?") { 1000.times { array.include?(500_000) } }
x.report("Hash.include?") { 1000.times { hash.include?(500_000) } }
end
Выдает:
user system total real
Array.include? 46.190000 0.160000 46.350000 ( 46.593477)
Hash.include? 0.000000 0.000000 0.000000 ( 0.000523)
Ответы
Ответ 1
Если вам нужен хэш для членства, используйте Set
:
Set
Set реализует набор неупорядоченных значений без дубликаты. Это гибрид интуитивного взаимодействия Array средства и быстрый поиск Hash.
Set прост в использовании с Enumerable объектов (реализация each
). Большинство методов инициализации и двоичных операторов принимают generic Enumerable объекты, кроме наборов и массивов. Enumerable объект может быть преобразован в Set, используя to_set
.
Set использует Хэш как хранилище, поэтому вы должны отметить следующие моменты:
- Равенство элементов определяется в соответствии с
Object#eql?
и Object#hash
. - Set предполагает, что идентичность каждого элемента не изменяется при сохранении. Изменение элемента набора приведет к тому, что ненадежное состояние.
- Когда строка должна быть сохранена, вместо этого сохраняется замороженная копия строки, если исходная строка уже не заморожена.
Сравнение
Операторы сравнения <
, >
, <=
и >=
реализованы как сокращенную для методов {proper _,} {subset?, superset?}. Однако Оператор <=>
намеренно исключен, поскольку не каждая пара множества сопоставимы. ({x, y} против {x, z}, например)
Пример
require 'set'
s1 = Set.new [1, 2] # -> #<Set: {1, 2}>
s2 = [1, 2].to_set # -> #<Set: {1, 2}>
s1 == s2 # -> true
s1.add("foo") # -> #<Set: {1, 2, "foo"}>
s1.merge([2, 6]) # -> #<Set: {1, 2, "foo", 6}>
s1.subset? s2 # -> false
s2.subset? s1 # -> true
[...]
Общие методы класса
new (enum = nil)
Создает новый набор, содержащий элементы данного перечислимого объект.
Если задан блок, элементы перечисления предварительно обрабатываются данный блок.
Ответ 2
попробуйте следующее:
a=[1,2,3]
Hash[a.zip]
Ответ 3
Вы можете сделать этот очень удобный трюк:
Hash[*[1, 2, 3, 4].map {|k| [k, nil]}.flatten]
=> {1=>nil, 2=>nil, 3=>nil, 4=>nil}
Ответ 4
Если вы хотите быстро спросить "есть X в массиве?" вы должны использовать Array#include?
.
Изменить (в ответ на добавление в OP):
Если вы хотите быстро найти время, используйте Set. Наличие хэша, указывающего на все nil
, глупо. Конверсия - это простой процесс с Array#to_set
.
require 'benchmark'
require 'set'
array = (1..1_000_000).to_a
set = array.to_set
Benchmark.bm(15) do |x|
x.report("Array.include?") { 1000.times { array.include?(500_000) } }
x.report("Set.include?") { 1000.times { set.include?(500_000) } }
end
Результаты на моей машине:
user system total real
Array.include? 36.200000 0.140000 36.340000 ( 36.740605)
Set.include? 0.000000 0.000000 0.000000 ( 0.000515)
Вы должны просто использовать набор для начала, вместо массива, чтобы преобразование никогда не было необходимым.
Ответ 5
Я абсолютно уверен, что не существует одноразового умного способа построения этого хэша. Моя склонность состояла в том, чтобы просто быть явным и заявить, что я делаю:
hash = {}
array.each{|x| hash[x] = nil}
Это выглядит не очень элегантно, но ясно, и делает работу.
FWIW, ваше первоначальное предложение (по крайней мере, по версии Ruby 1.8.6), похоже, не работает. Я получаю ошибку "ArgumentError: нечетное число аргументов для Hash". Hash. [] Ожидает буквальный, даже отсроченный список значений:
Hash[a, 1, b, 2] # => {a => 1, b => 2}
поэтому я попытался изменить свой код на:
hash = Hash[*array.map {|x| [x, nil]}.flatten]
но производительность очень тяжелая:
#!/usr/bin/ruby -w
require 'benchmark'
array = (1..100_000).to_a
Benchmark.bm(15) do |x|
x.report("assignment loop") {hash = {}; array.each{|e| hash[e] = nil}}
x.report("hash constructor") {hash = Hash[*array.map {|e| [e, nil]}.flatten]}
end
дает
user system total real
assignment loop 0.440000 0.200000 0.640000 ( 0.657287)
hash constructor 4.440000 0.250000 4.690000 ( 4.758663)
Если я здесь что-то не хватает, простой цикл назначения кажется самым ясным и эффективным способом для создания этого хэша.
Ответ 6
Чемпион победил меня. Набор может быть ответом.
Вы можете сделать:
require 'set'
set = array.to_set
set.include?(x)
Ответ 7
Ваш способ создания хэша выглядит хорошо. У меня была гадость в irb, и это еще один способ
>> [1,2,3,4].inject(Hash.new) { |h,i| {i => nil}.merge(h) }
=> {1=>nil, 2=>nil, 3=>nil, 4=>nil}
Ответ 8
Я думаю, что chrismear указывает на использование назначения над созданием. Чтобы сделать все это немного более рубиновым, я мог бы предложить присваивать каждому элементу что-то отличное от nil
:
hash = {}
array.each { |x| hash[x] = 1 } # or true or something else "truthy"
...
if hash[376] # instead of if hash.has_key?(376)
...
end
Проблема с назначением nil
заключается в том, что вы должны использовать has_key?
вместо []
, так как []
дает вам nil
(ваше значение маркера), если Hash
не имеет указанный ключ. Вы можете обойти это, используя другое значение по умолчанию, но зачем проходить дополнительную работу?
# much less elegant than above:
hash = Hash.new(42)
array.each { |x| hash[x] = nil }
...
unless hash[376]
...
end
Ответ 9
Возможно, я неправильно понимаю цель здесь; Если вы хотите знать, есть ли X в массиве, почему бы не сделать array.include? ( "X" )?
Ответ 10
Выполнение некоторых бенчмаркинга по предложениям пока дает, что хэш-макет и создание привязки на основе Gaius немного быстрее, чем мой метод карты (а назначение nil немного быстрее, чем назначение true). mtyaka и rampion. Предложение на 35% медленнее, чтобы создать.
Что касается поисковых запросов, hash.include?(x)
- это очень маленькое количество быстрее, чем hash[x]
; оба они в два раза быстрее, чем set.include?(x)
.
user system total real
chrismear 6.050000 0.850000 6.900000 ( 6.959355)
derobert 6.010000 1.060000 7.070000 ( 7.113237)
Gaius 6.210000 0.810000 7.020000 ( 7.049815)
mtyaka 8.750000 1.190000 9.940000 ( 9.967548)
rampion 8.700000 1.210000 9.910000 ( 9.962281)
user system total real
times 10.880000 0.000000 10.880000 ( 10.921315)
set 93.030000 17.490000 110.520000 (110.817044)
hash-i 45.820000 8.040000 53.860000 ( 53.981141)
hash-e 47.070000 8.280000 55.350000 ( 55.487760)
Код бенчмаркинга:
#!/usr/bin/ruby -w
require 'benchmark'
require 'set'
array = (1..5_000_000).to_a
Benchmark.bmbm(10) do |bm|
bm.report('chrismear') { hash = {}; array.each{|x| hash[x] = nil} }
bm.report('derobert') { hash = Hash[array.map {|x| [x, nil]}] }
bm.report('Gaius') { hash = {}; array.each{|x| hash[x] = true} }
bm.report('mtyaka') { set = array.to_set }
bm.report('rampion') { set = Set.new(array) }
end
hash = Hash[array.map {|x| [x, true]}]
set = array.to_set
array = nil
GC.start
GC.disable
Benchmark.bmbm(10) do |bm|
bm.report('times') { 100_000_000.times { } }
bm.report('set') { 100_000_000.times { set.include?(500_000) } }
bm.report('hash-i') { 100_000_000.times { hash.include?(500_000) } }
bm.report('hash-e') { 100_000_000.times { hash[500_000] } }
end
GC.enable
Ответ 11
Если вы не обеспокоены тем, что значения хэша
irb(main):031:0> a=(1..1_000_000).to_a ; a.length
=> 1000000
irb(main):032:0> h=Hash[a.zip a] ; h.keys.length
=> 1000000
Занимает секунду или около того на моем рабочем столе.
Ответ 12
Если вы ищете эквивалент этого кода Perl:
grep {$_ eq $element} @array
Вы можете просто использовать простой код Ruby:
array.include?(element)
Ответ 13
Здесь аккуратный способ кэширования запросов с помощью Hash:
a = (1..1000000).to_a
h = Hash.new{|hash,key| hash[key] = true if a.include? key}
В значительной степени он создает конструктор по умолчанию для новых значений хэша, а затем сохраняет "true" в кеше, если он в массиве (в противном случае - в противном случае). Это позволяет ленивую загрузку в кеш, на всякий случай, если вы не используете каждый элемент.
Ответ 14
Это сохраняет 0, если ваш хэш был [0,0,0,1,0]
hash = {}
arr.each_with_index{|el, idx| hash.merge!({(idx + 1 )=> el }) }
Возвращает:
# {1=>0, 2=>0, 3=>0, 4=>1, 5=>0}