Effizienter Listenschnittpunktalgorithmus

74

Was ist bei zwei Listen (nicht unbedingt sortiert) der effizienteste nicht rekursive Algorithmus, um den Schnittpunkt dieser Listen zu finden?

mwfearnley
quelle
3
Das klingt nach einer Hausaufgabenfrage - oder?
Erik Forbes
29
Nicht wirklich. Ich bin auf der Arbeit und muss in einer statistischen Modellierungsumgebung namens eviews programmieren. In Eviews ist keine Schnittmenge festgelegt und die Rekursion wird ebenfalls nicht unterstützt. Ich benötige einen schnellen Algorithmus, da meine Sets in der Regel groß sind und das Programm häufig ausgeführt werden muss. Vielen Dank!
4
Sind die Werte in jeder Liste einzigartig? Wenn ja, können Sie sich den Listen anschließen, das Ergebnis sortieren und nach Duplikaten suchen.
Fabio Ceconello
1
Wie viele Elemente in den Sets normalerweise? (zB lohnt es sich, einen Hash zu implementieren, oder können Sie mit sorting = O (n log n)
Jason S
2
Welchen Datentyp sortieren Sie? Manchmal gibt es Merkmale der Daten, die Sie beim Entwerfen eines Algorithmus nutzen können.
AShelly

Antworten:

42

Sie können alle Elemente der ersten Liste in ein Hash-Set einfügen. Wiederholen Sie dann das zweite und überprüfen Sie für jedes seiner Elemente den Hash, um festzustellen, ob er in der ersten Liste vorhanden ist. Wenn ja, geben Sie es als Element der Kreuzung aus.

Frank
quelle
Das hört sich gut an, aber ich glaube auch nicht, dass ich Zugriff auf Hashing-Algorithmen habe. Irgendwelche Vorschläge?
4
Dann vielleicht: * Sortierliste1 (Zeit: n log n) * Sortierliste2 (Zeit: n log n) * Zusammenführen der beiden und Suchen nach ähnlichen Einträgen, während Sie die beiden sortierten Listen gleichzeitig durchlaufen (lineare Zeit)
Frank
2
Ich habe nicht genug Punkte, um andere Threads zu kommentieren, aber in Bezug auf den Punkt, dass die schnelle Sortierung rekursiv ist: Sie können sie ohne Rekursion implementieren. Siehe hier zum Beispiel: codeguru.com/forum/archive/index.php/t-333288.html
Frank
3
Wenn Sie Zugriff auf Arrays haben, können Sie sicherlich Ihre eigene Hash-Tabelle erstellen. Das Erstellen einer vernünftigen Hash-Funktion ist normalerweise recht einfach.
Keith Irwin
1
Und wie macht man das für mehrere Listen? Angenommen, Sie haben mehrere Listen und möchten eine Kreuzung über alle? Nach meinem Verständnis wird es immer noch so weitergehen: Erstellen Sie zum ersten Mal einen Hash, beginnen Sie mit der Iteration über den Rest der Listen und überprüfen Sie, ob jedes ihrer Elemente im Hash vorhanden ist.
Khan
24

Vielleicht möchten Sie einen Blick auf Bloom-Filter werfen. Sie sind Bitvektoren, die eine probabilistische Antwort geben, ob ein Element Mitglied einer Menge ist. Die eingestellte Schnittmenge kann mit einer einfachen bitweisen UND-Verknüpfung implementiert werden. Wenn Sie eine große Anzahl von Null-Schnittpunkten haben, können Sie diese mithilfe des Bloom-Filters schnell entfernen. Sie müssen jedoch immer noch auf einen der anderen hier genannten Algorithmen zurückgreifen, um den tatsächlichen Schnittpunkt zu berechnen. http://en.wikipedia.org/wiki/Bloom_filter

Aneil Mallavarapu
quelle
Dies ist ein faszinierender Ansatz, um effizient zu bestimmen, ob sich zwei große Mengen überlappen.
Rick Sladkey
9

Ohne Hashing haben Sie vermutlich zwei Möglichkeiten:

  • Der naive Weg wird sein, jedes Element mit jedem anderen Element zu vergleichen. O (n ^ 2)
  • Eine andere Möglichkeit wäre, die Listen zuerst zu sortieren und dann zu durchlaufen: O (n lg n) * 2 + 2 * O (n)
Tom Ritter
quelle
Und noch eines: Wenn es möglich ist, jedem Element eine Eigenschaft hinzuzufügen, setzen Sie sie zuerst für alle Elemente in beiden Sätzen auf Null zurück, setzen Sie sie dann in einem der Sätze auf 1 und durchsuchen Sie dann den zweiten Satz, um Elemente mit dem Eigenschaftssatz zu finden zu 1. Dies ist O(n + m)aber nicht immer möglich.
Roman Starkov
Vielleicht kann es mit einer O (log n) Binärsuche verbessert werden?
Ritter
5
Nur eine Notiz, O(n lg n) * 2 + O(n) * 2die gleich ist wie O(n lg n).
Porglezomp
Zunächst einmal ist das Sortieren einer verknüpften Liste nicht erkennbar, da Sie keinen O (1) -Zugriff haben. Sie müssen sie in ein Array verschieben. Zweitens müssen Sie nur eine Liste sortieren und dann mit jedem Element der ersten Liste eine binäre Suche durchführen.
Shinzou
7

Aus der Liste der eviews-Funktionen geht hervor, dass komplexe Zusammenführungen und Verknüpfungen unterstützt werden (wenn dies wie in der DB-Terminologie "Verknüpfung" ist, wird eine Schnittmenge berechnet). Stöbern Sie jetzt in Ihrer Dokumentation :-)

