我需要找到向量中比之后的一个或多个元素小的元素。使用循环非常容易实现：
x = some_vector_values;
for m = 1 : length(x)
if( any( x(m+1:end) > x(m) )
do_such_and_such;
end
end
但速度让我抓狂。我正在想尽一切办法来寻找高效的解决方案，但却束手无策。数组长度可能达到数千，并且我需要为许多不同的数组执行此操作。
找出每个比其右侧元素小的元素
9
- AnonSubmitter85
11
6个回答
10
这里使用了一种分治的方法（类似于二分查找）：
结果是一个包含被接受元素的
- 找到向量中的最大值。
- 将其左侧的所有元素接受，但是拒绝最大值本身。
- 对于那些在最大值右侧的元素，执行步骤1。
结果是一个包含被接受元素的
true和被拒绝元素的false的逻辑向量ind。最终结果将是x(ind)。x = [3 4 3 5 6 3 4 1];
n = numel(x);
ind = false(1,n); %// intiallization
s = 1; %// starting index of the part of x that remains to be analyzed
while s <= n %// if s > n we have finished
[~, m] = max(x(s:end)); %// index of maximum within remaining part of x
ind(s:s-2+m) = true; %// elements to its left are accepted
s = s+m; %// update start of remaining part
end
通过将 while 条件更改为 while s < n，可以稍微减少运行时间，因为最后一个元素总是被拒绝。
- Luis Mendo
5
是的！这一定是处理更高数据的逻辑！+1 - Divakar
我猜这个算法的总运行时间是
O(n log(n))，而不是O(log(n))。我认为我的解决方案是O(n)。 - Bas Swinckels@BasSwinckels 你是对的，找到
max 会引入一个线性因素。已更正。 - Luis Mendo@BasSwinckels 重新考虑后，也许它是O(n)。平均而言，我计算n个元素的最大值，然后计算n/2个元素的最大值，然后计算n/4个元素的最大值……这样总和为2*n。 - Luis Mendo
1你可能是正确的，最优情况下（最大在结尾处）和平均情况下（如您所解释的），应该是
O(n)，但是在最坏情况下（当x严格递减时），为O(n^2)。 - Bas Swinckels6
一句话版本
comparisons = any(triu(bsxfun(@gt,x(:).',x(:))),2)
- Divakar
8
对于大向量（
numel(x)=10000），这种解决方案速度较慢。 - Daniel@Daniel 这是因为你在使用
bsxfun 时进行了拉伸，正如 @natan 指出的那样。 - Divakar谢谢。即使在最坏的情况下不是理想的，但在大多数情况下，这要快得多，并且非常有帮助。 - AnonSubmitter85
除了复杂性问题之外，你不会得到比这更简洁的答案。然而，我会考虑强制执行
x 的维度（即输入 x(:)）或进行检查。 - chappjc@chappjc，感谢你的发现错误的努力，已经进行了编辑！很高兴看到你在场！ - Divakar
显示剩余3条评论
6
您的算法很慢，因为
一个线性时间和内存的解决方案可能是首先计算从该点到结尾的最大值向量，这可以在一次向后传递中计算（您可以将其称为反向累积最大值，无法矢量化）。之后，该向量直接与
if any(...)在第一次迭代时必须检查n个项目，然后在第二次迭代中检查n-1个项目......直到在最后一次迭代中检查单个项目。因此，总体上它需要大约n^2/2次比较，因此它的运行时间是输入向量长度的平方函数！一个线性时间和内存的解决方案可能是首先计算从该点到结尾的最大值向量，这可以在一次向后传递中计算（您可以将其称为反向累积最大值，无法矢量化）。之后，该向量直接与
x进行比较（未经测试）：% calculate vector mx for which mx(i) = max(x(i:end))
mx = zeros(size(x));
mx(end) = x(end);
for i = length(x)-1:-1:1 % iterate backwards
mx(i) = max(x(i), mx(i+1));
end
for i = 1:length(x) - 1
if mx(i) > x(i)
do_such_and_such(i);
end
end
如果您不关心执行do_such_and_such的顺序，这些for循环甚至可以像这样组合：
mx = x(end);
for i = length(x)-1:-1:1 % iterate backwards
if x(i) < mx
do_such_and_such(i);
end
mx = max(x(i), mx); % maximum of x(i:end)
end
- Bas Swinckels
1
谢谢。我得到了几个好答案，但这个既简单又最快。非常有帮助，不仅对于这个具体问题，而且我感觉学到了一些东西供将来参考。 - AnonSubmitter85
6
这应该是一个只需O(n)时间和O(n)内存的算法: 把数组中最后一个元素标记为最大值。向后迭代整个数组。每当你遇到比最大值小的元素时，保存它。否则，它就成为新的最大值。这样一次迭代就能获取所有所需元素。
- Hovercouch
1
如果您想查找比右侧某个元素小的元素，也可以这样做：
x = some_values'; % x should be a column vector to use this
h = hankel(x);
m = max(h,[],2);
f = find(x<m) %returns indices or f = (a<m) %returns true/false
x =
9
8
16
16
4
10
9
13
15
1
>> h = hankel(x)
h =
9 8 16 16 4 10 9 13 15 1
8 16 16 4 10 9 13 15 1 0
16 16 4 10 9 13 15 1 0 0
16 4 10 9 13 15 1 0 0 0
4 10 9 13 15 1 0 0 0 0
10 9 13 15 1 0 0 0 0 0
9 13 15 1 0 0 0 0 0 0
13 15 1 0 0 0 0 0 0 0
15 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
>> m = max(h,[],2)
m =
16
16
16
16
15
15
15
15
15
1
>> f = find(a<m)
f =
1
2
5
6
7
8
- RDizzl3
1
该解决方案使用
O(n^2)内存。 - Bas Swinckels0
@NKN说得对。排序。
x = some_vector_values;
[Y,I]=sort(x); %sort in order, get indices
dy=gradient(Y); %get difference vector same size as input vector
ind=find(dy~=0);%ignore places that are equal to the value of interest
for m = 1 : length(ind)
do_such_and_such to Y(ind(m));
end
祝你好运
- EngrStudent
4
也许我错过了一些显而易见的东西，但我不明白这怎么可能起作用。有两个标准：1）A > B，2）A在B的右侧。 - AnonSubmitter85
@BasSwinckels - 对于编译软件是的。对于解释性语言可能不是。内置排序函数很可能是编译的，而你的脚本则不一定。我见过编译运行比解释运行快1000倍，但结果因情况而异。当形式为O(n log(n))时，编译排序与解释排序的速度比较为O( 1000n log(1000n) / n log(n) ) 或大约是3000 * O(n log(n))。内置函数非常快。 - EngrStudent
1现在的Matlab具有相当不错的JIT，特别是对于简单循环，其性能应该可以达到编译代码的小倍数。这个常数因子可能比大数组的log(n)还要小。 - Bas Swinckels
此答案不符合问题的标准。 - AnonSubmitter85
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
sort函数还可以返回排序后元素的原始索引。 - dustincarrif比较。 - AnonSubmitter85