44

私は配列を持っています。ハッシュを作成して、「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(1) ではなく O(n) でクエリを実行します。私の例の配列には、簡潔にするために 3 つの要素がありました。実際のものには百万の要素があると仮定します。少しベンチマークを行いましょう。

#!/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)
4

14 に答える 14

44

ハッシュが必要なのはメンバーシップだけである場合は、次の使用を検討してSetください。

設定

Setは、重複のない順序付けられていない値のコレクションを実装します。これは、Array の直感的な相互操作機能と Hash の高速ルックアップのハイブリッドです。

SetはEnumerableオブジェクト (実装 each) で簡単に使用できます。初期化メソッドと二項演算子のほとんどは、セットと配列以外に汎用のEnumerableオブジェクトを受け入れます。Enumerableオブジェクトは、 メソッドを使用し てSetに変換できます。to_set

Setは Hash をストレージとして使用するため、次の点に注意する必要があります。

  • 要素の等価性は、 および に従って決定されObject#eql?ますObject#hash。
  • Set は、格納中に各要素の ID が変更されないことを前提としています。セットの要素を変更すると、セットが信頼できない状態になります。
  • 文字列を保存する場合、元の文字列が既に凍結されていない限り、代わりに文字列の凍結されたコピーが保存されます。

比較

比較演算子<、>、<=および>=は、{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(列挙型 = nil)

指定された列挙可能なオブジェクトの要素を含む新しいセットを作成します。

ブロックが指定されている場合、enum の要素は指定されたブロックによって前処理されます。

于 2009-01-04T15:45:07.663 に答える
24

これを試してください：

a=[1,2,3]
Hash[a.zip]
于 2013-01-06T12:34:35.383 に答える
14

あなたはこの非常に便利なトリックを行うことができます：

Hash[*[1, 2, 3, 4].map {|k| [k, nil]}.flatten]
=> {1=>nil, 2=>nil, 3=>nil, 4=>nil}
于 2012-08-02T07:27:48.077 に答える
9

「X は配列に含まれていますか?」とすぐに聞きたい場合は、を使用する必要がありますArray#include?。

編集（OPへの追加に応じて）：

検索時間を短縮したい場合は、Set を使用します。すべての s を指すハッシュを持つこと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)

変換が不要になるように、配列の代わりにセットを使用することを検討する必要があります。

于 2009-01-04T08:08:39.643 に答える
6

このハッシュを構築するためのワンショットの巧妙な方法はないと確信しています。私の傾向は、私がやっていることを明確にして述べることです：

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)

ここで何かが欠けていない限り、単純な割り当てループが、このハッシュを構築する最も明確で効率的な方法のようです。

于 2009-01-04T14:16:18.263 に答える
5

ランピオンは私を打ち負かしました。セットが答えかもしれません。

できるよ：

require 'set'
set = array.to_set
set.include?(x)
于 2009-01-04T16:01:02.530 に答える
4

ハッシュを作成する方法はよさそうです。私はirbでうんざりしていましたが、これは別の方法です

>> [1,2,3,4].inject(Hash.new) { |h,i| {i => nil}.merge(h) }
=> {1=>nil, 2=>nil, 3=>nil, 4=>nil}
于 2009-01-04T09:24:48.693 に答える
2

作成よりも割り当てを使用することに関する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?[][]nilHash

# much less elegant than above:
hash = Hash.new(42)
array.each { |x| hash[x] = nil }
...
unless hash[376]
  ...
end
于 2009-01-04T15:24:02.730 に答える
1

ハッシュ値が何であるか気にしない場合

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

デスクトップで1秒ほどかかります。

于 2010-08-13T14:34:47.327 に答える
1

ここでの目標を誤解しているのかもしれません。X が配列に含まれているかどうかを知りたければ、なぜ array.include?("X") を実行しないのでしょうか?

于 2009-01-04T08:08:55.663 に答える
1

これまでの提案でいくつかのベンチマークを行うと、chrismear と Gaius の代入ベースのハッシュ作成が、私の map メソッドよりもわずかに高速であることがわかります (nil の代入は、true の代入よりもわずかに高速です)。mtyaka と rampion の Set 提案は、作成が約 35% 遅くなります。

ルックアップに関してhash.include?(x)は、 よりもわずかに高速ですhash[x]。どちらも の 2 倍の速さ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
于 2009-01-05T08:29:16.433 に答える
0

この Perl コードに相当するものを探している場合:

grep {$_ eq $element} @array

シンプルな Ruby コードを使用できます。

array.include?(element)
于 2009-01-04T08:18:52.337 に答える
0

ハッシュを使用してルックアップをキャッシュする適切な方法を次に示します。

a = (1..1000000).to_a
h = Hash.new{|hash,key| hash[key] = true if a.include? key}

それが行うことのほとんどは、新しいハッシュ値のデフォルトのコンストラクターを作成し、それが配列にある場合はキャッシュに「true」を格納することです (そうでない場合は nil)。これにより、すべての要素を使用しない場合に備えて、キャッシュへの遅延読み込みが可能になります。

于 2009-01-04T15:46:30.873 に答える