我有以下数组：
A = "cheddar".split(//) # ["c", "h", "e", "d", "d", "a", "r"]
B = "cheddaar".split(//) # ["c", "h", "e", "d", "d", "a", "a", "r"]
A 数组是 B 数组的子集。如果 A 数组有另一个“d”元素，它就不是一个子集。
我想比较并找出一个是否是另一个的子集，即使它们有重复。A - B 或 A & B 不会捕获重复项，它只是比较它们并发现它们匹配。所以我写了以下内容，它捕获了重复项：
B.each do |letter|
A.delete_at(A.index(letter)) rescue ""
end
p A.empty?
这是最好的方法还是可以优化？
不知道这是否真的比你的方法快，但它的运行时间应该是 O(N+M)，其中 N,M 是 a,b 的大小。（假设散列查找和插入是摊销 O(1) 这并不严格正确，因为散列通常是键大小的函数；尽管在示例中，所有键都是单个字符。）#index 方法的循环 #delete_at 具有实质性额外的数据运动，看起来可能是最坏的情况 O(N^2 * M)。
def ary_subset?(a,b) # true iff a is subset of b
a_counts = a.reduce(Hash.new(0)) { |m,v| m[v] += 1; m }
b_counts = b.reduce(Hash.new(0)) { |m,v| m[v] += 1; m }
a_counts.all? { |a_key,a_ct| a_ct <= b_counts[a_key] }
end
OP 要求最快的方法，所以我在这个 gist上创建了一个小基准。
我测试了 OP 的原始方法 (op_del)、我使用减少计数的版本 (ct)、重用计数数组的变体(ct_acc)，以及MultiSet 方法(mset)，编辑并添加了非常简洁的计数查找比较(slow_ct) 。针对 OP 的小数组输入示例 (s)、较大的基数集 10,000 (b) 以及针对大集 (sb) 的小集运行每个变体。（必须将大集合案例的迭代次数减少一个数量级，以使 _slow_ct_ 在合理的时间内完成。）这里的结果：
user system total real
s_op_del 1.850000 0.000000 1.850000 ( 1.853931)
s_ct 2.260000 0.000000 2.260000 ( 2.264028)
s_ct_acc 1.700000 0.000000 1.700000 ( 1.706881)
s_mset 5.460000 0.000000 5.460000 ( 5.484833)
s_slow_ct 1.720000 0.000000 1.720000 ( 1.731367)
b_op_del 0.310000 0.000000 0.310000 ( 0.312804)
b_ct 0.120000 0.000000 0.120000 ( 0.123329)
b_ct_acc 0.100000 0.000000 0.100000 ( 0.101532)
b_mset 0.310000 0.000000 0.310000 ( 0.319697)
b_slow_ct 82.910000 0.000000 82.910000 ( 83.013747)
sb_op_del 0.710000 0.020000 0.730000 ( 0.734022)
sb_ct 0.050000 0.000000 0.050000 ( 0.054416)
sb_ct_acc 0.040000 0.000000 0.040000 ( 0.059032)
sb_mset 0.110000 0.000000 0.110000 ( 0.117027)
sb_slow_ct 0.010000 0.000000 0.010000 ( 0.011287)
减少计数，重用计数累加器是明显的赢家。Multiset 的速度慢得令人失望。
如果我正确理解要求，您可以使用multiset gem。
require 'multiset'
a = Multiset.new "cheddar".split(//)
b = Multiset.new "cheddaar".split(//)
a.subset? b #=> true
如果我没记错的话，你的解决方案是 O(n^2) 这个有点麻烦，但效率更高，至少对于大输入（这是 O(n)）。它可能需要更多的工作......
def is_subset?(a, b)
letters = Hash.new(0)
a.each_char{|x| letters[x] += 1}
b.each_char{|x| letters[x] -= 1}
letters.values.all?{|v| v >= 0 }
end
编辑：更高效一点：
def is_subset?(a, b)
letters = Hash.new(0)
a.each_char{|x| letters[x] += 1}
b.each_char.all?{|x| (letters[x] -= 1) > 0}
end
绝对想在这里利用枚举器——最好的方法是使用 group_by 并比较每个字母出现的次数：
def subset?(a, b)
a = a.each_char.group_by { |char| char }
b = b.each_char.group_by { |char| char }
a.each_key.all? do |letter|
b[letter] && a[letter].size < b[letter].size
end
end
因此，如果我们将哈希查找算作 O(1) 操作，那么这是一个 O(m + n) 算法
试试这个：
class String
def subset_of?(str)
e2 = str.each_char
c2 = c2p = nil
each_char do |c1|
c2p, c2 = c2, e2.next
next if c2 == c1
c2p, c2 = c2, e2.next until (c2 != c2p) # move until we exclude duplicates
return false if c2 != c1
end
true
rescue StopIteration
false
end
end
测试功能：
>> "chedddar".subset_of?("cheddaaaaaar")
=> false
>> "cheddar".subset_of?("cheddaaaaaar")
=> true
>> "cheddar".subset_of?("cheddaaaaaarkkkk")
=> true
>> "chedddar".subset_of?("cheddar")
=> false
>> "chedddar".subset_of?("chedd")
=> false
编辑 1
根据提供的附加信息更新了解决方案。
class String
def subset_of?(str)
h1, h2 = [self, str].map {|s| s.each_char.reduce(Hash.new(0)){|h, c| h[c] += 1; h}}
h1.all?{|c, k| h2[c] >= k}
end
end
几周前发布了一个类似的问题，我得到了接受的答案，例如：
def is_subset?(a,b)
!a.find{|x| a.count(x) > b.count(x)}
end
基准更新
require 'benchmark'
def random_char
('a'..'z').to_a.sample
end
A = 8.times.map{random_char}
B = 8.times.map{random_char}
def ary_subset?(a,b) # true iff a is subset of b
a_counts = a.reduce(Hash.new(0)) { |m,v| m[v] += 1; m }
b_counts = b.reduce(Hash.new(0)) { |m,v| m[v] += 1; m }
a_counts.all? { |a_key,a_ct| a_ct <= b_counts[a_key] }
end
Benchmark.bm do |x|
x.report('me') {100000.times{is_subset?(A,B)}}
x.report('dbenhur'){100000.times{ary_subset?(A,B)}}
end
user system total real
me 0.375000 0.000000 0.375000 ( 0.384022)
dbenhur 2.558000 0.000000 2.558000 ( 2.550146)
先把骗子去掉怎么样？
(A.uniq - B.uniq).empty?