用于查找数字数组中的最大差异的算法

我有几百万个数字的数组.

double* const data = new double (3600000);

我需要迭代数组并找到范围(数组中的最大值减去最小值).然而,有一个问题.我只想找到最小值和最大值在1000个样本之间的范围.

所以我需要找到最大值:范围(数据+ 0,数据+ 1000),范围(数据+ 1,数据+ 1001),范围(数据+ 2,数据+ 1002),....,范围(数据) + 3599000,数据+ 3600000).

我希望这是有道理的.基本上我可以像上面那样做,但我正在寻找一个更有效的算法,如果存在的话.我认为上面的算法是O(n),但我觉得可以优化.我正在玩的一个想法是跟踪最近的最大值和最小值以及它们的返回距离,然后在必要时才回溯.

我将用C++编写它,但伪代码中的一个很好的算法就可以了.另外,如果我想找的这个号码有一个名字,我很想知道它是什么.

谢谢.

这类问题属于称为流式算法的算法分支.正是对问题的研究不仅需要O(n)解决方案,而且还需要在数据的单次传递中工作.数据作为流输入到算法中,算法无法保存所有数据,然后永远丢失.算法需要得到关于数据的一些答案,例如最小值或中值.

具体而言,您正在流中的窗口中寻找最大值(或更常见的文献 - 最小值).

这是一篇关于一篇文章的演讲,该文章将这个问题作为他们试图获得的问题的一个子问题.它可能会给你一些想法.

我认为解决方案的大纲是这样的 - 在流上保持窗口,在每个步骤中一个元素插入窗口,一个元素从另一侧移除(滑动窗口).您实际保留在内存中的项目不是窗口中的所有1000个项目,而是选定的代表,这些项目将成为最低(或最大)的最佳候选者.

阅读文章.这是复杂的,但在2-3次读取之后你可以掌握它.

你描述的算法实际上是O(N),但我认为常数太高了.另一个看起来合理的解决方案是使用O(N*log(N))算法,方法如下:

* create sorted container (std::multiset) of first 1000 numbers
* in loop (j=1, j<(3600000-1000); ++j)
   - calculate range
   - remove from the set number which is now irrelevant (i.e. in index *j - 1* of the array)
   - add to set new relevant number  (i.e. in index *j+1000-1* of the array)

我相信它应该更快,因为常数要低得多.

这是一个最小队列的良好应用- 一个队列(First-In,First-Out = FIFO),它可以同时跟踪它包含的最小元素,并进行分摊的常数时间更新.当然,max-queue基本上是一回事.

一旦你有了这个数据结构,你可以考虑CurrentMax(过去的1000个元素)减去CurrentMin,将其存储为BestSoFar,然后推送一个新值并弹出旧值,然后再次检查.这样,不断更新BestSoFar,直到最终值成为您问题的解决方案.每一步都需要摊销恒定时间,因此整个事情是线性的,我所知的实现具有良好的标量常数(它很快).

我不知道有关min-queue的任何文档 - 这是我与同事合作提出的数据结构.您可以通过在内部跟踪数据的每个连续子序列中的最少元素的二叉树来实现它.它简化了您只能从结构的一端弹出数据的问题.

如果您对更多细节感兴趣,我可以尝试提供它们.我正在考虑将这个数据结构写成arxiv的论文.另请注意,Tarjan和其他人之前已经建立了一个更强大的min-deque结构,可以在这里工作,但实现起来要复杂得多.您可以谷歌"mindeque"阅读有关Tarjan等人的工作.