Struttura dati per intervallo di tempo rapido cercare

Question

Ho una serie di intervalli di tempo In = (an, bn). Ho bisogno di eseguire un sacco di look up dove mi sono dato un tempo t e la necessità di tornare rapidamente gli intervalli che contengono t, per esempio, quegli intervalli tali che un < = t < = bn.

Che cos'è una buona struttura dati o un algoritmo per questo?

Se è importante, nel mio caso il un e miliardi sono numeri interi.

Answer 1

Quello che stai cercando è un Interval Tree (che è un tipo di Range Tree).

Questi hanno un tempo di ricerca logaritmico come altre strutture ad albero (ad es. Alberi RB), quindi dovresti vedere prestazioni paragonabili all'utilizzo di qualcosa come una Java TreeMap o una mappa STL.

• Code for Red-black trees and interval trees dal MIT
• C'è una C++ implementation nel CGAL Library.
• Ecco un C# Implementation

Answer 2

Questa è fondamentalmente una domanda di partizionamento dello spazio. Hai un grande spazio con contenitori e un punto specifico in quello spazio, quali contenitori tocca? Molti giochi devono risolvere questo problema, quindi non sarebbe una cattiva idea iniziare da lì. Cerca articoli sul "rilevamento di collisione in fase ampia".

Il modo più semplice per farlo è dividere lo spazio numerico in un numero costante di pezzi. Ogni pezzo sa quali insiemi si intersecano con esso, qualcosa che calcoli ogni volta che viene aggiunto un nuovo set. Ora, anziché testare ogni singolo set quando si ha un punto, è sufficiente controllare i set contenuti nel pezzo in cui si trova il punto.

Un altro algoritmo generale ed efficiente utilizzato è il parzializzazione dello spazio binario. Questo algoritmo suddivide il tuo spazio in due parti. Ogni lato dovrebbe sapere quali insiemi si intersecano con esso. È possibile ripetere ricorsivamente questo processo alla precisione desiderata (anche se non ha senso creare una suddivisione più piccola dell'intervallo del set più piccolo).

Answer 3

Il tuo problema è solo unidimensionale, quindi è un po 'più semplice dei problemi di partizionamento dello spazio trovati nella maggior parte dei giochi. Si potrebbe avere solo un semplice BST e in ogni foglia ricordare l'elenco degli intervalli a sinistra della foglia.

se avessi intervalli A (0, 10) e B (5, 15), quindi le foglie dell'albero sarebbero (0 con la lista vuota), (5 con A), (10 con A, B) e (15 con B).

Answer 4

Siete invitati a controllare il C# implementation I've posted on CodePlex for IntervalTree che risolvono questo problema esattamente.

Ido.