Ich habe ein Zeitintervall wie folgt:
%Vor%und ich habe mehr Liste von Zeitpunkten, mit unterschiedlicher Länge, zum Beispiel:
%Vor% Dabei steht t1 [3,6] für das erste Intervall, [6,9] für die Sekunde usw.
Dasselbe gilt für t2 und andere Liste.
Jetzt muss ich die Liste und das spezifische Intervall speichern, die sich mit dem ersten Zeitintervall schneiden. Zum Beispiel in t1 Ich habe [3,6] , die sich in [5,10], [6,9] schneiden, die sich mit [5,10] usw. schneiden.
Ich habe einen Algorithmus erstellt, aber ich arbeite mit mehr Daten und brauche einen schnellen Algorithmus. Wenn ich zum Beispiel mit 300.000 Listen arbeite und jede Liste 200 Zeitpunkte hat, ist mein Algorithmus in etwa 5-10 Sekunden in Ordnung. Aber wenn ich 10.000 oder mehr Zeitpunkte habe, ist der Algorithmus sehr langsam.
Mein Algorithmus ist so:
%Vor%Edit1: Ja, ich habe eine Liste bestellt.
Edit2: Ich habe ein anderes Problem, wenn ich die Intersaction finde, muss ich eine Punktzahl zwischen 0 und 1 berechnen, wie die Kreuzung groß ist. Ich benutze das:
%Vor%Ich kann das auch beschleunigen?
In erster Linie ist Ihre Datenstruktur verwirrend - wenn Sie versuchen, über diskrete Zeitintervalle zu sprechen, strukturieren Sie Ihre Daten so; zum Beispiel int[][] , wobei das innere Array immer die Länge 2 hat, also wird Ihr t1 zu
Die richtige Struktur hilft Ihnen wahrscheinlich, Ihren Algorithmus zu vereinfachen und die Arbeit zu vereinfachen.
Besser als richtig strukturierte Arrays wäre es jedoch, einen dedizierten Typ zu verwenden, um diese Intervalle darzustellen, so dass Sie List<Interval> -Objekte weitergeben und eine Art "contains" -Überprüfung durchführen könnten. Aber erfinde das Rad nicht neu. Die beeindruckende Guava-Bibliothek bietet einen robusten Range Klasse, die Sie verwenden können. Aber noch besser: RangeSet und RangeMap Klassen, die Sie ganz einfach erreichen Mach die Dinge, über die du redest. Siehe auch den Artikel Bereiche erklärt , der die Grundlagen behandelt.
Beachten Sie, dass Sie Ihr aktuelles Design sehr einfach intern in Range -Objekte umwandeln können, wenn Sie die Array-Struktur nicht extern neu gestalten können.
Nachdem ich einmal versucht habe, meine eigene Klasse IntervalSet zu erstellen, möchte ich Ihnen sagen, dass es ein schwieriges Problem ist, richtig zu kommen, und Sie sich mit ihren gut durchdachten und getesteten Reichweiten-Utilities eine Menge Kopfschmerzen ersparen / p>
Hier ist die Art und Weise, wie ich das tun würde, was Sie mit Guava beschreiben - beachten Sie, dass wir es vermeiden, darüber nachzudenken - Range macht das Richtige für uns:
Verwenden Sie Ihre Beispiele:
%Vor%Das obige gibt aus:
%Vor%
Der Schnittpunkt zweier Intervalle [s1, s2] und [t1, t2] ist leer genau dann, wenn :
%Vor%Wenn Sie also in zwei Intervallen prüfen wollen, ob sich die beiden schneiden oder nicht, müssen Sie nur den obigen Test durchführen.
Auch wenn Sie wissen, dass s2 & lt; t1 dann gibt es keinen Grund, weiter auf der Liste zu gehen, die t1 gebracht hat, da sich die größeren Intervalle niemals schneiden werden, was bedeutet, dass Sie weitergehen sollten.
Naive Psuedo-Algorithmus:
%Vor%Dies kann ziemlich verbessert werden, um wirklich die Tatsache zu nutzen, dass [t1, t2, .., t (n)] sortiert ist.
Bitte beachten Sie, dass [s1, s2] sich mit [t(x), t(x+1)] iff t(x+1) >= s1 und s2 >= t(x)
Jedoch
%Vor%auch
%Vor% Also, wenn wir das kleinste i finden, so dass t (i + 1) & gt; = s1, dann erfüllen alle Intervalle von [t(i), t(i+1)] vor der ersten Bedingung des Schnittpunkts; d. h. ( [t(i+1), t(i+2)] , [t(i+2), t(i+3)] ...)
und wenn wir das größte j finden, so dass s2 & gt; = t (j-1) dann erfüllen alle Intervalle von [t(j-1), t(j)] rückwärts die zweite Bedingung. d. h. ( [t(j-2), t(j-1)] , [t(j-3), t(j-2)] ...)
Alle Intervalle zwischen i und j erfüllen beide Kriterien und nur sie.
Also ist der endgültige Algorithmus:
%Vor% Da {t1, t2, t3...t(n)} sortiert ist, können wir die binäre Suche verwenden, um die Indizes i und j effizient zu finden
EDIT2:
Der Schnittpunkt von [s1, s2] und [t1, t2] ist:
[max(s1, t1), min(s2,t2)]
die Größen sind:
%Code%
%Code%
L1 = s2-s1
Die gesuchte Punktzahl ist: L2 = t2-t1 eine Punktzahl zwischen 0 und 1.
Die Kosten für die Berechnung sind 3 Tests, 3 minus Operationen und eine Gleitkommaoperation.
Aber ich gehe davon aus, dass die Intervalle gültig sind und der Schnittpunkt existiert, sonst werden mehr Tests benötigt. ( L3 = min(s2,t2) - max(s1,t1) , L3/ min(L2, L1) und s2>s2 . Der letzte Test ist die gleiche iff Bedingung für die Schnittmenge aus der obigen Diskussion.
Vorgegebene linke Grenze und Länge von zwei Intervallen, Kreuzung kann mit dem folgenden Code getestet werden.
%Vor%Es gibt einen kurzen Artikel , in dem dieser Ansatz diskutiert wird. Darüber hinaus wird eine alternative Darstellung von Intervallen (unter Verwendung von Mittelpunkt und Länge) vorgestellt, für die ein Schnittstellentest effizienter durchgeführt werden kann.