숫자 배열에서 최대 차이를 찾기위한 알고리즘
-
02-07-2019 - |
문제
수백만 개의 배열이 있습니다.
double* const data = new double (3600000);
배열을 반복하고 범위를 찾아야합니다 (배열에서 가장 큰 값을 가장 작은 값을 뺀 값). 그러나 캐치가 있습니다. 가장 작고 가장 큰 값이 서로 1,000 개의 샘플 이외의 범위 만 찾고 싶습니다.
따라서 범위 (데이터 + 0, 데이터 + 1000), 범위 (데이터 + 1, 데이터 + 1001), 범위 (데이터 + 2, 데이터 + 1002), ...., 범위 (데이터)를 찾아야합니다. + 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) 솔루션뿐만 아니라 데이터를 통해 단일 패스로 작업 해야하는 문제에 대한 연구입니다. 데이터는 알고리즘의 스트림으로 입력되며 알고리즘은 모든 데이터를 저장 한 다음 영원히 손실됩니다. 알고리즘은 예를 들어 최소 또는 중앙값과 같은 데이터에 대한 답을 얻어야합니다.
구체적으로 당신은 스트림 위의 창에서 최대 (또는 더 일반적으로 문헌 - 최소)를 찾고 있습니다.
여기에 프레젠테이션이 있습니다 에 기사 그것은이 문제를 그들이 얻으려고하는 것의 하위 문제로 언급합니다. 그것은 당신에게 몇 가지 아이디어를 줄 수 있습니다.
솔루션의 개요는 그와 비슷하다고 생각합니다. 각 단계에서 각 단계에서 한 요소가 창에 삽입되고 하나는 다른 쪽 (슬라이딩 창)에서 제거되는 스트림 위의 창을 유지합니다. 실제로 메모리에 보관하는 항목은 창에있는 1000 개의 항목이 아니라 최소 (또는 최대)가 될 수있는 좋은 후보자가 될 선택된 대표자입니다.
기사를 읽다. 그것은 단지이지만 2-3 번 읽은 후에는 그것을 갈 수 있습니다.
이것은 a를 잘 적용하는 것입니다 최소 큐 -상각 된 일정한 시간 업데이트와 함께 포함 된 최소 요소를 동시에 추적 할 수있는 큐 (First-in, First-out = Fifo). 물론 최대 큐는 기본적으로 동일합니다.
이 데이터 구조를 마련한 후에는 CurrentMax (지난 1000 개 요소)에서 CurrentMin을 뺀 것을 고려하여 최고로 가장 좋은 것으로 저장 한 다음 새 값을 푸시하고 이전 값을 팝하고 다시 확인할 수 있습니다. 이런 식으로 최종 가치가 질문에 대한 해결책이 될 때까지 최고의 업데이트를 계속 업데이트하십시오. 각 단일 단계는 상각 된 일정한 시간이 걸리므로 모든 것이 선형이며, 내가 아는 구현은 우수한 스칼라 상수를 가지고 있습니다 (빠릅니다).
나는 Min -Queue의 문서에 대한 어떤 문서도 모른다 - 이것은 동료와 협력하여 제가 생각한 데이터 구조이다. 데이터의 각 연속 하단 내에서 최소 요소의 이진 트리를 내부적으로 추적하여 구현할 수 있습니다. 구조의 한쪽 끝에서 데이터 만 팝업하는 문제를 단순화합니다.
자세한 내용에 관심이 있으시면 제공 할 수 있습니다. 이 데이터 구조를 Arxiv의 논문으로 작성하려고 생각했습니다. 또한 Tarjan과 다른 사람들은 이전에 여기서 작동 할보다 강력한 최소-다크 구조에 도달했지만 구현은 훨씬 더 복잡합니다. 당신은 할 수 있습니다 "Mindeque"를위한 Google Tarjan et al.의 작품에 대해 읽습니다.
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());
}
메모 테스트되지 않은 코드.
편집하다: 외부로 수정 된 오류.
- 처음 1000 숫자로 읽으십시오.
- 현재 1000 숫자를 추적하는 1000 요소 링크 목록을 만듭니다.
- 링크 된 목록 노드에 1000 개의 요소 배열, 1-1 매핑을 만듭니다.
- 링크 된 목록 노드 값을 기반으로 포인터 배열을 정렬하십시오. 이것은 배열을 재 배열하지만 링크 된 목록을 그대로 유지합니다.
- 이제 포인터 배열의 첫 번째 및 마지막 요소를 검사하여 처음 1000 숫자의 범위를 계산할 수 있습니다.
- 링크 된 목록을 만드는 방법에 따라 머리 또는 꼬리 인 첫 번째 삽입 요소를 제거하십시오. 노드의 값을 사용하면 포인터 배열에서 이진 검색을 수행하여 염려된 노드의 포인터를 찾아 배열을 이동하여 제거합니다.
- 링크 된 목록에 1001 번째 요소를 추가하고 삽입 정렬의 한 단계를 수행하여 배열의 올바른 위치에 포인터를 삽입하십시오. 배열을 정렬합니다.
- 이제 당신은 분이 있습니다. 그리고 맥스. 1과 1001 사이의 숫자 값이며 포인터 배열의 첫 번째 및 마지막 요소를 사용하여 범위를 계산할 수 있습니다.
- 이제 나머지 배열에 대해 무엇을 해야하는지 분명해야합니다.
삭제 및 삽입이 로그 (1E3)에 의해 제한되므로 알고리즘은 O (n)이어야하며 다른 모든 것은 일정한 시간이 걸립니다.
이 문제를 해결하기 위해 가장 효율적인 알고리즘이 실제 코드와 실제 타이밍을 사용하는 것이 무엇인지 확인하기로 결정했습니다. 먼저 원형 버퍼를 사용하여 이전 N 항목의 최소/최대를 추적하는 간단한 솔루션과 속도를 측정하기위한 테스트 하네스를 만들었습니다. 간단한 솔루션에서 각 데이터 값은 최소/최대 값 세트와 비교되므로 Window_Size * 카운트 테스트에 관한 것입니다 (원래 질문의 창 크기는 1000이고 카운트는 3600000).
그런 다음 더 빨리 만드는 방법에 대해 생각했습니다. 먼저, FIFO 대기열을 사용하여 Window_Size 값을 저장하는 솔루션을 만들었고 링크 된 목록을 링크 된 순서로 저장하여 링크 된 목록의 각 노드도 큐의 노드 인 경우 값을 오름차순 순서로 저장했습니다. 데이터 값을 처리하기 위해 FIFO 끝의 항목은 링크 된 목록과 대기열에서 제거되었습니다. 새로운 값이 큐 시작에 추가되었고 선형 검색을 사용하여 링크 된 목록에서 위치를 찾았습니다. 그런 다음 최소 및 최대 값을 링크 된 목록의 시작과 끝에서 읽을 수 있습니다. 이것은 빠르지 만 Window_size가 증가함에 따라 (예 : 선형 적으로) 확장되지는 않을 것입니다.
그래서 나는 알고리즘의 검색 부분을 속도를 높이기 위해 시스템에 이진 트리를 추가하기로 결정했습니다. Window_Size = 1000 및 Count = 3600000의 최종 타이밍은 다음과 같습니다.
Simple: 106875
Quite Complex: 1218
Complex: 1219
예상과 예상치 못한 것입니다. 정렬 된 링크 목록을 사용하면 셀프 밸런싱 트리가있는 오버 헤드가 빠른 검색의 장점을 상쇄하지 않았다는 점에서 예상치 못한 것으로 예상됩니다. 나는 창 크기가 증가한 후자 2 개를 시도했지만 항상 100000의 Window_size까지 거의 동일하다는 것을 발견했습니다.
모든 것이 알고리즘에 대한 이론화가 한 가지임을 보여줍니다.이를 구현하는 것은 다른 것입니다.
어쨌든, 관심이있는 사람들을 위해, 여기에 내가 쓴 코드가 있습니다 (꽤 조금 있습니다!).
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 값을 가져 와서 정렬하십시오.
마지막으로 - 첫 번째는 범위입니다 (data + 0, data + 999).
그런 다음 정렬 파일에서 값 데이터를 사용하여 첫 번째 요소를 제거합니다 [0
요소 데이터를 추가합니다 [1000
이제 마지막으로 - 첫 번째는 범위 (데이터 + 1, 데이터 + 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 개의 오류로 확인해야하지만 아이디어가 있습니다.