Wie kann ich die Schnittmenge zweier Listen in OCaml?

Wenn ich zwei Listen in OCaml, zum Beispiel

e1 = [3; 4; 5; 6; 7]

und

e2 = [1; 3; 5; 7; 9]

Ist es ein effizienter Weg, um die Schnittmenge dieser beiden Listen?
I. e.:

[3; 5; 7]

Weil ich weiß nicht wie das Scannen jedes element in der Liste e2 für jedes element in der Liste e1, wodurch eine grosse Oh der Ordnung n^2.

InformationsquelleAutor vstrien | 2010-03-04
  1. 8

    Als Franck und Rémi sagte, konvertieren Sie Ihre Listen setzt (aus stdlib-Modul-Set) Kosten n log(n), und Setzt dann bietet sich eine lineare Umsetzung der Kreuzung. Franck erwähnte auch die gleichwertige alternative zu Sortieren, die Listen, und dann durchqueren Sie in einer synchronisierten Art und Weise. Diese sind etwa die gleichen (und durch die Art und Weise, in beiden Fällen müssen Sie in der Lage sein, um eine Gesamt-Bestellung auf die Elemente in Ihren Listen).

    Wenn Kreuzungen sind ein wichtiger Teil des Algorithmus und Sie wollen, dass Sie schneller in den Fall von zwei Mengen von Elementen, die nur geringfügig anders ist, müssen Sie zum Umschalten auf ein zusammenführbare Struktur wie Patricia-Bäume. Siehe Dateien pt* im http://www.lri.fr/~filliatr/ftp/ocaml/ds/ .

    Wenn Sie brauchen, Kreuzung, schnell und in allen Fällen haben Sie die Möglichkeit der Verwendung von hash-consed Patricia-Bäume. Hash-consing hilft zu erkennen, strukturell identische sub-Bäumen, und bauen effiziente caches, die für frühere Operationen durch Vergleich Billig.

    Patricia-Bäume nicht verwenden, kann ein beliebiger Typ als Schlüssel (Sie sind in der Regel präsentiert mit int-Werte als Schlüssel). Aber manchmal kann man diese Einschränkung umgehen, indem die Nummerierung bei der Erstellung jeder Wert, den Sie verwenden möchten, wie einen Schlüssel.

    InformationsquelleAutor Pascal Cuoq
  2. 5

    Meine OCaml ist nicht die beste, aber ich hackte diese Funktion zusammen, die intersect-sortierte Listen:

    let rec intersect l1 l2 =
    match l1 with [] -> []
        | h1::t1 -> (
          match l2 with [] -> []
              | h2::t2 when h1 < h2 -> intersect t1 l2
              | h2::t2 when h1 > h2 -> intersect l1 t2
              | h2::t2 -> (
                match intersect t1 t2 with [] -> [h1]
                    | h3::t3 as l when h3 = h1 -> l
                    | h3::t3 as l -> h1::l
              )
        );;

    die sollten laufen in O(n+m) Zeit. Grundsätzlich prüft es das erste element der jeweiligen Liste. Wenn Sie gleich sind, speichert er das Ergebnis des rekursiven Aufrufs, um Ihre Schwänze, und dann überprüft, um zu sehen, wenn der Kopf der gespeicherte Ergebnis ist gleich um die Köpfe der Listen. Wenn nicht, fügt es es, sonst ist es ein Duplikat und er ignoriert es.

    Wenn Sie nicht gleich sind, ist es nur Fortschritte, je nachdem, was ein kleiner ist.

    • Die Funktion scheint in Ordnung zu mir. Ich habe die kleinste Bemerkungen obwohl. Wenn Sie schreiben | h3::t3 as l -> h1::l statt | h3::t3 -> h1::(h3::t3) können Sie der compiler die Zuweisung an eine neue cons-Zelle, um eine neue Liste erstellen, identisch zu einem der es schon hat. Der compiler könnte dies tun-Optimierung selbst, aber es wahrscheinlich nicht.
    • Gute Entscheidung, ich werde meinen Beitrag Bearbeiten und hinzufügen, dass.
    InformationsquelleAutor Niki Yoshiuchi
  3. 3

    Ich weiß nicht, OCaml (syntax-Weise), aber im Allgemeinen können Sie dies auf zwei Arten tun:

    1. Wenn Ihre Sprache hat die Unterstützung für eine Set-datastructure, dann konvertieren Sie die beiden Listen in Sets und verwenden Sie die set-intersection-operation.

    2. Allgemein: Sortieren der beiden Listen, und Scannen Sie dann die sortierten Listen, die das Auffinden der Duplikate viel effizienter. Sie nehmen n log(n) für das Sortieren und finden der Duplikate in linearer Zeit dann.

    InformationsquelleAutor Frank
  4. 3

    Als @Frank vorgeschlagen, die Sie verwenden können, setzt um dieses problem zu lösen, aber es ist nicht die beste Antwort immer, aber hier ist eine kurze code-listing demonstriert, wie dies erreicht werden könnte, die in OCaml :

    module Int_set = Set.Make (struct
                             type t = int
                             let compare = compare
                           end);;

