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(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)
4

14 回答 14

44

如果您只需要成员资格，请考虑使用Set：

放

Set实现了一组无重复的无序值。这是 Array 的直观互操作设施和 Hash 的快速查找的混合体。

Set易于与Enumerable对象一起使用（实现 each）。除了集合和数组之外，大多数初始化方法和二元运算符都接受通用的Enumerable对象。可以使用该 方法将 Enumerable对象转换为Set 。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

[...]

公共类方法

新的（枚举 = 无）

创建一个包含给定可枚举对象的元素的新集合。

如果给定一个块，则枚举的元素由给定的块预处理。

于 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。拥有一个指向所有nils 的 Hash 是愚蠢的。转换也是一个简单的过程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

Rampion 打败了我。设置可能是答案。

你可以做：

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

我认为chrissear关于使用分配而不是创造的观点很棒。不过，为了让整个事情更像 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
于 2009-01-04T15:24:02.730 回答
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];快一点。两者的速度都是 的两倍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 回答
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

在我的桌面上花费一秒钟左右。

于 2010-08-13T14:34:47.327 回答
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”存储在缓存中（否则为零）。这允许延迟加载到缓存中，以防万一您不使用每个元素。

于 2009-01-04T15:46:30.873 回答
0

如果您的哈希是，这将保留 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}
于 2014-04-21T12:17:46.500 回答