arrays - 查找两个数组之间的(多集)差异

Question

给定数组(比如行向量)A 和 B，我如何找到一个数组 C，使得合并 B 和 C 得到 A？

例如给定

A = [2, 4, 6, 4, 3, 3, 1, 5, 5, 5];
B = [2, 3, 5, 5];

然后

C = multiset_diff(A, B) % Should be [4, 6, 4, 3, 1, 5]

(结果的顺序在这里无关紧要)。

对于同一个A，如果B = [2, 4, 5]，那么结果应该是[6, 4, 3, 3, 1, 5, 5]。

(由于 A 中有两个 4，B 中有一个 4，结果 C 应该有 2 - 1 = 1 4在其中。对于其他值也是如此。)

PS:请注意，setdiff 会删除 2、3 和 5 的所有实例，而在这里，无论它们在 B 中出现多少次，都需要删除它们。

---

性能:我在本地运行了一些 quick-n-dirty 基准测试，以下是供将来引用的结果:

• @heigele 的嵌套循环方法最适用于小长度的 A(比如最多 N = 50 个左右的元素)。与下一个最佳方法相比，它对小型 (N=20) A 的效果提高了 3 倍，对中型 (N=50) A 的效果提高了 1.5 倍- 即:

• @obchardon 基于histc 的方法。当 A 的大小 N 开始为 100 及以上时，这是表现最好的。例如，当 N = 200 时，这比上述嵌套循环方法好 3 倍。

@matt 的 for+find 方法对于小 N 的性能与 histc 方法相当，但对于大 N 的性能会迅速下降(这是有道理的，因为整个 C == B(x) 比较是运行每个迭代)。

(在撰写本文时，其他方法要么慢几倍，要么无效。)

Answer 1

还有一种使用histc函数的方法:

A = [2, 4, 6, 4, 3, 3, 1, 5, 5, 5];
B = [2, 3, 5, 5];

uA  = unique(A);
hca = histc(A,uA); 
hcb = histc(B,uA);
res = repelem(uA,hca-hcb)

我们简单地根据向量A的唯一值计算每个向量重复元素的数量，然后我们使用repelem来创建结果。

此解决方案不保留初始顺序，但对您来说似乎不是问题。

我使用 histc 来实现 Octave 兼容性，但这个函数已被弃用，因此您也可以使用 histcounts