Ricerca intervallo in Java

Question

Supponiamo, Ho una matrice non ordinata di sovrapposti ranges. Ogni range è solo una coppia di numeri interi begin e end. Ora voglio scoprire se un dato key appartiene ad almeno uno degli ranges. Probabilmente, devo sapere che lo ranges appartiene pure.

Possiamo supporre che l'array ranges impieghi ~ 1 M e si adatti alla memoria. Sto cercando un algoritmo semplice, che utilizzi solo raccolte JDK standard senza alcuna libreria di parti 3D e strutture dati speciali, ma funziona abbastanza velocemente.

Che cosa suggeriresti?

Answer 1

Se non avete bisogno di sapere che intervallo contiene il punto (EDIT: Credo che probabilmente è così, ma io Lascerai questa risposta per gli altri con questa domanda che non lo fanno), quindi

1. pre-elaborazione gli intervalli calcolando due array B ed E. B è i valori di inizio in modo ordinato. E è il valore di fine nell'ordine ordinato.

2. Per interrogare un punto x, utilizzare la ricerca binaria per trovare l'indice minore i tale che B [i]> x e l'indice minore j tali che E [j] ≥ x. Il numero di intervalli [inizio, fine] contenente x è i-j.

---

class Interval { 
    double begin, end; 
} 

class BeginComparator implements java.util.Comparator<Interval> { 
    public int compare(Interval o1, Interval o2) { 
     return Double.compare(o1.begin, o2.begin); 
    } 
}; 

public class IntervalTree { 
    IntervalTree(Interval[] intervals_) { 
     intervals = intervals_.clone(); 
     java.util.Arrays.sort(intervals, new BeginComparator()); 
     maxEnd = new double[intervals.length]; 
     initializeMaxEnd(0, intervals.length); 
    } 

    double initializeMaxEnd(int a, int b) { 
     if (a >= b) { 
      return Double.NEGATIVE_INFINITY; 
     } 
     int m = (a + b) >>> 1; 
     maxEnd[m] = initializeMaxEnd(a, m); 
     return Math.max(Math.max(maxEnd[m], intervals[m].end), initializeMaxEnd(m + 1, b)); 
    } 

    void findContainingIntervals(double x, int a, int b, java.util.Collection<Interval> result) { 
     if (a >= b) { 
      return; 
     } 
     int m = (a + b) >>> 1; 
     Interval i = intervals[m]; 
     if (x < i.begin) { 
      findContainingIntervals(x, a, m, result); 
     } else { 
      if (x <= i.end) { 
       result.add(i); 
      } 
      if (maxEnd[m] >= x) { 
       findContainingIntervals(x, a, m, result); 
      } 
      findContainingIntervals(x, m + 1, b, result); 
     } 
    } 

    java.util.Collection<Interval> findContainingIntervals(double x) { 
     java.util.Collection<Interval> result = new java.util.ArrayList<Interval>(); 
     findContainingIntervals(x, 0, intervals.length, result); 
     return result; 
    } 

    Interval[] intervals; 
    double[] maxEnd; 

    public static void main(String[] args) { 
     java.util.Random r = new java.util.Random(); 
     Interval[] intervals = new Interval[10000]; 
     for (int j = 0; j < intervals.length; j++) { 
      Interval i = new Interval(); 
      do { 
       i.begin = r.nextDouble(); 
       i.end = r.nextDouble(); 
      } while (i.begin >= i.end); 
      intervals[j] = i; 
     } 
     IntervalTree it = new IntervalTree(intervals); 
     double x = r.nextDouble(); 
     java.util.Collection<Interval> result = it.findContainingIntervals(x); 
     int count = 0; 
     for (Interval i : intervals) { 
      if (i.begin <= x && x <= i.end) { 
       count++; 
      } 
     } 
     System.out.println(result.size()); 
     System.out.println(count); 
    } 
} 

Answer 2

Ordina gli intervalli numericamente una consuetudine Comparator, quindi per ogni chiave k costruire una serie di un elemento [k, k] e fare un binary search per questa gamma con un diverso Comparator.

Il Comparator per la ricerca di compare(x,y) dovrebbe restituire

• <0 se x.max < y.min
• >0 se x.min > y.max
• 0 altrimenti (i suoi due argomenti gamma si sovrappongono).

Come notato da @Per, è necessario un diverso, più rigoroso Comparator per l'ordinamento, ma le prime due clausole rimangono valide.

Questo dovrebbe funzionare anche se gli intervalli si sovrappongono, anche se è possibile che si desideri unire intervalli sovrapposti dopo l'ordinamento per accelerare la ricerca. La fusione può essere eseguita in tempo O (N).

Questo è in effetti una statica interval tree, cioè uno senza O (lg N) inserimento o delezione, nello stesso modo in cui un array ordinato può essere considerato un statico albero binario di ricerca.

Answer 3

Credo che questo è quello che stai cercando: http://en.wikipedia.org/wiki/Interval_tree

ma controllare questa soluzione più semplice per vedere se si adatta alle vostre esigenze: Using java map for range searches

Answer 4

soluzione semplice con O (n) la complessità:

for(Range range: ranges){ 
    if (key >= range.start && key <= range.end) 
    return range; 
} 

È possibile applicare un algoritmo più intelligente se si conoscono ulteriori informazioni sugli intervalli. Sono ordinati? Si sono sovrapposti? e così via

Answer 5

Dato solo le vostre specifiche, sarei propenso a ordinare gli intervalli per dimensione, con gli intervalli più ampi prima (utilizzare un comparatore personalizzato per facilitare questo). Quindi semplicemente itera attraverso di loro e restituisce true non appena trovi un intervallo che contiene la chiave. Poiché non sappiamo nient'altro sui dati, ovviamente gli intervalli più ampi sono quelli con maggiori probabilità di contenere una determinata chiave; la prima ricerca potrebbe essere una (piccola) ottimizzazione.

È possibile pre-elaborare l'elenco in altri modi.Ad esempio, è possibile escludere qualsiasi intervallo che è completamente racchiuso da altri intervalli. È possibile ordinare per begin e uscire anticipatamente non appena si incontra un valore begin superiore alla chiave.