Eine Reihe Kreuzung Algorithmus besser als O(n)?
https://stackoverflow.com/questions/303591
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Bereich Kreuzung ist ein einfaches, aber nicht triviales problem.
Ihr beantwortet wurde schon zweimal:
Die ersten Lösungen ist O(n) und die zweite Lösung ist für eine Datenbank (das ist weniger als O(n) natürlich).
Ich habe das gleiche problem, aber für große n und ich bin nicht in einer Datenbank.
Dieses problem scheint sehr ähnlich zu sein Speichern von 2D-Punkte für schnellen Abruf von denen im inneren eines Rechtecks aber ich weiß nicht, wie es Karten.
Also, was Datenstruktur würde, speichern Sie die Menge von Bereichen, in solche, die eine Suche auf einen Bereich Kosten weniger als O(n)?(Extra-Guthaben für die Verwendung von Bibliotheken für Java)
EDIT:
Ich möchte eine Teilmenge aller sich überschneidenden Bereiche, d.h. die Suche Bereich überschneiden mehrere Bereiche.
Die Methode, die Bedürfnisse zu werden weniger als O(n) in Java ist:
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
Wobei der Bereich ist einfach Klasse mit einem paar von int start und Ende.
Dies ist nicht eine Unmögliche Frage, ich habe bereits die Lösung, ich wollte nur sehen, ob es noch eine mehr standard/einfacheren Weg, es zu tun
Lösung
Der standard-Ansatz ist zu verwenden eine Intervall-Baum.
In der informatik, ein Intervall-Baum ist eine Baum-Datenstruktur zu halten Abständen.Speziell, die es einem ermöglicht, effizient zu finden, die alle Intervalle, die sich überschneiden, mit einer gegebenen Intervall oder Punkt.Es wird oft für windowing Abfragen, zum Beispiel, finden alle Straßen, die auf ein EDV-anzeigen in einem rechteckigen Ansichtsfenster, oder finden Sie alle sichtbaren Elemente innerhalb einer dreidimensionalen Szene.Eine ähnliche Datenstruktur ist der segment-Baum.
Die triviale Lösung ist der Besuch jedes Intervall und testen, ob es schneidet den gegebenen Punkt oder ein Intervall, das erfordert O(n) Zeit, wobei n die Anzahl der Intervalle, die in der Sammlung.Da eine Abfrage zurückgeben kann alle Intervalle, zum Beispiel, wenn die Abfrage eine große Intervall kreuzenden alle Intervalle in der Sammlung, dies ist asymptotisch optimal;jedoch, wir tun können besser durch die Berücksichtigung output-sensitive algorithms, wobei die Laufzeit ist ausgedrückt in m, die die Anzahl der Intervalle, erzeugt durch die Abfrage.Intervall-Bäume haben eine Anfrage in Zeit O(log n + m) und einer ersten Schöpfung der Zeit O(n log n), während die Begrenzung der Speicherverbrauch von O(n).Nach der Erstellung Intervall-Bäume können dynamisch sein, so dass eine effiziente einfügen und löschen eines Intervalls in O(log n).Wenn die Endpunkte der Intervalle sind in einem kleinen integer-Bereich (z.B. im Bereich [1,...,A(n)]), schneller Daten-Strukturen existieren, [1] mit der Vorverarbeitung der Zeit O(n) und Abfrage-Zeit von O(1+m) für die Berichterstattung der m-Abständen mit einer bestimmten Abfrage zeigen.
Andere Tipps
Edit: Es klingt wie diese Lösung ist mehr oder weniger ein Intervall-Baum.Eine vollständige Umsetzung einer Intervall-Baum gefunden werden kann hier.
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 log n):
- Erstellen Sie die Liste reicht
- Wählen Sie die pivot-Punkte (ggf. durch die Verwendung einer sortierten Liste von der Enddaten.) ??
- Bauen Sie Ihren Baum.
Suche:
- Verwenden Sie die binäre Suche, um zu finden die erste pivot-das ist >= TestRange.Ende
Durchlaufen Sie den Baum, bis der pivot - > TestRange.Start
2a.Fügen Sie die Blätter zu Ihrem Ergebnis.
Beispiel:
Bereiche:
- 0 - 2
- 1 - 2
- 2 - 3
- 1 - 4
- 2 - 4
- 0 - 5
- 4 - 5
- 2 - 6
- 3 - 7
Baum:
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
Nicht Überlappende Bereiche:
Prep O(n log n):
- Machen Sie ein array / Vektor-Bereiche.
- Art der Vektor durch das Ende des Bereichs (Bande brechen, indem Sie Sie Sortieren, indem Sie den Beginn des Bereichs)
Suche:
- Verwenden Sie die binäre Suche auf den ersten Bereich mit einem End-Wert von >= TestRange.Start
Iterator beginnend bei der binären Suche, bis du findest einen Start > TestRange.Ende:
2a.Wenn der Bereich, wenn der aktuelle Bereich ist in der TestRange, fügen Sie es zu Ihrem Ergebnis.
Dies hängt von Ihrem genauen problem, in der verlinkten Frage, die Bereiche, wo verschiedene, kein gemeinsames Teil, und das gesuchte reichte, konnte sich über mehrere Bereiche.Wenn Ihr problem das gleiche ist ganz einfach:Nehmen Sie ein array von Bereichen, Sortieren Sie durch Ihre niedrigsten Werte (da Sie sich nicht überlappen, wäre dies auch der Reihenfolge, sortiert nach Ihren Ober-Werte).
Jetzt machen Sie einfach eine binsearch für die Ihr Ziel nicht niedriger Wert (oder kleiner, wenn nicht genau) und eine für das Ziel oberen Wert(oder größer, wenn nicht genau).Die daraus resultierenden Indizes sind das die Bereiche, die sind coverd.Sie haben zu prüfen, ob Sie die Bereiche an, die Indizes selbst sind ein - oder ausgeschlossen, aber das sind nur 2 Prüfungen.Insgesamt ist die Komplexität O(log n).
Überlappende Bereiche:
Prep O(n log n):
- Machen Sie ein array / Vektor-Bereiche.
- Art der Vektor durch das Ende des Bereichs (Bande brechen, indem Sie Sie Sortieren, indem Sie den Beginn des Bereichs)
Machen Sie einen zweiten Vektor von ints.Dies entspricht dem Punkt, an dem Sie aufhören zu suchen.
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]); }
Suche:
- Verwenden Sie die binäre Suche auf den ersten Bereich mit einem End-Wert von >= TestRange.Start
Iterator beginnend bei der binären Suche, bis stop[i] > TestRange.Ende:
2a.Wenn der Bereich, wenn der aktuelle Bereich ist in der TestRange, fügen Sie es zu Ihrem Ergebnis.
Wenn Bereiche sich überschneiden und man abrufen möchte alle die Bereiche, die sich überlappen (oder enthalten) ein bestimmtes Ziel Bereich, die meisten der oben genannten Lösungen nicht zu funktionieren scheinen.
Einige haben darauf hingewiesen, wenn (worst-case) alle die Bereiche passieren, um schneiden Sie die Ziel-Bereich (für Beispiel, wenn der Zielbereich ist {0..MAXINT} oder ähnlich) dann natürlich dauert es O(n), um die n-Bereiche.
Aber ist nicht die interessante und typisch/Durchschnitt der Fall, wo nur ein sehr kleiner % n Gesamt-Reichweiten tun, schneiden Sie die Ziel-Bereich?Rufen Sie die Nummer, die do schneiden Sie die "m" - in diesem Fall könnten Sie möglicherweise in der Lage sein zu tun, sowie O(m).Und wenn n=10^9 und m=10, das ist ein make-oder-break Unterschied.
Betrachten Sie den einfachen Fall von einem text-Dokument mit verschiedenen geprägten Regionen, für Ihre "Art" - vielleicht, wenn Sie möchten, um herauszufinden, alle markierten Einheiten enthalten oder schneiden Sie einen bestimmten Seitenbereich des Textes (Z. B. eines Absatzes).Im HTML -, XML -, oder ähnlich wie diese können nur Ahnen des text-node(s) mit zumindest einige Zeichen der Ziel Bereich.In typischen Darstellungen mit übergeordneten Zeiger in den einzelnen Knoten ist O(m) - Weg besser als O(n), vor allem, weil m ist (für kurz-oder synchron-Zielgruppe reicht) bloß der Baum Verschachtelungstiefe, die meist sogar niedriger als ln(n), weil große XML-Dokumente in der Praxis bekommen buschiger nicht tiefer.
Der interessante Fall ist schwerer:was, wenn Ihre "Elemente" nicht bilden eine Struktur wie in XML, sondern können sich überlappen, wie in MECS, CLIX, LMNL, und einige andere Systeme?Sie wollen immer noch, um herauszufinden, alle Regionen/"Elementen", die sich überschneiden Ihr Ziel, aber Sie sind nicht so leicht organisiert.
Auf der anderen Seite, sollten Sie in der Lage sein zu tun, sehr gut, weil markierte Bereiche in vielen Anwendungen sind die meisten oft kleinen-es gibt viel mehr Wörter, Sätze und Absätze in einem Buch, als gibt es Kapitel.Also, auch wenn es möglicherweise eine große Anzahl von Bereichen, die vor dem starten der Ziel-und eine riesige Zahl, die nach ihm enden der Kreuzung werden sehr gering sein im Durchschnitt.
Ich denke, das ist, was die ursprüngliche Frage war immer, und ich fürchte, ich habe nicht finden Sie eine Antwort, die behebt das problem.Wenn es ist nicht, was die ursprüngliche Frage war etwa, dann würde ich gerne stellen, als eine neue Frage.
Klingt wie Sie brauchen eine Klasse, die das interface SortedSet.TreeSet ist die Implementierung, die Schiffe mit der Kern-API.
Ein Satz holding die Bereiche, sortiert nach dem niedrigsten Wert, und ein, sortiert nach dem höchsten Wert.
Sie können dann umzusetzen, ist das äquivalent des Datenbank-Algorithmus unter Verwendung der in-memory-sets.
Als ob dies tatsächlich schneller als O(n), konnte ich nicht sagen.
Nur als ein quad-tree funktioniert für eine Reihe von 2d-Punkten, eine einfache binäre Baum sollte funktionieren für diesen Fall.Bauen Sie einen Baum mit Ihren Bereichen.
Im weiteren näher erläutert werden:Jeder Knoten in der Struktur enthält die zwei ganzen zahlen, dem Anfang und das Ende des Bereichs, und die zwei Kinder, wenn es nicht einen Blattknoten.Zu finden, die Bereiche, die Ihrem Eingangsbereich überspannt, dann beginnen Sie an der Spitze des Baumes
- 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.
Es sollte O(logN)
Weitere Details:Der binäre Baum strukturiert werden, wie ein 1-d-version von ein quad-Baum.Jeder Knoten drei Ganzzahlen (sorry, ich sagte beiden oben, aber jetzt erkenne ich, Sie benötigen drei), die niedrigsten Vertreter der niedrigste Wert der niedrigsten Bereich unterhalb dieses Knotens, der höchste Vertreter der höchste Wert der höchsten Reichweite, die unterhalb dieses Knotens, und der Dreh-und Angelpunkt.Die linke Kind würde Spannweite von diesem Knoten die niedrigsten um seinen Drehpunkt.Das Rechte Kind würde Spannweite von diesem Knoten die pivot-dieser Knoten ist am höchsten.Wenn es ist nur eine Palette, die geht von "niedrigste" bis "höchste", die Sie nicht haben, eine pivot-und dies wäre ein Blatt.Im Idealfall würden Sie Holen sich die Zapfen, die für jeden Knoten, um den Baum zu halten ausgewogene.
Als ich dieses problem hatte, habe ich ein sortiertes array von Bereichen und eine binäre Suche zu suchen Kreuzungen.Dies ist (glaube ich) O(log n) Leistung, mit ein wenig Aufwand umgehen mit überlappenden Bereichen.
Die Antwort auf Ihre Frage ist, glaube ich, ableitbar aus dem code unten, aber stoppen kurz von der Einfügemarke.Ich präsentiere den gesamten code zu vermeiden Verwirrung durch den unterschiedlichen Kontext -, die ich brauchte, um fügen Sie eine Reihe von Unicode-codepoints in eine Liste von codepoint reicht.
-- BEARBEITEN --
Die Anpassung der code unten, um festzustellen, Kreuzungen mehrerer Bereiche beinhaltet eine triviale Suchlauf vorwärts vom Einfügepunkt bis eine Palette gefunden wird, welche nicht mehr schneidet.
-- END EDIT --
Der Range-Klasse enthält:
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;
}
Reihe Einfügen:
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;
}
Binäre Suche:
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.
}
}
