주문한 집합의 고성능 병합

Question

번호 집합을 정렬 (오름차순 또는 내림차순이지만 아래 예제는 오름차순 만 표시)하는 것이 좋습니다. 최고의 속도를위한 데이터 구조 표현이 문제입니다.

예를 들어 네트워크를 통해 많은 모니터링 에이전트에서 숫자 패킷을 계속 수신하는 집계 프로그램을 말합니다. 아이디어는 항상 빠르게 정렬되도록 유지하는 것입니다. 예를 들어, 당신은 순서 (int 치의을 사용하고 있지만 이중 실제 사건)이 패킷을 얻을 수 있습니다 : 등등

A = [1, 3, 4, 6] 
B = [1, 2, 3] 
C = [2, 3, 5] 
A = [2, 4, 7, 8] 

하고 있습니다. 최초의 패킷 후에 게이터의 데이터 구조는 이미 정렬 될 것이다 (데이터 구조가 정렬 각 번호가 참조 어떤 소스 기억)

[1, 3, 4, 6] => 이벤트

다음 패킷 이후

그것이 새로운 소스이기 때문에, 데이터 구조는이

[1, 1, 2, 3, 3, 4, 6] => 이벤트 같을 것이다

다음 패킷 후 0

,

[1, 1, 2, 2, 3, 3, 3, 4, 5, 6] => 이벤트

지금은 새로운 패킷을 전송 이후

, 우리는 A의 이전 값을 찾아 새 값으로 대체해야만하고 결국 새로운 정렬로 끝나야합니다. 치환 후의와 별도로 여부 (올바른 위치) 일 수 정렬 목표는 극도 속도 :

[1, 2, 2, 2, 3, 3, 4, 5, 7, 8] => 이벤트

두 번째 A를 얻으면 이전의 모든 As는 정렬을 유지하면서 새로운 As 패킷으로 "대체"되어야한다는 점에 유의하십시오. 각 패킷이 데이터 구조로 정렬 된 후에 복사되고 "이벤트"로 전송되어야합니다. 이러한 패킷은 수십 마이크로 초마다 병합 정렬 알고리즘에서 맹렬히 그리고 지속적으로 발생합니다.

*이 작업을 수행하는 데 가장 적합한 데이터 구조는 무엇입니까? 아마도 Splay Tree 또는 AVL 트리입니까? *

Answer 1

이 내가 생각 특정 목적을위한 가장 빠른 데이터 구조 & 알고리즘 될 수 없습니다, 그러나 충분히 빠르게 할 수있다. 직접 테스트 해보십시오.

std::forward_list 또는 심지어 std::vector은 실제 시나리오에 따라 더 빠를 수도 있습니다 (큰 -O 표기법의 상수 요소).

tmyklebu 언급 된 다른 접근 방식 in the comments : 시나리오에 따라 요청시 병합하는 것이 더 빠를 수도 있습니다. 모든 데이터 세트를 개별적으로 저장하고 vector에 병합하여 이벤트 핸들러에 전달하거나 "증가"가 개별 데이터 세트의 다음 요소를 가져 오는 "병합"반복자를 사용합니다.

추가 성능 향상은 사용자 지정 메모리 풀 -> 사용자 지정 할당자를 사용하여 얻을 수 있습니다.

#include <set> 
#include <iostream> 
#include <iterator> 
#include <algorithm> 

// inserts a sorted range into the `to` container 
template < typename To, typename InputIt > 
void insert_new_sorted(To& to, 
         InputIt beg_old, InputIt end_old, 
         InputIt beg_new, InputIt end_new) 
{ 
    auto const& comp = to.value_comp(); 
    typename To::iterator i = to.begin(); 

    // might improve performance: don't remove elements which are in both 
    // ranges (old and new) 
    while(beg_old != end_old && beg_new != end_new) 
    { 
     if(comp(*beg_old, *beg_new)) 
     { 
      // remove old element 
      i = to.find(*beg_old); // "slow", no hint :(
      i = to.erase(i); 
      ++beg_old; 
     }else if(comp(*beg_new, *beg_old)) 
     { 
      // insert new element 
      // using the hint to achieve better performance 
      i = to.insert(i, *beg_new); 
      ++beg_new; 
     }else 
     { 
      // both equal, do nothing 
      ++beg_new; 
      ++beg_old; 
     } 
    } 

    // remove remaining old elements 
    for(; beg_old != end_old; ++beg_old) 
    { 
     to.erase(to.find(*beg_old)); // "slow", no hint :(
    } 

    // insert remaining new elements 
    for(; beg_new != end_new; ++beg_new) 
    { 
     i = to.insert(i, *beg_new); 
    } 

    std::copy(to.begin(), to.end(), 
     std::ostream_iterator<typename To::value_type>(std::cout, ", ")); 
    std::cout << std::endl; 
} 

int main() 
{ 
    using set_t = std::multiset<double>; 

    set_t const A = {1, 3, 4, 6}; 
    set_t const B = {1, 2, 3}; 
    set_t const C = {2, 3, 5}; 
    set_t const A2 = {2, 4, 7, 8}; 

    set_t result; 
    insert_new_sorted(result, A.end(), A.end(), A.begin(), A.end()); 
    insert_new_sorted(result, B.end(), B.end(), B.begin(), B.end()); 
    insert_new_sorted(result, C.end(), C.end(), C.begin(), C.end()); 
    insert_new_sorted(result, A.begin(), A.end(), A2.begin(), A2.end()); 
} 

출력 :

1, 3, 4, 6,
1, 1, 2, 3, 3, 4, 6,
1, 1, 2, 2, 3, 3, 3, 4, 5, 6,
1, 2, 2, 2, 3, 3, 4, 5, 7, 8,

---

다른 접근 : 삽입 된 요소의 반복자를 저장하여 지우기 속도를 높입니다.