KEINE SETS!
Ich kann keine Sets verwenden, weil:
Gibt es nur die Endpunkte der Bereiche, um zwei Listen von Bereichen optimal zu subtrahieren?
Danke.
Eine Lösung (zusätzlich zu all den anderen verschiedenen Lösungen, die hier vorgestellt wurden) ist die Verwendung eines Intervall- / Segmentbaums (sie sind wirklich das Gleiche):
Ein großer Vorteil dabei ist, dass es einfach ist, beliebige boolesche Operationen (nicht nur Subtraktionen) mit demselben Code auszuführen. Diese Datenstruktur wird standardmäßig in de Berg behandelt. Um eine boolesche Operation für ein Paar von Intervallbäumen durchzuführen (einschließlich der Subtraktion), fügen Sie sie einfach zusammen. Hier ist ein (zugegebenermaßen naive) Python-Code dafür, dies mit unsymmetrischen Bereichsbäumen zu tun. Die Tatsache, dass sie unausgewogen sind, hat keinen Einfluss auf die Zeit, die zum Zusammenführen der Bäume benötigt wird, jedoch ist die Baumkonstruktion hier der wirklich dumme Teil, der letztendlich quadratisch ist (außer die Reduzierung wird durch Partitionierung ausgeführt, was ich irgendwie bezweifle). Wie auch immer du gehst:
%Vor%Ich schrieb diese Art von schnell und habe es nicht so viel getestet, so dass es Fehler geben konnte. Beachten Sie auch, dass dieser Code mit beliebigen booleschen Operationen arbeitet, nicht nur mit Unterschieden (Sie übergeben sie einfach als Argument an op in der Zusammenführung). Die zeitliche Komplexität der Auswertung von diesen ist linear von der Größe des Ausgabebaums (was auch die gleiche ist wie die Anzahl der Intervalle im Ergebnis). Als Beispiel habe ich den Fall ausgeführt, den Sie angegeben haben:
%Vor%Und ich habe folgende Ausgabe:
[(1, 29), (51, 59), (201, 1000), (1100, 1149)]
Das scheint mit dem übereinzustimmen, was Sie erwarten würden. Wenn Sie nun andere boolesche Operationen ausführen möchten, ist dies die gleiche Funktion:
%Vor%Hier ist eine schnelle Python-Funktion, die die Subtraktion durchführt, unabhängig davon, ob die Anfangslisten wohlgeformt sind (d. h. die Listen vor der Subtraktion in die kleinste Liste äquivalenter Bereiche sortiert, sortiert):
%Vor%Das war ein interessantes Problem!
Ich denke, das ist richtig, und es ist ziemlich kompakt. Es sollte mit überlappenden Bereichen aller Arten arbeiten, aber es nimmt wohlgeformte Bereiche an (d. H.% Co_de% wo [x, y) ). Es verwendet x < y style-Bereiche zur Vereinfachung. Es basiert auf der Beobachtung, dass es wirklich nur sechs mögliche Anordnungen gibt (mit Ergebnissen in ()):
Bearbeiten : Ich habe eine kompaktere Darstellung gefunden:
%Vor% Bei einer sortierten Liste von Endpunkten, wenn [x, y) , sollten die ersten beiden Endpunkte im Ergebnis enthalten sein. Wenn endpoints[0] == s1 , dann sollten die letzten beiden Endpunkte im Ergebnis sein. Wenn keine, dann sollte es kein Ergebnis geben.
Ich habe es nicht viel getestet, daher ist es durchaus möglich, dass etwas nicht stimmt. Bitte lassen Sie mich wissen, wenn Sie einen Fehler finden!
%Vor%Getestet:
%Vor%