我想(快速)确定一个数组是否包含另一个数组的所有元素,考虑到数组可能有重复的元素。
因此,我尝试了这样的事情:
alice = %w(a a a b)
bob = %w(a a b c d e)
alice & bob => ["a", "b"]
alice - bob => []
但我想要的是一个运算符,它可以让我确定 bob 不包括 alice 的所有元素,因为 bob 没有足够的“a”字符。
可能最容易计算每个元素出现的频率,因此我们不必太担心跟踪我们有/没有计算过的重复项:
alice_counts = alice.each_with_object(Hash.new(0)) { |o, h| h[o] += 1 }
#=> {"a"=>3, "b"=>1}
bob_counts = bob.each_with_object(Hash.new(0)) { |o, h| h[o] += 1 }
#=> {"a"=>2, "b"=>1, "c"=>1, "d"=>1, "e"=>1}
然后检查每个键 inalice_counts
是否具有等于或大于 in 的值bob_counts
:
alice_counts.all? { |k, v| bob_counts[k] >= v }
#=> false
alice.select{|x| alice.count(x) > bob.count(x)}
更新 设置基准:
require 'benchmark'
def subset_multivalue?(a, b)
bb = b.clone
a.each do |e|
i = bb.index(e)
if i
bb.delete_at(i)
else
return false
end
end
return true
end
def subset_multivalue2?(a, b)
a.find{|x| a.count(x) > b.count(x)}
end
def subset_multivalue3?(alice, bob)
alice_counts = alice.each_with_object(Hash.new(0)) { |o, h| h[o] += 1 }
bob_counts = bob.each_with_object(Hash.new(0)) { |o, h| h[o] += 1 }
alice_counts.all? do |k, v|
bob_counts.has_key?(k) && bob_counts[k] >= v
end
end
alice = %w(a a a b)
bob = %w(a a b c d e)
Benchmark.bm do |x|
x.report("dave:") do
1000000.times do
subset_multivalue?(alice, bob)
end
end
x.report("me:") do
1000000.times do
subset_multivalue2?(alice,bob)
end
end
x.report("andrew:") do
1000000.times do
subset_multivalue3?(alice,bob)
end
end
end
结果:
user system total real
dave: 15.054000 0.000000 15.054000 ( 15.108864)
me: 11.529000 0.031000 11.560000 ( 11.689669)
andrew: 65.036000 0.047000 65.083000 ( 67.463859)
Enumerable#group_by() 将是一个选择。
alice = %w(a a a b)
bob = %w(a a b c d e)
alice_group = alice.group_by{|a| a}.map{|k,v| [k ,v.length]}
#=> [["a", 3], ["b", 1]]
bob_group = bob.group_by{|a| a}.map{|k,v| [k ,v.length]}
#=> [["a", 2], ["b", 1], ["c", 1], ["d", 1], ["e", 1]]
alice_group-bob_group
#=> [["a", 3]]
bob_group-alice_group
#=>[["a", 2], ["c", 1], ["d", 1], ["e", 1]]
我想我正在解决这个问题:
def subset_multivalue?(a, b)
bb = b.clone
a.each do |e|
i = bb.index(e)
if i
bb.delete_at(i)
else
return false
end
end
return true
end
我意识到这不是很红宝石,但它似乎完成了这项工作。