查找两个数组之间的(multiset)差异

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].

(由于4A中有两个s,4B 中有一个,因此结果C中应该有2 - 1 = 1.4其他值类似.)

PS:请注意,这setdiff将删除2,3和5的所有实例,而在这里它们需要被删除,但是它们出现在B中很多次.

---

性能:我在本地运行了一些快速的基准测试,以下是未来参考的结果:

• @ heigele的嵌套循环方法对于小长度的A(最多N = 50左右的元素)表现最佳.与下一个最佳方法相比,它对于小(N = 20)As来说好3倍,对于中等大小(N = 50)As 好1.5倍- 这是:

• @ obchardon的histc方法.当A的大小N开始为100及以上时,这是最好的.例如,当N = 200时,这比上面的嵌套循环方法好3倍.

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

(其他方法在写作时要慢几倍或无效.)

Answer 1

这是一种矢量化的方式。内存效率低下，主要是为了好玩：

tA = sum(triu(bsxfun(@eq, A, A.')), 1);
tB = sum(triu(bsxfun(@eq, B, B.')), 1);
result = setdiff([A; tA].', [B; tB].', 'rows', 'stable');
result = result(:,1).';

这个想法是通过用出现次数标记每个条目来使其唯一。向量变成 2 列矩阵，setdiff应用该'rows'选项，然后从结果中删除标签。

Answer 2

使用该函数的另一种方法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 来创建结果。

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

我用于histcOctave 兼容性，但此函数已弃用，因此您也可以使用histcounts