Конвертировать массив в хеш индекса в Ruby

Question

У меня есть массив, и я хочу создать хеш, чтобы я мог быстро спросить «есть ли 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)

Answer 1

Если все, что вам нужно для хеширования, это членство, рассмотрите возможность использования Set:

Установить

Set реализует коллекцию неупорядоченных значений без дубликаты. Это гибрид интуитивного взаимодействия Array объекты и быстрый поиск Хэша.

Set прост в использовании с Enumerable objects (реализующий each). Большинство методов инициализатора и бинарных операторов принимают универсальные перечисляемые объекты помимо наборов и массивов. Перечислимый объект можно преобразовать в Установить , используя to_set метод.

Set использует Hash в качестве хранилища, поэтому вы должны отметить следующие моменты:

• Равенство элементов определяется согласно 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)

Создает новый набор, содержащий элементы указанного перечислимого объект.

Если указан блок, элементы enum предварительно обрабатываются данный блок.

Answer 2

попробуйте это:

a=[1,2,3]
Hash[a.zip]

Answer 3

Вы можете сделать этот очень удобный трюк:

Hash[*[1, 2, 3, 4].map {|k| [k, nil]}.flatten]
=> {1=>nil, 2=>nil, 3=>nil, 4=>nil}

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

Вы должны рассмотреть возможность использования набора для начала вместо массива, чтобы преобразование никогда не требовалось.

Answer 5

Я вполне уверен, что не существует единого умного способа создать этот хэш. Я хотел бы просто быть явным и заявить, что я делаю:

hash = {}
array.each{|x| hash[x] = nil}

Это не выглядит особенно элегантно, но понятно и выполняет свою работу.

FWIW, ваше первоначальное предложение (по крайней мере, под Ruby 1.8.6) не работает. Я получаю сообщение об ошибке «ArgumentError: нечетное количество аргументов для хэша». Хеш. [] Ожидает буквальный, ровный список значений:

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)

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

Answer 6

Рэмпион победил меня в этом. Сет может быть ответом.

Вы можете сделать:

require 'set'
set = array.to_set
set.include?(x)

Answer 7

Ваш способ создания хэша выглядит хорошо. У меня была грязь в irb, и это другой способ

>> [1,2,3,4].inject(Hash.new) { |h,i| {i => nil}.merge(h) }
=> {1=>nil, 2=>nil, 3=>nil, 4=>nil}

Answer 8

Я думаю, что chrismear замечает, что использование присваивания над созданием великолепно. Тем не менее, чтобы сделать все это немного более похожим на Ruby, я мог бы предложить назначить что-то другое , чем 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

Answer 9

Если вас не беспокоит, какие значения хеша

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

Занимает секунду или около того на моем рабочем столе.

Answer 10

Проведение некоторого сравнительного анализа предложений пока что дает chrismear и Gaius основанное на назначении хэш-создание немного быстрее, чем мой метод карты (и назначение nil немного быстрее, чем назначение true). Предложение мтяки и 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