Zusätzlich hat eviews ein eigenes Benutzerforum - warum nicht dort fragen?

zvrba
quelle
6

Erstellen Sie mit Satz 1 einen binären Suchbaum mit O(log n)und iterieren Sie Satz 2 und suchen Sie die BST m X O(log n)GesamtsummeO(log n) + O(m)+O(log n) ==> O(log n)(m+1)

khaja
quelle
2
Für den binären Suchbaumteil muss noch eine der Listen sortiert werden (wodurch der Komplexität ein O (m log m) oder ein O (n log n) hinzugefügt wird). Dies ist jedoch immer noch eine sehr nützliche Antwort: In meinem Fall habe ich zwei Listen mit denselben Objekten, die jedoch jeweils nach unterschiedlichen Objektattributen sortiert sind - und ich muss herausfinden, welche Objekte in beiden Listen enthalten sind. Diese Antwort ist unabhängig von dem Attribut, nach dem jede Liste sortiert ist. Vielen Dank!
versehentlicher_PhD
2
Tatsächlich ist das Erstellen des Baums O (n log n), also ist es O ((n + m) log n) insgesamt
c-urchin
6

In C ++ kann Folgendes mithilfe der STL-Map versucht werden

vector<int> set_intersection(vector<int> s1, vector<int> s2){

    vector<int> ret;
    map<int, bool> store;
    for(int i=0; i < s1.size(); i++){

        store[s1[i]] = true;
    }
    for(int i=0; i < s2.size(); i++){

        if(store[s2[i]] == true) ret.push_back(s2[i]);

    }
    return ret;
}
Quasar
quelle
3

Hier ist eine weitere mögliche Lösung, die ich mir ausgedacht habe, um O (nlogn) in zeitlicher Komplexität und ohne zusätzlichen Speicherplatz zu verwenden. Sie können es hier überprüfen https://gist.github.com/4455373

So funktioniert es: Angenommen, die Sätze enthalten keine Wiederholungen, führen Sie alle Sätze zu einem zusammen und sortieren Sie sie. Durchlaufen Sie dann die zusammengeführte Menge und erstellen Sie bei jeder Iteration eine Teilmenge zwischen dem aktuellen Index i und i + n, wobei n die Anzahl der im Universum verfügbaren Mengen ist. Was wir beim Schleifen suchen, ist eine sich wiederholende Folge der Größe n, die der Anzahl der Mengen im Universum entspricht.

Wenn diese Teilmenge bei i gleich dieser Teilmenge bei n ist, bedeutet dies, dass das Element bei i n-mal wiederholt wird, was der Gesamtzahl der Mengen entspricht. Und da es in keiner Menge Wiederholungen gibt, bedeutet dies, dass jede der Mengen diesen Wert enthält, also fügen wir ihn dem Schnittpunkt hinzu. Dann verschieben wir den Index um i +, was zwischen ihm und n verbleibt, da definitiv keiner dieser Indizes eine sich wiederholende Sequenz bilden wird.

Ayman Farhat
quelle
Das Sortieren einer verknüpften Liste kann nicht nlogn sein
shinzou
2

Sortieren Sie zunächst beide Listen mit Quicksort: O (n * log (n). Vergleichen Sie dann die Listen, indem Sie zuerst die niedrigsten Werte durchsuchen und die allgemeinen Werte hinzufügen. Beispiel: in lua):

function findIntersection(l1, l2)
    i, j = 1,1
    intersect = {}

    while i < #l1 and j < #l2 do
        if l1[i] == l2[i] then
            i, j = i + 1, j + 1
            table.insert(intersect, l1[i])
        else if l1[i] > l2[j] then
            l1, l2 = l2, l1
            i, j = j, i
        else
            i = i + 1
        end
    end

    return intersect
end

Welches ist O(max(n, m))wo nund msind die Größen der Listen.

