Ich habe ein Listenverständnis, das so aussieht:
%Vor% C ist ein Diktat mit Schlüsseln, die Tupel beliebiger Integer sind. Alle Tupel haben die gleiche Länge. Im schlimmsten Fall sollten alle Kombinationen in die neue Liste aufgenommen werden. Dies kann sehr häufig passieren.
Als Beispiel habe ich ein Wörterbuch wie folgt:
%Vor%Und ich möchte das Ergebnis sein:
%Vor% Also, bei Überlappung beziehe ich mich beispielsweise darauf, dass die Tupel (1,2,3,4) und (2,3,4,5) den überlappenden Abschnitt (2,3,4) haben. Die überlappenden Abschnitte müssen sich an den "Rändern" der Tupel befinden. Ich möchte nur Überlappungen, die eine Länge kürzer als die Tupellänge haben. Daher überschneidet sich (1,2,3,4) nicht mit (3,4,5,6) . Beachten Sie auch, dass beim Entfernen des ersten oder letzten Elements eines Tupels möglicherweise nicht eindeutige Tupel auftreten, die alle mit allen anderen Elementen verglichen werden müssen. Dieser letzte Punkt wurde in meinem ersten Beispiel nicht hervorgehoben.
Der bessere Teil meiner Code-Ausführungszeit wird in diesem Listenverständnis verbracht. Ich brauche immer alle Elemente von cart , daher scheint es keine Beschleunigung zu geben, wenn stattdessen ein Generator verwendet wird.
Meine Frage ist: Gibt es einen schnelleren Weg, dies zu tun?
Ein Gedanke, den ich hatte, war, dass ich versuchen könnte, zwei neue Wörterbücher zu erstellen:
%Vor% Und füge irgendwie alle Kombinationen von Elementen der Liste in aa[i] mit der Liste in bb[i] für alle i zusammen, aber ich kann mich auch nicht um diese Idee kümmern.
Aktualisieren
Sowohl die von tobias_k als auch von shx2 hinzugefügte Lösung hat eine größere Komplexität als mein ursprünglicher Code (soweit ich das beurteilen kann). Mein Code ist O (n ^ 2), während die beiden anderen Lösungen O (n) sind. Für meine Problemgröße und -zusammensetzung scheinen jedoch alle drei Lösungen mehr oder weniger gleichzeitig zu laufen. Ich nehme an, dass dies mit einer Kombination aus Overhead verbunden ist, der mit Funktionsaufrufen verbunden ist, sowie der Art der Daten, mit denen ich arbeite. Insbesondere die Anzahl der verschiedenen Tasten sowie die tatsächliche Zusammensetzung der Tasten scheinen eine große Wirkung zu haben. Letzteres weiß ich, weil der Code für völlig zufällige Schlüssel viel langsamer läuft. Ich habe die Antwort von tobias_k akzeptiert, weil sein Code am einfachsten zu befolgen ist. Ich würde jedoch andere Vorschläge zur Durchführung dieser Aufgabe sehr begrüßen.
Sie waren tatsächlich auf dem richtigen Weg und nutzten die Wörterbücher, um alle Präfixe für die Schlüssel zu speichern. Beachten Sie jedoch, dass (soweit ich die Frage verstehe) zwei Schlüssel auch überlappen können, wenn die Überlappung kleiner als len-1 ist, z. Die Schlüssel (1,2,3,4) und (3,4,5,6) würden sich ebenfalls überschneiden. Daher müssen wir eine Karte erstellen, die alle die Präfixe der Schlüssel enthält. (Wenn ich mich diesbezüglich täusche, lasse einfach die zwei inneren for Schleifen fallen.) Sobald wir diese Map haben, können wir ein zweites Mal über alle Schlüssel iterieren und prüfen, ob es für ihre Suffixe passende Schlüssel gibt prefixes Karte. ( Update: Da Schlüssel mehrere Präfixe / Suffixe überlappen können, speichern wir die überlappenden Paare in einem Satz.)
(Bitte beachten Sie, dass es für die Einfachheit nur auf die Schlüssel im Wörterbuch ankommt, nicht auf die Werte. Erweitern Sie dies, um auch die Werte zurückzugeben, oder dies als Nachbearbeitungsschritt, sollte trivial sein.)
Die Gesamtlaufzeit sollte nur 2*n*k sein, n ist die Anzahl der Schlüssel und k die Länge der Schlüssel. Die Raumkomplexität (die Größe der Karte prefixes ) sollte zwischen n*k und n^2*k liegen, wenn es sehr viele Schlüssel mit denselben Präfixen gibt.
Hinweis: Die obige Antwort gilt für den allgemeineren Fall, dass der überlappende Bereich eine beliebige Länge haben kann. Für den einfacheren Fall, dass Sie nur ein kürzeres als das ursprüngliche Tupel betrachten, sollte das Folgende ausreichen und die in Ihren Beispielen beschriebenen Ergebnisse liefern:
%Vor%Tags und Links python algorithm performance dictionary itertools