代码之家 › 专栏 › 技术社区 › Sundar R

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

multiset matlab arrays

Sundar R · 技术社区 · 7 年前

例如,给定

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]

(因为有两个 4 在一和一中 4个 4个 在里面。与其他值类似。)

注:注意 setdiff 将删除2、3和5的所有实例,而这里只需要删除它们在B中出现的次数。

:我在本地运行了一些quick-n-dirty基准测试,以下是结果供将来参考:

A s、中型(N=50)的1.5倍 一个
@奥巴查顿氏 histc -基于方法。当A的大小N开始大于等于100时,这是性能最好的一个。例如,当N=200时,这比上面的嵌套循环方法要好3倍。

@matt的for+find方法与hisc方法对于小N的性能相当,但是对于大N的性能迅速下降(这是有意义的,因为 C == B(x)

(其他方法在编写时可能会慢几倍或无效。)

5 回复 | 直到 7 年前

obchardon 7 年前

另一种方法是使用 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创建结果。

这个解决方案不保留最初的顺序,但对您来说似乎不是问题。

我用为了兼容八度音阶,但不推荐使用此函数,因此也可以使用 histcounts

Luis Mendo 7 年前

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).';

这样做的目的是通过在每个条目上标记一个出现编号来使其唯一。向量变成两列矩阵, setdiff 应用于 'rows'

Matt 7 年前

我不喜欢循环,但喜欢 A 这是我想出的最好的办法。

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

我很好奇地想看看在解决方案方法上,我设置了这样一个测试:

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

Paolo 7 年前

ismember 查找其中元素的索引 B 在 A ,和 diff 要删除重复项:

这个答案假设 乙 乙 必须在执行上述解决方案之前进行排序。

对于第一个示例:

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

Christian Heigele 7 年前

灵感来自马特,但在我的机器上速度快了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