BEARBEITEN: Quicksort ist rekursiv, wie in den Kommentaren erwähnt, aber es sieht so aus, als gäbe es nicht rekursive Implementierungen

Wookai
quelle
Ist Quicksort nicht rekursiv? Oder gibt es eine nicht rekursive Version davon?
Ich würde das nicht O nennen (max (n, m)). Du machst auch zwei Arten.
Tom Ritter
Gibt es eine nicht rekursive Version von Mergesort, die auch funktionieren könnte?
Heapsort ist nicht rekursiv, fügt jedoch einige Datenstrukturanforderungen hinzu. Wäre es ok ?
Wookai
1
Es gibt eine nicht rekursive Quicksortierung. Schieben Sie das gesamte zu sortierende Intervall auf den Stapel. Pop in einer Schleife, dann partitionieren Sie das Intervall. Alle Intervalle, die weiter sortiert werden müssen, werden auf den Stapel verschoben. Gehen Sie zurück zum Anfang der Schleife, platzieren Sie die Partition ... Spülen Sie die Wiederholung, bis der Stapel leer ist.
EvilTeach
1

Warum implementieren Sie nicht Ihre eigene einfache Hash-Tabelle oder Hash-Set? Es lohnt sich, keine Überschneidungen zu vermeiden, wenn Ihre Listen groß sind, wie Sie sagen.

Da Sie vorher ein wenig über Ihre Daten wissen, sollten Sie in der Lage sein, eine gute Hash-Funktion auszuwählen.

Imran
quelle
1

Ich stimme der Idee der "Sets" zu. In JavaScript können Sie die erste Liste verwenden, um ein Objekt zu füllen, wobei Sie die Listenelemente als Namen verwenden. Anschließend verwenden Sie die Listenelemente aus der zweiten Liste und prüfen, ob diese Eigenschaften vorhanden sind.

Nosredna
quelle
1

Wenn Sets (wie Sie sie im Titel nennen) als integriert unterstützt werden, gibt es normalerweise eine Schnittmethode.

Wie auch immer, wie jemand sagte, Sie könnten es leicht machen (ich werde keine Postleitzahl posten, jemand hat es bereits getan), wenn Sie die Listen sortiert haben. Wenn Sie keine Rekursion verwenden können, gibt es kein Problem. Es gibt schnell rekursionsfreie Implementierungen.

Andrea Ambu
quelle
1. Wenn eviews Mengen unterstützen würden, würde es wahrscheinlich eine Methode für Mengenschnittpunkte bieten. 2. Wie kann das Verbinden von zwei Mengen hier helfen? Der Schnittpunkt sind die Elemente, die sich in beiden Mengen befinden. Wenn ich hier beitrete, denke ich an die Berechnung der Vereinigung zweier Mengen
f3lix
Java unterstützt Mengen, aber keine integrierten Schnittfunktionen.
Lensovet
2
@lensovet: Wenn es java.util.Set implementiert, gibt es die Methode java.util.Set.retainAll (Collection). In der Dokumentation heißt es: "Wenn die angegebene Sammlung auch eine Menge ist, ändert diese Operation diese Menge effektiv, sodass ihr Wert der Schnittpunkt der beiden Mengen ist."
Andrea Ambu
0

Ich habe ein paar gute Antworten aus diesen , dass Sie in der Lage sein können , anzuwenden. Ich habe noch keine Gelegenheit, sie auszuprobieren, aber da sie auch Kreuzungen abdecken, können Sie sie nützlich finden.

StingyJack
quelle
0

In PHP so etwas wie

function intersect($X) { // X is an array of arrays; returns intersection of all the arrays
  $counts = Array(); $result = Array();
  foreach ($X AS $x) {
    foreach ($x AS $y) { $counts[$y]++; }
  }
  foreach ($counts AS $x => $count) {
    if ($count == count($X)) { $result[] = $x; }
  }
  return $result;
}

quelle
1
Wenn Sie Duplikate in einem der Arrays haben, erhalten Sie ein falsches Verhalten.
Slawek
0

Aus der Definition der Big-Oh-Notation:

T (N) = O (f (N)), wenn es positive Konstanten c und n 0 gibt, so dass T (N) ≤ cf (N) ist, wenn N ≥ n 0 ist.

Was in der Praxis bedeutet, dass, wenn die beiden Listen relativ klein sind, weniger als 100 Elemente in jeweils zwei for-Schleifen gut funktionieren. Durchlaufen Sie die erste Liste und suchen Sie in der zweiten nach einem ähnlichen Objekt. In meinem Fall funktioniert es einwandfrei, da ich nicht mehr als 10 - 20 maximale Elemente in meinen Listen habe. Eine gute Lösung ist jedoch, das erste O (n log n) zu sortieren, das zweite auch O (n log n) zu sortieren und sie zusammenzuführen Die beiden Listen sind gleich groß.

Adelin
quelle