时间戳

首页 > 解决方案 > 查找（多集）两个数组之间的差异

arrays - 查找（多集）两个数组之间的差异

问题描述

给定数组（比如行向量）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 中有两个4s，4B 中有一个，因此结果 C 中应该有 2 - 1 = 1。4对于其他值也是如此。）

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

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

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

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

标签： arraysmatlabmultiset

解决方案

我不喜欢循环，但对于随机扰动，A这是我想出的最好的方法。

C = A;
for x = 1:numel(B)
C(find(C == B(x), 1, 'first')) = [];
end

我很好奇查看不同顺序A对解决方案方法的影响，所以我设置了一个这样的测试：

Ctruth = [1 3 3 4 5 5 6];
for testNumber = 1:100
    Atest = A(randperm(numel(A)));
    C = myFunction(Atest,B);
    C = sort(C);
    assert(all(C==Ctruth));
end

推荐阅读