我有一个由数百万个数字组成的数组。
double* const data = new double (3600000);
我需要遍历数组并找到范围（数组中的最大值减去最小值）。但是，有一个陷阱。我只想找到最小和最大值彼此在1,000个样本内的范围。
所以我需要找到以下项的最大值：range（data + 0，data + 1000），range（data + 1，data + 1001），range（data + 2，data + 1002），....，range （数据+ 3599000，数据+ 3600000）。
我希望这是有道理的。基本上我可以像上面那样做，但是我正在寻找一种更有效的算法（如果存在）。我认为上述算法为O（n），但我认为可以进行优化。我正在考虑的一个想法是跟踪最近的最大值和最小值以及它们的回溯距离，然后仅在必要时回溯。
我将用C ++进行编码，但是用伪代码编写好的算法就可以了。此外，如果我要查找的这个号码有名字，我很想知道它是什么。
谢谢。
您描述的算法实际上是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)
我相信它应该更快，因为常数要低得多。
这种类型的问题属于称为流算法的算法的一个分支。对问题的研究不仅需要O（n）解决方案，而且还需要单次处理数据。数据作为流输入到算法，算法无法保存所有数据，然后永远丢失。该算法需要获得有关数据的一些答案，例如最小值或中位数。
特别是，您正在流中的窗口中寻找最大值（或更常见的文献中的最小值）。
Here's a presentation上的[article]将此问题作为他们要解决的问题的子问题。它可能会给您一些想法。
我认为解决方案的轮廓是这样的-保持流上的窗口，在每个步骤中，一个元素插入到窗口中，一个元素从另一侧移出（滑动窗口）。您实际存储的项目并不是窗口中所有1000个项目，而是选定的代表，这些代表可能会成为最小（或最大）的候选对象。
阅读文章。它有点复杂，但是经过2-3次读取后，您就可以掌握它了。
这是min-queue的一个很好的应用-队列（先进先出= FIFO），该队列可以同时跟踪其包含的最小元素，并分摊固定时间更新。当然，最大队列基本上是一回事。
一旦有了此数据结构，就可以考虑（过去1000个元素中的）CurrentMax减去CurrentMin，将其存储为BestSoFar，然后推送新值并弹出旧值，然后再次检查。这样，请不断更新BestSoFar，直到最终值成为您问题的解决方案为止。每个步骤都需要摊销固定时间，因此整个过程都是线性的，我所知道的实现具有良好的标量常数（快速）。
我不知道有关min-queue的任何文档-这是我与同事合作开发的数据结构。您可以通过内部跟踪数据的每个连续子序列中最少元素的二进制树来实现它。它简化了仅从结构的一端弹出数据的问题。
如果您对更多详细信息感兴趣，我可以尝试提供它们。我当时正在考虑将此数据结构写为arxiv的论文。还要注意的是，Tarjan和其他人以前已经达到了一种更强大的最小双端队列结构，该结构可以在这里工作，但是实现起来要复杂得多。您可以google for "mindeque"阅读有关Tarjan等人的著作。
std::multiset<double> range;
double currentmax = 0.0;
for (int i = 0; i < 3600000; ++i)
{
if (i >= 1000)
range.erase(range.find(data[i-1000]));
range.insert(data[i]);
if (i >= 999)
currentmax = max(currentmax, *range.rbegin());
}
Note未经测试的代码。
编辑：修正了一个错误。
该算法应为O（n），因为删除和插入受log（1e3）限制，其他所有内容都需要固定时间。
我决定看看我能想到的解决这个问题的最有效算法是使用实际代码和实际时序。我首先创建了一个简单的解决方案，该解决方案使用循环缓冲区跟踪前n个条目的最小/最大值，并使用测试工具来测量速度。在简单的解决方案中，将每个数据值与一组最小/最大值进行比较，因此大约是window_size * count测试（原始问题中的window大小为1000，count为3600000）。
然后我考虑了如何使其更快。首先，我创建了一个解决方案，该方案使用fifo队列存储window_size值，并使用链表以升序存储值，其中链表中的每个节点也是队列中的节点。为了处理数据值，将fifo末尾的项目从链表和队列中删除。新值被添加到队列的开头，并且使用线性搜索来找到链表中的位置。然后可以从链接列表的开头和结尾读取最小值和最大值。这很快，但是随着window_size的增加（即线性地），缩放效果不佳。
因此，我决定向系统添加一个二叉树，以尝试加快算法的搜索部分。 window_size = 1000和count = 3600000的最终计时是：
Simple: 106875
Quite Complex: 1218
Complex: 1219
这既是预期的，也是意外的。期望使用排序的链表会有所帮助，这出乎意料，因为拥有自平衡树的开销并没有抵消快速搜索的优势。我尝试了增加窗口大小的后两个，发现直到window_size为100000时，它们始终几乎相同。
[这一切都表明，对算法进行理论化是一回事，而实现它们则是另一回事。
无论如何，对于那些感兴趣的人，这是我编写的代码（有很多！）：
Range.h：
#include <algorithm>
#include <iostream>
#include <ctime>
using namespace std;
// Callback types.
typedef void (*OutputCallback) (int min, int max);
typedef int (*GeneratorCallback) ();
// Declarations of the test functions.
clock_t Simple (int, int, GeneratorCallback, OutputCallback);
clock_t QuiteComplex (int, int, GeneratorCallback, OutputCallback);
clock_t Complex (int, int, GeneratorCallback, OutputCallback);
main.cpp：
#include "Range.h"
int
checksum;
// This callback is used to get data.
int CreateData ()
{
return rand ();
}
// This callback is used to output the results.
void OutputResults (int min, int max)
{
//cout << min << " - " << max << endl;
checksum += max - min;
}
// The program entry point.
void main ()
{
int
count = 3600000,
window = 1000;
srand (0);
checksum = 0;
std::cout << "Simple: Ticks = " << Simple (count, window, CreateData, OutputResults) << ", checksum = " << checksum << std::endl;
srand (0);
checksum = 0;
std::cout << "Quite Complex: Ticks = " << QuiteComplex (count, window, CreateData, OutputResults) << ", checksum = " << checksum << std::endl;
srand (0);
checksum = 0;
std::cout << "Complex: Ticks = " << Complex (count, window, CreateData, OutputResults) << ", checksum = " << checksum << std::endl;
}
Simple.cpp：
#include "Range.h"
// Function to actually process the data.
// A circular buffer of min/max values for the current window is filled
// and once full, the oldest min/max pair is sent to the output callback
// and replaced with the newest input value. Each value inputted is
// compared against all min/max pairs.
void ProcessData
(
int count,
int window,
GeneratorCallback input,
OutputCallback output,
int *min_buffer,
int *max_buffer
)
{
int
i;
for (i = 0 ; i < window ; ++i)
{
int
value = input ();
min_buffer [i] = max_buffer [i] = value;
for (int j = 0 ; j < i ; ++j)
{
min_buffer [j] = min (min_buffer [j], value);
max_buffer [j] = max (max_buffer [j], value);
}
}
for ( ; i < count ; ++i)
{
int
index = i % window;
output (min_buffer [index], max_buffer [index]);
int
value = input ();
min_buffer [index] = max_buffer [index] = value;
for (int k = (i + 1) % window ; k != index ; k = (k + 1) % window)
{
min_buffer [k] = min (min_buffer [k], value);
max_buffer [k] = max (max_buffer [k], value);
}
}
output (min_buffer [count % window], max_buffer [count % window]);
}
// A simple method of calculating the results.
// Memory management is done here outside of the timing portion.
clock_t Simple
(
int count,
int window,
GeneratorCallback input,
OutputCallback output
)
{
int
*min_buffer = new int [window],
*max_buffer = new int [window];
clock_t
start = clock ();
ProcessData (count, window, input, output, min_buffer, max_buffer);
clock_t
end = clock ();
delete [] max_buffer;
delete [] min_buffer;
return end - start;
}
QuiteComplex.cpp：
#include "Range.h"
template <class T>
class Range
{
private:
// Class Types
// Node Data
// Stores a value and its position in various lists.
struct Node
{
Node
*m_queue_next,
*m_list_greater,
*m_list_lower;
T
m_value;
};
public:
// Constructor
// Allocates memory for the node data and adds all the allocated
// nodes to the unused/free list of nodes.
Range
(
int window_size
) :
m_nodes (new Node [window_size]),
m_queue_tail (m_nodes),
m_queue_head (0),
m_list_min (0),
m_list_max (0),
m_free_list (m_nodes)
{
for (int i = 0 ; i < window_size - 1 ; ++i)
{
m_nodes [i].m_list_lower = &m_nodes [i + 1];
}
m_nodes [window_size - 1].m_list_lower = 0;
}
// Destructor
// Tidy up allocated data.
~Range ()
{
delete [] m_nodes;
}
// Function to add a new value into the data structure.
void AddValue
(
T value
)
{
Node
*node = GetNode ();
// clear links
node->m_queue_next = 0;
// set value of node
node->m_value = value;
// find place to add node into linked list
Node
*search;
for (search = m_list_max ; search ; search = search->m_list_lower)
{
if (search->m_value < value)
{
if (search->m_list_greater)
{
node->m_list_greater = search->m_list_greater;
search->m_list_greater->m_list_lower = node;
}
else
{
m_list_max = node;
}
node->m_list_lower = search;
search->m_list_greater = node;
}
}
if (!search)
{
m_list_min->m_list_lower = node;
node->m_list_greater = m_list_min;
m_list_min = node;
}
}
// Accessor to determine if the first output value is ready for use.
bool RangeAvailable ()
{
return !m_free_list;
}
// Accessor to get the minimum value of all values in the current window.
T Min ()
{
return m_list_min->m_value;
}
// Accessor to get the maximum value of all values in the current window.
T Max ()
{
return m_list_max->m_value;
}
private:
// Function to get a node to store a value into.
// This function gets nodes from one of two places:
// 1. From the unused/free list
// 2. From the end of the fifo queue, this requires removing the node from the list and tree
Node *GetNode ()
{
Node
*node;
if (m_free_list)
{
// get new node from unused/free list and place at head
node = m_free_list;
m_free_list = node->m_list_lower;
if (m_queue_head)
{
m_queue_head->m_queue_next = node;
}
m_queue_head = node;
}
else
{
// get node from tail of queue and place at head
node = m_queue_tail;
m_queue_tail = node->m_queue_next;
m_queue_head->m_queue_next = node;
m_queue_head = node;
// remove node from linked list
if (node->m_list_lower)
{
node->m_list_lower->m_list_greater = node->m_list_greater;
}
else
{
m_list_min = node->m_list_greater;
}
if (node->m_list_greater)
{
node->m_list_greater->m_list_lower = node->m_list_lower;
}
else
{
m_list_max = node->m_list_lower;
}
}
return node;
}
// Member Data.
Node
*m_nodes,
*m_queue_tail,
*m_queue_head,
*m_list_min,
*m_list_max,
*m_free_list;
};
// A reasonable complex but more efficent method of calculating the results.
// Memory management is done here outside of the timing portion.
clock_t QuiteComplex
(
int size,
int window,
GeneratorCallback input,
OutputCallback output
)
{
Range <int>
range (window);
clock_t
start = clock ();
for (int i = 0 ; i < size ; ++i)
{
range.AddValue (input ());
if (range.RangeAvailable ())
{
output (range.Min (), range.Max ());
}
}
clock_t
end = clock ();
return end - start;
}
Complex.cpp：
#include "Range.h"
template <class T>
class Range
{
private:
// Class Types
// Red/Black tree node colours.
enum NodeColour
{
Red,
Black
};
// Node Data
// Stores a value and its position in various lists and trees.
struct Node
{
// Function to get the sibling of a node.
// Because leaves are stored as null pointers, it must be possible
// to get the sibling of a null pointer. If the object is a null pointer
// then the parent pointer is used to determine the sibling.
Node *Sibling
(
Node *parent
)
{
Node
*sibling;
if (this)
{
sibling = m_tree_parent->m_tree_less == this ? m_tree_parent->m_tree_more : m_tree_parent->m_tree_less;
}
else
{
sibling = parent->m_tree_less ? parent->m_tree_less : parent->m_tree_more;
}
return sibling;
}
// Node Members
Node
*m_queue_next,
*m_tree_less,
*m_tree_more,
*m_tree_parent,
*m_list_greater,
*m_list_lower;
NodeColour
m_colour;
T
m_value;
};
public:
// Constructor
// Allocates memory for the node data and adds all the allocated
// nodes to the unused/free list of nodes.
Range
(
int window_size
) :
m_nodes (new Node [window_size]),
m_queue_tail (m_nodes),
m_queue_head (0),
m_tree_root (0),
m_list_min (0),
m_list_max (0),
m_free_list (m_nodes)
{
for (int i = 0 ; i < window_size - 1 ; ++i)
{
m_nodes [i].m_list_lower = &m_nodes [i + 1];
}
m_nodes [window_size - 1].m_list_lower = 0;
}
// Destructor
// Tidy up allocated data.
~Range ()
{
delete [] m_nodes;
}
// Function to add a new value into the data structure.
void AddValue
(
T value
)
{
Node
*node = GetNode ();
// clear links
node->m_queue_next = node->m_tree_more = node->m_tree_less = node->m_tree_parent = 0;
// set value of node
node->m_value = value;
// insert node into tree
if (m_tree_root)
{
InsertNodeIntoTree (node);
BalanceTreeAfterInsertion (node);
}
else
{
m_tree_root = m_list_max = m_list_min = node;
node->m_tree_parent = node->m_list_greater = node->m_list_lower = 0;
}
m_tree_root->m_colour = Black;
}
// Accessor to determine if the first output value is ready for use.
bool RangeAvailable ()
{
return !m_free_list;
}
// Accessor to get the minimum value of all values in the current window.
T Min ()
{
return m_list_min->m_value;
}
// Accessor to get the maximum value of all values in the current window.
T Max ()
{
return m_list_max->m_value;
}
private:
// Function to get a node to store a value into.
// This function gets nodes from one of two places:
// 1. From the unused/free list
// 2. From the end of the fifo queue, this requires removing the node from the list and tree
Node *GetNode ()
{
Node
*node;
if (m_free_list)
{
// get new node from unused/free list and place at head
node = m_free_list;
m_free_list = node->m_list_lower;
if (m_queue_head)
{
m_queue_head->m_queue_next = node;
}
m_queue_head = node;
}
else
{
// get node from tail of queue and place at head
node = m_queue_tail;
m_queue_tail = node->m_queue_next;
m_queue_head->m_queue_next = node;
m_queue_head = node;
// remove node from tree
node = RemoveNodeFromTree (node);
RebalanceTreeAfterDeletion (node);
// remove node from linked list
if (node->m_list_lower)
{
node->m_list_lower->m_list_greater = node->m_list_greater;
}
else
{
m_list_min = node->m_list_greater;
}
if (node->m_list_greater)
{
node->m_list_greater->m_list_lower = node->m_list_lower;
}
else
{
m_list_max = node->m_list_lower;
}
}
return node;
}
// Rebalances the tree after insertion
void BalanceTreeAfterInsertion
(
Node *node
)
{
node->m_colour = Red;
while (node != m_tree_root && node->m_tree_parent->m_colour == Red)
{
if (node->m_tree_parent == node->m_tree_parent->m_tree_parent->m_tree_more)
{
Node
*uncle = node->m_tree_parent->m_tree_parent->m_tree_less;
if (uncle && uncle->m_colour == Red)
{
node->m_tree_parent->m_colour = Black;
uncle->m_colour = Black;
node->m_tree_parent->m_tree_parent->m_colour = Red;
node = node->m_tree_parent->m_tree_parent;
}
else
{
if (node == node->m_tree_parent->m_tree_less)
{
node = node->m_tree_parent;
LeftRotate (node);
}
node->m_tree_parent->m_colour = Black;
node->m_tree_parent->m_tree_parent->m_colour = Red;
RightRotate (node->m_tree_parent->m_tree_parent);
}
}
else
{
Node
*uncle = node->m_tree_parent->m_tree_parent->m_tree_more;
if (uncle && uncle->m_colour == Red)
{
node->m_tree_parent->m_colour = Black;
uncle->m_colour = Black;
node->m_tree_parent->m_tree_parent->m_colour = Red;
node = node->m_tree_parent->m_tree_parent;
}
else
{
if (node == node->m_tree_parent->m_tree_more)
{
node = node->m_tree_parent;
RightRotate (node);
}
node->m_tree_parent->m_colour = Black;
node->m_tree_parent->m_tree_parent->m_colour = Red;
LeftRotate (node->m_tree_parent->m_tree_parent);
}
}
}
}
// Adds a node into the tree and sorted linked list
void InsertNodeIntoTree
(
Node *node
)
{
Node
*parent = 0,
*child = m_tree_root;
bool
greater;
while (child)
{
parent = child;
child = (greater = node->m_value > child->m_value) ? child->m_tree_more : child->m_tree_less;
}
node->m_tree_parent = parent;
if (greater)
{
parent->m_tree_more = node;
// insert node into linked list
if (parent->m_list_greater)
{
parent->m_list_greater->m_list_lower = node;
}
else
{
m_list_max = node;
}
node->m_list_greater = parent->m_list_greater;
node->m_list_lower = parent;
parent->m_list_greater = node;
}
else
{
parent->m_tree_less = node;
// insert node into linked list
if (parent->m_list_lower)
{
parent->m_list_lower->m_list_greater = node;
}
else
{
m_list_min = node;
}
node->m_list_lower = parent->m_list_lower;
node->m_list_greater = parent;
parent->m_list_lower = node;
}
}
// Red/Black tree manipulation routine, used for removing a node
Node *RemoveNodeFromTree
(
Node *node
)
{
if (node->m_tree_less && node->m_tree_more)
{
// the complex case, swap node with a child node
Node
*child;
if (node->m_tree_less)
{
// find largest value in lesser half (node with no greater pointer)
for (child = node->m_tree_less ; child->m_tree_more ; child = child->m_tree_more)
{
}
}
else
{
// find smallest value in greater half (node with no lesser pointer)
for (child = node->m_tree_more ; child->m_tree_less ; child = child->m_tree_less)
{
}
}
swap (child->m_colour, node->m_colour);
if (child->m_tree_parent != node)
{
swap (child->m_tree_less, node->m_tree_less);
swap (child->m_tree_more, node->m_tree_more);
swap (child->m_tree_parent, node->m_tree_parent);
if (!child->m_tree_parent)
{
m_tree_root = child;
}
else
{
if (child->m_tree_parent->m_tree_less == node)
{
child->m_tree_parent->m_tree_less = child;
}
else
{
child->m_tree_parent->m_tree_more = child;
}
}
if (node->m_tree_parent->m_tree_less == child)
{
node->m_tree_parent->m_tree_less = node;
}
else
{
node->m_tree_parent->m_tree_more = node;
}
}
else
{
child->m_tree_parent = node->m_tree_parent;
node->m_tree_parent = child;
Node
*child_less = child->m_tree_less,
*child_more = child->m_tree_more;
if (node->m_tree_less == child)
{
child->m_tree_less = node;
child->m_tree_more = node->m_tree_more;
node->m_tree_less = child_less;
node->m_tree_more = child_more;
}
else
{
child->m_tree_less = node->m_tree_less;
child->m_tree_more = node;
node->m_tree_less = child_less;
node->m_tree_more = child_more;
}
if (!child->m_tree_parent)
{
m_tree_root = child;
}
else
{
if (child->m_tree_parent->m_tree_less == node)
{
child->m_tree_parent->m_tree_less = child;
}
else
{
child->m_tree_parent->m_tree_more = child;
}
}
}
if (child->m_tree_less)
{
child->m_tree_less->m_tree_parent = child;
}
if (child->m_tree_more)
{
child->m_tree_more->m_tree_parent = child;
}
if (node->m_tree_less)
{
node->m_tree_less->m_tree_parent = node;
}
if (node->m_tree_more)
{
node->m_tree_more->m_tree_parent = node;
}
}
Node
*child = node->m_tree_less ? node->m_tree_less : node->m_tree_more;
if (node->m_tree_parent->m_tree_less == node)
{
node->m_tree_parent->m_tree_less = child;
}
else
{
node->m_tree_parent->m_tree_more = child;
}
if (child)
{
child->m_tree_parent = node->m_tree_parent;
}
return node;
}
// Red/Black tree manipulation routine, used for rebalancing a tree after a deletion
void RebalanceTreeAfterDeletion
(
Node *node
)
{
Node
*child = node->m_tree_less ? node->m_tree_less : node->m_tree_more;
if (node->m_colour == Black)
{
if (child && child->m_colour == Red)
{
child->m_colour = Black;
}
else
{
Node
*parent = node->m_tree_parent,
*n = child;
while (parent)
{
Node
*sibling = n->Sibling (parent);
if (sibling && sibling->m_colour == Red)
{
parent->m_colour = Red;
sibling->m_colour = Black;
if (n == parent->m_tree_more)
{
LeftRotate (parent);
}
else
{
RightRotate (parent);
}
}
sibling = n->Sibling (parent);
if (parent->m_colour == Black &&
sibling->m_colour == Black &&
(!sibling->m_tree_more || sibling->m_tree_more->m_colour == Black) &&
(!sibling->m_tree_less || sibling->m_tree_less->m_colour == Black))
{
sibling->m_colour = Red;
n = parent;
parent = n->m_tree_parent;
continue;
}
else
{
if (parent->m_colour == Red &&
sibling->m_colour == Black &&
(!sibling->m_tree_more || sibling->m_tree_more->m_colour == Black) &&
(!sibling->m_tree_less || sibling->m_tree_less->m_colour == Black))
{
sibling->m_colour = Red;
parent->m_colour = Black;
break;
}
else
{
if (n == parent->m_tree_more &&
sibling->m_colour == Black &&
(sibling->m_tree_more && sibling->m_tree_more->m_colour == Red) &&
(!sibling->m_tree_less || sibling->m_tree_less->m_colour == Black))
{
sibling->m_colour = Red;
sibling->m_tree_more->m_colour = Black;
RightRotate (sibling);
}
else
{
if (n == parent->m_tree_less &&
sibling->m_colour == Black &&
(!sibling->m_tree_more || sibling->m_tree_more->m_colour == Black) &&
(sibling->m_tree_less && sibling->m_tree_less->m_colour == Red))
{
sibling->m_colour = Red;
sibling->m_tree_less->m_colour = Black;
LeftRotate (sibling);
}
}
sibling = n->Sibling (parent);
sibling->m_colour = parent->m_colour;
parent->m_colour = Black;
if (n == parent->m_tree_more)
{
sibling->m_tree_less->m_colour = Black;
LeftRotate (parent);
}
else
{
sibling->m_tree_more->m_colour = Black;
RightRotate (parent);
}
break;
}
}
}
}
}
}
// Red/Black tree manipulation routine, used for balancing the tree
void LeftRotate
(
Node *node
)
{
Node
*less = node->m_tree_less;
node->m_tree_less = less->m_tree_more;
if (less->m_tree_more)
{
less->m_tree_more->m_tree_parent = node;
}
less->m_tree_parent = node->m_tree_parent;
if (!node->m_tree_parent)
{
m_tree_root = less;
}
else
{
if (node == node->m_tree_parent->m_tree_more)
{
node->m_tree_parent->m_tree_more = less;
}
else
{
node->m_tree_parent->m_tree_less = less;
}
}
less->m_tree_more = node;
node->m_tree_parent = less;
}
// Red/Black tree manipulation routine, used for balancing the tree
void RightRotate
(
Node *node
)
{
Node
*more = node->m_tree_more;
node->m_tree_more = more->m_tree_less;
if (more->m_tree_less)
{
more->m_tree_less->m_tree_parent = node;
}
more->m_tree_parent = node->m_tree_parent;
if (!node->m_tree_parent)
{
m_tree_root = more;
}
else
{
if (node == node->m_tree_parent->m_tree_less)
{
node->m_tree_parent->m_tree_less = more;
}
else
{
node->m_tree_parent->m_tree_more = more;
}
}
more->m_tree_less = node;
node->m_tree_parent = more;
}
// Member Data.
Node
*m_nodes,
*m_queue_tail,
*m_queue_head,
*m_tree_root,
*m_list_min,
*m_list_max,
*m_free_list;
};
// A complex but more efficent method of calculating the results.
// Memory management is done here outside of the timing portion.
clock_t Complex
(
int count,
int window,
GeneratorCallback input,
OutputCallback output
)
{
Range <int>
range (window);
clock_t
start = clock ();
for (int i = 0 ; i < count ; ++i)
{
range.AddValue (input ());
if (range.RangeAvailable ())
{
output (range.Min (), range.Max ());
}
}
clock_t
end = clock ();
return end - start;
}
算法思想：
[取数据的前1000个值并将其排序排序中的最后一个-第一个是range（data + 0，data + 999）。然后从排序堆中删除值为data [0]的第一个元素并添加元素数据[1000]现在，排序中的最后一个-第一个是range（data + 1，data + 1000）。重复直到完成
// This should run in (DATA_LEN - RANGE_WIDTH)log(RANGE_WIDTH)
#include <set>
#include <algorithm>
using namespace std;
const int DATA_LEN = 3600000;
double* const data = new double (DATA_LEN);
....
....
const int RANGE_WIDTH = 1000;
double range = new double(DATA_LEN - RANGE_WIDTH);
multiset<double> data_set;
data_set.insert(data[i], data[RANGE_WIDTH]);
for (int i = 0 ; i < DATA_LEN - RANGE_WIDTH - 1 ; i++)
{
range[i] = *data_set.end() - *data_set.begin();
multiset<double>::iterator iter = data_set.find(data[i]);
data_set.erase(iter);
data_set.insert(data[i+1]);
}
range[i] = *data_set.end() - *data_set.begin();
// range now holds the values you seek
您可能应该检查一下是否有1个错误，但是这里有个主意。