Überlappung zwischen zwei großen Listen finden

-1

Ich habe zwei sehr große Listen P und Q und möchte Elemente in P finden, die auch in Q sind. Ich lese andere Threads, die Sätze vorschlagen, aber ich bin mir nicht sicher, ob das notwendig ist . Ich denke, die folgende Zeile die Notwendigkeit erfüllt:Überlappung zwischen zwei großen Listen finden

overlap = [l for l in P if l in Q]

aber ich frage mich, ob dies ein vernünftiger und schnellster Weg ist, um die Überlappung zu finden oder Sie würden unter Verwendung von Sätzen vorschlagen?

Danke.

Quelle

2016-11-13 crownLearning

Bei einem großen 'N' wird das Drehen von' Q' in ein 'Set' merkliche Auswirkungen auf die Leistung haben. Gegenwärtig ist dies "O (N^2)", d. H. Jedes Element in "P" erfordert ein "O (N)" - Nachschlagen in "Q". Mit einem Satz redest du 'O (N)', jedes Element in 'P' benötigt einen O (1) Lookup in' set (Q) '. Es gibt eine 'O (N)' Bauzeit für 'set (Q)', die im Aufschlag verschwindet, je größer das 'N' ist - also wird immer noch als' O (N) ' – AChampion

@AChampion: Ich nehme an, du meinst das OP's Algorithmus ist 'O (N^2)', nicht dass das Drehen von 'Q' in eine Menge diese Reihenfolge hat. –

Ja in der Tat, Entschuldigung, wenn das nicht klar ist. Mit mehr Information könnte es möglich sein, optimale/einfache Lösungen z.B. Multisets mit 'collections.Counter()'. – AChampion

Wie von @AChampion empfohlen, sind die Sets für diesen Zweck effizienter. Hier ist der Code für diejenigen, die interessiert sind. Sie müssen nur die größere Liste, sagen Q, in eine Liste konvertieren, dann ist

effizienter.

Quelle

2016-12-15 22:04:20 crownLearning

Wenn Sie auf die Verwendung von Mengen zurückgreifen, können Sie auch die Methode "overlap = set1.intersection (set2)" verwenden. – exfizik

Überlappung zwischen zwei großen Listen finden

Antwort

Verwandte Themen