在 Matlab 中查找反转次数

Question

在通过分而治之的方法查找数组中的反转次数的过程中，我遇到了实现合并步骤的问题：我们有两个排序数组，任务是计算第一个数组的元素大于第二个数组的元素。

例如，如果数组是 v1 = [1,2,4], v2 = [0,3,5]，我们应该计算 4 个反转。

所以，我在 Matlab 中实现了合并步骤，但我仍然遇到如何使其更快的问题。

首先，我尝试了暴力方法

tempArray = arrayfun(@(x) length(find(v2>x)), v1)

它和下一个片段一样运行太慢

l = 1;
s = 0;
for ii = 1:n1 
    while(l <= n2 && p1(ii)>p2(l))
        l = l + 1;
    end
    s = s + l - 1;
end

有什么好的方法可以让它更快？

编辑

感谢您的回答和方法！我为我的进一步工作找到了有趣的东西。

这是片段，应该是我试过最快的

n1 = length(vec1); n2 = length(vec2);

uniteOne = [vec1, vec2];

[~, d1] = sort(uniteOne);
[~, d2] = sort(d1); % Find ind-s IX such that B(IX) = A, where B = sort(A)
vec1Slice = d2(1:n1);
finalVecToSolve = vec1Slice - (1:n1);

sum(finalVecToSolve)

Answer 1

另一种暴力方法 bsxfun -

sum(reshape(bsxfun(@gt,v1(:),v2(:).'),[],1))

或者，正如@thewaywewalk 在评论中提到的那样，使用 nnz 替换 summing -

nnz(bsxfun(@gt,v1(:),v2(:).'))

Answer 2

一种明确的方法可能是减去您的元素并查看它们在哪里为负数：

v1 = [1,2,4];
v2 = [0,3,5];

mydiffs = zeros(length(v1), length(v2));
for ii = 1:length(v1)
    mydiffs(ii,:) = v2 - v1(ii);
end

test = sum(reshape(mydiffs,[],length(v1)*length(v2)) < 0)

哪个returns:

test =

     4

这不是最好的方法，而且肯定有改进的余地。我也怀疑它是否比 bsxfun 方法更快。

Edit1：一种 arrayfun 方法，看起来更整洁但不一定比循环更快。

test = arrayfun(@(x) (v2 - x) < 0, v1, 'UniformOutput', false);
inversions = sum([test{:}]);

Edit2：repmat 方法

inversions = nnz(repmat(v2, length(v2), 1) - repmat(v1', 1, length(v1)) < 0)

Answer 3

代码

n = numel(v1);
[~, ind_sort] = sort([v1 v2]);
ind_v = ind_sort<=n;
result = sum(find(ind_v))-n*(n+1)/2;

说明

n 表示输入向量的长度。 ind_v 是一个长度为 2*n 的向量，表示 v1 和 v2 的值一起排序，其中 one 表示来自v1 和 zero 表示来自 v2 的值。例如，

v1 = [1,2,4];
v2 = [0,3,5];

我们有

ind_v =
     0     1     1     0     1     0

ind_v 的第一个条目是零。这意味着 v1 和 v2 中的最小值（即 0）属于 v2。然后有一个 one 因为第二低的值（即 1）属于 v1。 ind_v 的最后一个条目是 zero 因为输入向量的最大值（即 5）属于 v2.

由此ind_v很容易计算出结果。也就是说，我们只需要 计算每个 one 左边有多少 zeros，然后对所有这些计数求和.

我们甚至不需要统计；我们可以从每个 one 的位置推断出它们。第一个one左边的zeros的个数就是那个one减[=的位置25=]。第二个one左边的zeros个数就是它的位置减去2。等等。因此 sum(find(ind_v)-(1:n)) 会给出期望的结果。但是 sum(1:n) 就是 n*(n+1)/2，所以结果可以简化为 sum(find(ind_v))-n*(n+1)/2.

复杂性

向量排序是这里的限制操作，需要O(2*n*log(2*n))算术比较。相反，蛮力需要 O(n^2) 比较。

在 Matlab 中查找反转次数

Find the number of inversions in Matlab

arrays

optimization

performance

matlab

inversion

代码

说明

复杂性