(잠재적으로) 1.000.000 + 개 항목의 하위 집합 필터링

Question

나는 두세 가지 이상의 항목이 포함 된 dataset이 있습니다. 모든 항목에는 지정된 시간 소인이 있고 런타임에 세트에 항목이 추가됩니다 (일반적으로는 아니지만 항상 최신 시간 소인으로). 특정 시간 범위에서이 데이터의 하위 집합을 표시해야합니다. 이 시간 범위는 일반적으로 총 데이터 세트, 즉 주어진 시간 범위에 약 1000 개 이하의 1.000.000 이상의 항목에 비해 상당히 적습니다. 이 시간 범위는 일정한 속도로 이동합니다 (예 : 매초마다 시간 범위가 1 초씩 이동합니다. 또한 사용자는 언제든지 시간 범위를 조정하거나 (데이터 세트를 '이동') 추가 필터를 설정할 수 있습니다 (예 : 텍스트로 필터링).

지금까지 나는 성능에 대해 걱정하지 않고 다른 것들을 올바르게하려고 노력했으며 더 작은 테스트 세트로만 작업했습니다. 나는이 문제를 효율적으로 다루는 방법을 잘 모르며 모든 입력에 대해 기뻐할 것입니다. 감사.

편집 : 사용 언어는 C 번호를 4.

업데이트 : 지금은 간격 나무를 사용하고, 구현은 여기에서 찾을 수 있습니다 : https://github.com/mbuchetics/RangeTree

또한 사용하여 트리를 재 구축 비동기 버전과 함께 제공 작업 병렬 라이브러리 (TPL).

Answer 1

새 항목을 정렬 된 목록에 삽입하십시오. 이렇게하면 범위를 쉽게 선택할 수 있습니다. linq를 잘 알고 있다면 잠재적으로 linq도 사용할 수 있습니다.

Answer 2

SortedList을 타임 스탬프별로 정렬하여 사용하십시오.

정렬 목록의 정렬 된 키에 대해 이진 검색을 구현하면 선택한 항목의 경계를 쉽게 찾을 수 있습니다.

Answer 3

우리는 비슷한 문제를 안고있었습니다. 몇 백만 개의 항목을 몇 개의 키로 정렬 한 다음 요청시 한 페이지를 내 보내야했습니다. 나는 당신의 문제가 어떻게 든 유사하다는 것을 알았다. 목적

, 우리는 다음과 같은 방법으로 red-black tree 구조, 적용 :

• 우리가 그것에 반복자 추가를, 그래서 (1)
• 우리가 추가 우리는 O를 '다음'아이템을 얻을 수 '인덱스'에서 반복자를 발견하고하는 것은

RB Tree이 O를 삽입 복잡성 (로그 n), 그래서 당신의 삽입이 잘 거기에 맞는 추측이 O에 (로그 n) 그렇게 할 수 있었다.

next()은 모든 리프 노드의 링크 된 목록을 추가하고 유지함으로써 구현되었습니다. 원래 채택한 RB Tree 구현에는이 내용이 포함되어 있지 않았습니다.

RB Tree은 사용자의 필요에 따라 노드 크기를 미세 조정할 수 있으므로 멋지기도합니다. 실험을 통해 문제에 맞는 번호를 찾아 낼 수 있습니다.