Wie überschneide ich zwei Listen in OCaml?

Question

Wenn ich zwei Listen in OCaml, zum Beispiel

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

und

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

Gibt es eine effiziente Möglichkeit, den Schnittpunkt dieser beiden Listen zu bekommen? d.h .:

[3; 5; 7] 

Da ich mag nicht jedes Element in der Liste e2 Abtastung für jedes Element in der Liste e1, wodurch eine große Oh der Ordnung n^2 zu schaffen.

Answer 1

Als Franck und Rémi sagte, Ihre Listen zu Sätzen (von stdlib Modul Set) Umwandlung Kosten n log (n), und stellt dann liefert eine lineare Umsetzung der Kreuzung. 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 der Elemente in Ihren Listen anzugeben).

Wenn Kreuzungen ein wichtiger Teil Ihres Algorithmus sind und Sie wollen, dass sie im Fall von zwei Gruppen von Elementen, schneller sein, die nur geringfügig unterschiedlich sind, müssen Sie eine zusammenführbar Struktur wechseln wie Patricia Bäume. Siehe Dateien pt* in http://www.lri.fr/~filliatr/ftp/ocaml/ds/.

Wenn Sie eine Kreuzung benötigen, 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, effiziente Caches für frühere Operationen zu erstellen, indem Vergleich billig gemacht wird.

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.

Answer 2

Ich weiß nicht, OCaml (Syntax-weise), aber in der Regel können Sie dies auf zwei Arten tun:

1. Wenn Ihre Sprache Unterstützung für eine Set-Datenstruktur hat, dann beide Listen in Sets umwandeln und verwende die Set-Intersection-Operation.

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

Answer 3

Mein OCaml ist nicht die beste, aber ich gehackt diese Funktion zusammen, die Listen sortiert schneidet:

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 in O laufen sollte (n + m) Zeit. 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. Ist dies nicht der Fall, wird es eingefügt, andernfalls ist es ein Duplikat und ignoriert es.

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

Answer 4

Als @Frank vorgeschlagen, man setzt dieses Problem lösen kann, obwohl es überhaupt nicht die beste Antwort ist, aber hier ist ein kurzer Code zeigt die Auflistung, wie dies in OCaml erreicht werden kann:

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;; 

der Ausgang ist:

3 
5 
7 
- : unit =() 

Answer 5

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

1.) erstellen einen Arrays von booleschen der Größe y o der größte ganzzahlige Wert plus 1 in Ihren ursprünglichen Listen (z. in Ihrem Beispiel '9 + 1'); setze alle Felder auf false;

let m = Array.create 10 false

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

2.) Iterate über die erste Liste: Für jedes Element auftreten, stellen Sie den boolean mit dem jeweiligen Offset auf 'true'; in Ihrem Beispiel würde dies

Ausbeute

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

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

3.) die zweiten Liste Filter über, nur die Elemente, von denen in der Anordnung das entsprechende Feld hält wahr ist

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

->[3; 5; 7]