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

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 中出现多少次，都需要删除它们。

性能：我运行在本地进行了一些快速的基准测试，这里是供将来参考的结果：

@heigele 的嵌套循环方法对于 A 的小长度（比如最多 N = 50 个左右的元素）表现最佳。与下一个最佳方法相比，它对小型 (N=20) As 的性能提高了 3 倍，对中型 (N=50) As 的性能提高了 1.5 倍 - 即：
@obchardon 基于 histc 的方法。当 A 的大小 N 开始为 100 及以上时，这是表现最好的。例如，当 N = 200.

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

（其他方法要么慢了好几倍，要么在写的时候无效。）

Answer 1

您可以使用 ismember 的第二个输出来查找 B 的元素在 A 中的索引，并使用 diff 删除重复项：

此答案假设 B 已经排序。如果不是这种情况，B 必须在执行上述解决方案之前进行排序。

第一个例子：

A = [2, 4, 6, 4, 3, 3, 1, 5, 5, 5];
B = [2, 3, 5, 5];
%B = sort(B); Sort if B is not sorted.
[~,col] = ismember(B,A);
indx = find(diff(col)==0);
col(indx+1) = col(indx)+1;
A(col) = [];
C = A;

>>C

4     6     4     3     1     5

第二个例子：

A = [2, 4, 6, 4, 3, 3, 1, 5, 5, 5];
B = [2, 4, 5, 5];
%B = sort(B); Sort if B is not sorted.
[~,col] = ismember(B,A);
indx = find(diff(col)==0);
col(indx+1) = col(indx)+1;
A(col) = [];
C = A;
>>C

6     4     3     3     1     5

Answer 2

我不喜欢循环，但是对于 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

Answer 3

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

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 4

还有一种使用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

Answer 5

受到 Matt 的强烈启发，但在我的机器上速度提高了 40%：

function A = multiDiff(A,B)
for j = 1:numel(B)
    for i = 1:numel(A)
        if A(i) == B(j)
            A(i) = [];
            break;
        end
    end
end
end

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

Finding (multiset) difference between two arrays

arrays

matlab

multiset