(* iters through a list to construct a set*)
let set_of_list = List.fold_left (fun acc x -> Int_set.add x acc) Int_set.empty;;

let e1 = [3; 4; 5; 6; 7];;
let e2 = [1; 3; 5; 7; 9];;

let s1 = set_of_list e1;;
let s2 = set_of_list e2;;

(*result*)
let s3 = Int_set.inter s1 s2;;


(*testing output*)
Int_set.iter (fun elt -> print_int elt;print_string "\n") s3;;

    Ausgabe :

    3
5
7
- : unit = ()
    InformationsquelleAutor 0xFF
  5. 1

    Wenn Ihr Listen enthält nur ganze zahlen, eine begrenzte Größe, gibt es auch eine Lösung in O(n):

    1.) Erstellen Sie ein array von booleans der Größe, die Sie größten integer-Wert plus 1 in Ihrer ursprünglichen Listen (z.B. in deinem Beispiel '9+1'); legen Sie alle Felder auf false;

    let m = Array.create 10 false

    -> [|false; false; false; false; false; false; false; false; false; false|]

    2.) Iteration über die erste Liste: Für jedes element, das Sie stoßen, legen Sie die boolean mit den entsprechenden offset auf 'true'; in deinem Beispiel würde dieser Ertrag

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

    -> [|false; false; false; true; true; true; true; true; false; false|]

    3.) Filter über die zweite Liste, halten Sie nur die Elemente, aus denen das entsprechende Feld im array true ist

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

    -> [3; 5; 7]

    InformationsquelleAutor lambdapower
  6. 0

    Ich glaube nicht, dass meine Lösung ist O(n), aber es ist sehr kurz, und vielleicht für Leute interessant, die sind nicht begrenzt durch die Komplexität von constraints (diese Antwort ist eines der ersten Suchergebnisse für "Ocaml-intersect-Liste")

    Diese Funktion gibt true zurück, wenn die Schnittmenge nicht leer ist. In anderen Worten, es wird geprüft, ob zwei Listen teilen Elemente, wenn ja, wird true, sonst false.

    let intersect l1 l2 =
    List.fold_left (fun acc x -> if (List.exists (fun y -> y = x) l1) then true else acc) false l2;;

    Sehr ähnlich ist, liefert diese Funktion die eigentliche Kreuzung.

    let intersect l1 l2 =
    List.fold_left (fun acc x -> if (List.exists (fun y -> y = x) l1) then x::acc else acc) [] l2;;

    Fühlen Sie sich frei, mich zu korrigieren, wenn meine Lösung nicht korrekt ist. Es sollte sein, 'Verwandlung', wie x und y kann jede Art verglichen werden kann.

    InformationsquelleAutor charel-f
Schreibe einen Kommentar