检查元素是否比另一个元素高的快速方法

Question

我正在用MATLAB编写一个程序来检查两个元素A和B是否在排名位置上被交换。

示例

假设第一位排名是：

list1 = [1 2 3 4]

第二个问题是：

list2 = [1 2 4 3]

我想检查一下A = 3和B = 4在排名中是否交换了相对位置，在这种情况下，这是正确的，因为在第一次排名中，3在4之前，在第二次排名中，3在4之后。

过程

为了做到这一点，我编写了以下MATLAB代码：

positionA1 = find(list1 == A);
positionB1 = find(list1 == B);
positionA2 = find(list2 == A);
positionB2 = find(list2 == B);
if (positionA1 <= positionB1 && positionA2 >= positionB2) || ...
   (positionA1 >= positionB1 && positionA2 <= positionB2)
      ... do something
end

不幸的是，我需要多次运行这段代码，而且find函数非常慢(但需要获得元素在列表中的位置)。

我想知道是否有办法加快手术速度。我还试图编写一个MEX文件，在C中执行查找操作，但没有帮助。

Answer 1

如果列表在循环中没有变化，那么您可以提前确定项目的位置。

假设您的项总是从1到N的整数：

[~, positions_1] = sort( list1 );
[~, positions_2] = sort( list2 );

这样您就不需要在循环中调用find了，您可以这样做：

positionA1 = positions_1(A);
positionB1 = positions_1(B);
positionA2 = positions_2(A);
positionB2 = positions_2(B);

如果您的循环正在遍历所有可能的A和B组合，那么您也可以将其向量化。

找到交换相对排名的元素：

rank_diff_1 = bsxfun(@minus, positions_1, positions_1');
rank_diff_2 = bsxfun(@minus, positions_2, positions_2');
rel_rank_changed = sign(rank_diff_1) ~= sign(rank_diff_2);
[A_changed, B_changed] = find(rel_rank_changed);

可选:删除一半的结果，因为如果(3,4)在列表中，那么(4,3)也会是，而且您可能不想这样：

mask = (A_changed < B_changed);
A_changed = A_changed(mask);
B_changed = B_changed(mask);

现在只循环那些已经交换了相对排名的元素。

for ii = 1:length(A_changed)
    A = A_changed(ii);
    B = B_changed(ii);
    % Do something...
end

Answer 2

而不是find，尝试计算这样的东西

检查是否有交换的值。

if logical(sum(abs(list1-list2)))
    do something
end;

对于具体值A和B：

if (list1(logical((list1-list2)-abs((list1-list2))))==A)&&(list1(logical((list1-list2)+abs((list1-list2))))==B)
    do something
end;