Un algoritmo di intersezione di intervallo migliore di O (n)?
https://stackoverflow.com/questions/303591
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
L'intersezione dell'intervallo è un problema semplice, ma non banale.
Ha già ricevuto una risposta due volte:
La prima soluzione è O (n) e la seconda soluzione è per un database (che è ovviamente inferiore a O (n)).
Ho lo stesso problema, ma per una n grande e non sono all'interno di un database.
Questo problema sembra essere molto simile a Memorizza punti 2D per un rapido recupero di quelli all'interno di un rettangolo ma non vedo come si mappa.
Quindi in quale struttura di dati memorizzereste l'insieme di intervalli, in modo tale che una ricerca su un intervallo abbia un costo inferiore a O (n)? (Credito extra per l'utilizzo delle librerie disponibili per Java)
EDIT:
Voglio ottenere un sottoinsieme di tutti gli intervalli che si intersecano, il che significa che l'intervallo di ricerca potrebbe intersecare più intervalli.
Il metodo che deve essere inferiore a O (n) in Java è:
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
Dove Range è solo una classe che contiene una coppia di inizio e fine int.
Questa non è una domanda impossibile, ho già la soluzione, volevo solo vedere se c'era un modo più standard / più semplice di farlo
Soluzione
L'approccio standard consiste nell'utilizzare un albero degli intervalli .
In informatica, una struttura ad intervalli è una struttura di dati ad albero per contenere gli intervalli. In particolare, consente di trovare in modo efficiente tutti gli intervalli che si sovrappongono a un dato intervallo o punto. Viene spesso utilizzato per le query di finestre, ad esempio, per trovare tutte le strade su una mappa computerizzata all'interno di una finestra rettangolare o per trovare tutti gli elementi visibili all'interno di una scena tridimensionale. Una struttura di dati simile è l'albero dei segmenti.
La banale soluzione è visitare ogni intervallo e verificare se interseca il punto o l'intervallo dato, che richiede O (n) tempo, dove n è il numero di intervalli nella raccolta. Poiché una query può restituire tutti gli intervalli, ad esempio se la query è un intervallo ampio che interseca tutti gli intervalli nella raccolta, questo è asintoticamente ottimale; tuttavia, possiamo fare meglio considerando gli algoritmi sensibili all'output, in cui il runtime è espresso in termini di m, il numero di intervalli prodotti dalla query. Gli alberi degli intervalli hanno un tempo di query di O (log n + m) e un tempo di creazione iniziale di O (n log n), limitando il consumo di memoria a O (n). Dopo la creazione, gli alberi degli intervalli possono essere dinamici, consentendo l'inserimento e l'eliminazione efficienti di un intervallo in O (log n). Se gli endpoint degli intervalli si trovano all'interno di un piccolo intervallo intero (ad es. Nell'intervallo [1, ..., O (n)]), esistono strutture di dati più veloci [1] con tempo di preelaborazione O (n) e tempo di query O ( 1 + m) per la segnalazione di intervalli m contenenti un determinato punto di query.
Altri suggerimenti
Modifica Sembra che questa soluzione sia più o meno un Interval Tree . Un'implementazione più completa di un albero a intervalli è disponibile qui .
class TreeNode
{
public:
long pivot;
List<Range> leaves; //Any ranges that intersect the pivot
TreeNode left; //Tree nodes that fall to the left of the pivot
TreeNode right; //Tree nodes that fall to the right of the pivot
};
Prep O (n registro n):
- Crea l'elenco di intervalli
- Scegli i punti pivot (possibilmente utilizzando un elenco ordinato delle date di fine.) ??
- Costruisci il tuo albero.
Ricerca:
- Utilizza la ricerca binaria per trovare il primo pivot che è > = TestRange.End
-
Attraversa l'albero fino a quando il perno > TestRange.Start
2a. Aggiungi le foglie al tuo risultato.
Esempio:
SERIE:
- 0 - 2
- 1 - 2
- 2 - 3
- 1 - 4
- 2-4
- 0-5
- 4 - 5
- 2-6
- 3 - 7
Albero:
4
--------------+------------------
3 | 7
| 1-4 |
| 2-4 |
| 0-5 |
| 4-5 |
---------+------ --------+--------
2 | null 6 | null
-----+---- 2-3 ----+---- 3-7
null | null null | null
0-2 2-6
1-2
Intervalli non sovrapposti:
Prep O (n registro n):
- Crea un array / vettore degli intervalli.
- Ordina il vettore entro la fine dell'intervallo (interrompi i legami ordinandoli all'inizio dell'intervallo)
Ricerca:
- Utilizza la ricerca binaria per trovare il primo intervallo con un valore finale di > = TestRange.Start
-
Iteratore che inizia alla ricerca binaria fino a trovare Start > TestRange.End:
2a. Se l'intervallo se l'intervallo corrente è compreso nel TestRange, aggiungilo al tuo risultato.
Questo dipende dal tuo esatto problema, nella domanda collegata, gli intervalli in cui distinti, nessuna parte comune e l'intervallo cercato potrebbero estendersi su più intervalli. Se il tuo problema è lo stesso, è davvero facile: Prendi una matrice degli intervalli, ordinali in base ai loro valori più bassi (poiché non si sovrappongono, questo sarebbe anche lo stesso ordine in cui sono ordinati in base ai loro valori superiori).
Ora fai solo una ricerca per il valore target più basso (o più piccolo se non esatto) e uno per il valore target più alto (o più grande se non esatto). Gli indici risultanti sono gli intervalli che sono coperti. Devi controllare se gli intervalli negli indici stessi sono interni o esclusi, ma sono solo 2 controlli. Complessità complessiva O (log n).
Intervalli sovrapposti:
Prep O (n registro n):
- Crea un array / vettore degli intervalli.
- Ordina il vettore entro la fine dell'intervallo (interrompi i legami ordinandoli all'inizio dell'intervallo)
-
Crea un secondo vettore di ints. Questo rappresenta il punto in cui è possibile interrompere la ricerca.
int stop[size]; stop[size-1] = Ranges[size - 1].start; for (int i = size - 2; i >= 0; i--) { stop[i] = min(Ranges[i].start, stop[i+1]); }
Ricerca:
- Utilizza la ricerca binaria per trovare il primo intervallo con un valore finale di > = TestRange.Start
-
Iteratore che inizia alla ricerca binaria fino all'arresto [i] > TestRange.End:
2a. Se l'intervallo se l'intervallo corrente è compreso nel TestRange, aggiungilo al tuo risultato.
Se gli intervalli si sovrappongono e si desidera recuperare tutti gli intervalli che si sovrappongono (o contengono) un determinato intervallo di destinazione, la maggior parte delle soluzioni sopra non sembrano funzionare.
Come alcuni hanno sottolineato, se (nel peggiore dei casi) tutti gli intervalli si intersecano con l'intervallo target (ad esempio, se l'intervallo target è {0..MAXINT} o simile), allora ovviamente ci vuole O (n) per restituire gli n intervalli.
Ma non è il caso interessante e tipico / medio, in cui solo una percentuale molto piccola di n intervalli totali interseca l'intervallo obiettivo? Chiama il numero che fa interseca " m " - in tal caso, è possibile che tu sia in grado di fare così come O (m). E se n = 10 ^ 9 e m = 10, questa è una differenza make-or-break.
Considera il semplice caso di un documento di testo che ha diverse regioni contrassegnate per il loro "tipo" - forse vuoi trovare tutte le unità contrassegnate che contengono o intersecano un determinato intervallo contiguo di testo (ad esempio un paragrafo). In HTML, XML o simili, questi possono essere solo antenati dei nodi di testo contenenti almeno alcuni caratteri dell'intervallo di destinazione. Nelle rappresentazioni tipiche con puntatori padre in ciascun nodo, questo è O (m) - molto meglio di O (n), soprattutto perché m è (per intervalli target brevi o sincroni) semplicemente la profondità di annidamento dell'albero, che tende ad essere persino inferiore a ln (n) perché in pratica i grandi documenti XML non diventano più profondi.
Il caso interessante è più difficile: cosa succede se i tuoi "elementi" non formano un albero come in XML, ma possono sovrapporsi come in MECS, CLIX, LMNL e altri sistemi? Desideri comunque trovare tutte le regioni / "elementi" che si sovrappongono al tuo obiettivo, ma non sono così facilmente organizzabili.
D'altra parte, dovresti essere in grado di fare molto bene perché gli intervalli di mark-up in molte applicazioni sono più frequentemente piccoli - ci sono molte più parole, frasi e paragrafi in un libro, rispetto ai capitoli. Quindi, anche se potrebbe esserci un numero enorme di intervalli che iniziano prima dell'obiettivo e un numero enorme che termina dopo di esso, l'intersezione sarà mediamente molto piccola.
Penso che sia quello a cui stava arrivando l'interrogatore originale, e temo di non aver visto una risposta che risolva il problema. Se non si tratta di quale fosse la domanda originale, allora vorrei porla come una nuova domanda.
Sembra che tu abbia bisogno di una classe che implementa l'interfaccia SortedSet. TreeSet è l'implementazione fornita con l'API principale.
Avere un set contenente gli intervalli ordinati per valore più basso e uno ordinato per valore più alto.
È quindi possibile implementare l'equivalente dell'algoritmo del database utilizzando i set in memoria.
Non posso dire se questo sia effettivamente più veloce di O (n).
Proprio come un albero quad funziona per un insieme di 2d punti, un semplice albero binario dovrebbe funzionare in questo caso. Costruisci un albero con le tue gamme.
Per spiegare ulteriormente: Ogni nodo nella struttura contiene due numeri interi, l'inizio e la fine dell'intervallo e i due figli se non è un nodo foglia. Per trovare gli intervalli che abbraccia l'intervallo di input, iniziando dalla parte superiore dell'albero
- if the node range intersects the input range:
- if it's a leaf node, then add the range to your result list
- if it's not a leaf node, then traverse down to the child nodes and repeat this process.
Dovrebbe essere O (logN)
Ulteriori dettagli: L'albero binario sarebbe strutturato come una versione 1-d di un albero quad. Ogni nodo avrebbe tre numeri interi (mi dispiace, ho detto due sopra, ma ora mi rendo conto che ne hai bisogno tre), il più basso che rappresenta il valore più basso dell'intervallo più basso che è sotto questo nodo, il più alto che rappresenta il valore più alto dell'intervallo più alto che è al di sotto di questo nodo e il perno. Il bambino sinistro si estenderebbe dal più basso di questo nodo al suo perno. Il bambino giusto si estenderebbe dal perno di questo nodo al più alto di questo nodo. Se esiste un solo intervallo che va da "più basso" a "più alto", non avresti un perno e questa sarebbe una foglia. Idealmente, dovresti scegliere i perni per ciascun nodo per mantenere l'albero equilibrato.
Quando ho avuto questo problema, ho usato una matrice ordinata di intervalli e una ricerca binaria per cercare intersezioni. Questa è (credo) O (log n) performance, con un po 'di overhead per gestire intervalli sovrapposti.
La risposta alla tua domanda è, credo, derivabile dal codice qui sotto, ma interrompendo l'inserimento. Vi presento l'intero codice per evitare confusione nel contesto diverso: avevo bisogno di inserire un intervallo di punti di codice Unicode in un elenco di intervalli di punti di codice.
- EDIT -
L'adattamento del codice seguente per determinare le intersezioni di più intervalli comporta una banale ricerca in avanti dal punto di inserimento fino a quando non viene trovato un intervallo che non si interseca più.
- END EDIT -
La classe Range contiene:
final int lower; // lower end of range
final int upper; // upper end of range
public int compareTo(Object obj) {
if(obj==null) { return -1; }
Range oth=(Range)obj;
if(lower<oth.lower) { return -1; }
if(lower>oth.lower) { return 1; }
if(upper<oth.upper) { return -1; }
if(upper>oth.upper) { return 1; }
return 0;
}
Inserimento intervallo:
public Builder addRange(int fir, int las) {
if(fir!=-1) { fir&=0x001FFFFF; }
if(las!=-1) { las&=0x001FFFFF; }
if(codepoints==null || codepoints.length==0) {
codepoints=new Range[]{new Range(fir,las)};
}
else {
int idx=Range.findChar(codepoints,fir);
int ins=(idx<0 ? -(idx+1) : idx);
if(idx<0) {
if (ins>0 && fir==(codepoints[ins-1].upper+1)) { idx=(ins-1); } // new range adjoins the following range (can't overlap or idx would be >=0)
else if(ins<codepoints.length && las>=(codepoints[ins ].lower-1)) { idx=ins; } // new range overlaps or adjoins the following range
}
if(idx<0) {
codepoints=(Range[])Util.arrayInsert(codepoints,ins,new Range(fir,las));
}
else {
boolean rmv=false;
for(int xa=(idx+1); xa<codepoints.length && codepoints[xa].lower<=las; xa++) {
if(las<codepoints[xa].upper) { las=codepoints[xa].upper; }
codepoints[xa]=null;
rmv=true;
}
if(codepoints[idx].lower>fir || codepoints[idx].upper<las) {
codepoints[idx]=new Range((codepoints[idx].lower < fir ? codepoints[idx].lower : fir),(codepoints[idx].upper>las ? codepoints[idx].upper : las));
}
if(rmv) { codepoints=Range.removeNulls(codepoints); }
}
}
return this;
}
Ricerca binaria:
static int findChar(Range[] arr, int val) {
if(arr.length==1) {
if (val< arr[0].lower) { return -1; } // value too low
else if(val<=arr[0].upper) { return 0; } // value found
else { return -2; } // value too high
}
else {
int lowidx=0; // low index
int hghidx=(arr.length-1); // high index
int mididx; // middle index
Range midval; // middle value
while(lowidx<=hghidx) {
mididx=((lowidx+hghidx)>>>1);
midval=arr[mididx];
if (val< midval.lower) { hghidx=(mididx-1); } // value too low
else if(val<=midval.upper) { return mididx; } // value found
else { lowidx=(mididx+1); } // value too high
}
return -(lowidx+1); // value not found.
}
}
