Ruby - 优化两个数组重复项的比较

Question

我有以下数组:

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?

这是最好的方法还是可以优化？

Answer 1

不知道这是否真的比您的方法更快，但它的运行时间应该是 O(N+M)，其中 N、M 是 a、b 的大小。 (假设散列查找和插入是摊销的 O(1) 这不是严格正确的，因为散列通常是键大小的函数；尽管在示例中，所有键都是单个字符。)您的循环 #delete_at of#index 方法有实质性的额外的数据移动，看起来可能是最坏的情况 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 要求最快的方法，所以我在 this gist 上创建了一个小的微基准测试.

我测试了 OP 的原始方法 (op_del)、我使用减少计数的版本 (ct) 和变体 where the count array is reused (ct_acc)，以及 MultiSet approach (mset)，编辑 并添加了 very concise find of count comparisons (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 慢得令人失望。