Wie überschneide ich zwei Listen in OCaml?

Wie Franck und Rémi gesagt haben, kostet das Konvertieren Ihrer Listen in Mengen (aus dem stdlib-Modul Set) n log (n), und dann liefert Sets eine lineare Implementierung der Schnittmenge. Franck erwähnte auch die äquivalente Alternative, um die Listen zu sortieren und sie dann synchron zu durchlaufen. Diese sind ungefähr gleich (und in beiden Fällen müssen Sie in der Lage sein, eine vollständige Reihenfolge für die Elemente in Ihren Listen anzugeben).

Wenn Schnittpunkte ein wichtiger Teil Ihres Algorithmus sind und Sie möchten, dass sie bei zwei Gruppen von Elementen, die nur geringfügig voneinander abweichen, schneller sind, müssen Sie zu einer zusammenfügbaren Struktur wechseln, wie z Patricia Bäume. Siehe Dateien pt* in Ссылка .

Wenn Sie eine Kreuzung brauchen, um in allen Fällen schnell zu sein, haben Sie die Möglichkeit, Hash-konzedierte Patricia-Bäume zu verwenden. Hash-Consing hilft dabei, strukturell identische Sub-Bäume zu erkennen und hilft dabei, effiziente Caches für frühere Operationen zu erstellen, indem es einen Vergleich billig macht.

Patricia-Bäume können keinen beliebigen Typ als Schlüssel verwenden (normalerweise werden sie mit Ints als Schlüssel dargestellt). Sie können diese Einschränkung jedoch manchmal umgehen, indem Sie bei der Erstellung jeden Wert nummerieren, den Sie als Schlüssel verwenden möchten.

Mein OCaml ist nicht der beste, aber ich habe diese Funktion zusammengehackt, die sortierte Listen überschneiden wird:

sollte in O (n + m) Zeit laufen. Grundsätzlich überprüft es das erste Element jeder Liste. Wenn sie gleich sind, speichert sie das Ergebnis des rekursiven Aufrufs an ihren Schwänzen und prüft dann, ob der Kopf des gespeicherten Ergebnisses gleich dem Kopf der Listen ist. Wenn nicht, fügt es es ein, andernfalls ist es ein Duplikat und es ignoriert es.

Wenn sie nicht gleich sind, wird nur der kleinere Wert angezeigt.

Ich kenne OCaml (Syntax-weise) nicht, aber im Allgemeinen können Sie dies auf zwei Arten tun:

1. Wenn Ihre Sprache eine Set-Datenstruktur unterstützt, dann konvertieren Sie beide Listen in Sets und verwenden Sie die set-intersection-Operation.

2. Allgemeiner: Sortieren Sie beide Listen und scannen Sie dann die sortierten Listen, was das Auffinden der Duplikate wesentlich effizienter macht. Sie nehmen n log (n) zum Sortieren und können dann die Duplikate in linearer Zeit finden.

Wie von @Frank vorgeschlagen, können Sie Sets verwenden, um dieses Problem zu lösen, obwohl es nicht die beste Antwort aller Zeiten ist, aber hier ist ein kurzer Code, der demonstriert, wie dies in OCaml erreicht werden kann:

Die Ausgabe ist:

Wenn Ihre Listen nur ganze Zahlen begrenzter Größe enthalten, gibt es auch eine Lösung in O (n):

1.) Erstellen Sie ein Array von booleschen Werten der Größe Ihres größten ganzzahligen Werts plus 1 in Ihren ursprünglichen Listen (z. B. in Ihrem Beispiel '9 + 1'); setze alle Felder auf false;

let m = Array.create 10 false

- & gt; [|false; false; false; false; false; false; false; false; false; false|]

2.) Iterate über die erste Liste: Setzen Sie für jedes gefundene Element den Boolean mit dem entsprechenden Offset auf 'true'; In Ihrem Beispiel würde dies

List.iter (fun x -> m.(x) <- true) e1

- & gt; [|false; false; false; true; true; true; true; true; false; false|]

3.) Filtern Sie über die zweite Liste, wobei Sie nur die Elemente beibehalten, deren entsprechendes Feld im Array wahr ist

List.filter (fun x -> m.(x) = true) e2

- & gt; [3; 5; 7]