Comment croiser deux listes dans OCaml?

Question

Quand j'ai deux listes dans OCaml, par exemple

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

et

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

Y at-il un moyen efficace pour obtenir l'intersection de ces deux listes? i.e. .:

[3; 5; 7] 

Parce que je n'aime pas numériser tous les éléments dans la liste e2 pour chaque élément dans la liste e1, créant ainsi un grand Oh d'ordre n^2.

Answer 1

Comme Franck et Rémi dit, la conversion de vos listes de jeux (à partir du module stdlib Set) les coûts log n (n), et définit ensuite fournit une implémentation linéaire d'intersection. Franck a également mentionné l'alternative équivalente pour trier les listes, puis les parcourir de manière synchronisée. Ce sont à peu près les mêmes (et en passant, dans les deux cas, vous devez être en mesure de fournir un total de commande sur les éléments de vos listes). Si les intersections sont une partie importante de votre algorithme et si vous voulez qu'elles soient plus rapides dans le cas de deux ensembles d'éléments qui ne sont que légèrement différents, vous devez passer à une structure fusionnable telle que les arborescences Patricia. Voir les fichiers pt* dans http://www.lri.fr/~filliatr/ftp/ocaml/ds/.

Si vous avez besoin d'intersection pour être rapide dans tous les cas, vous avez la possibilité d'utiliser des arbres Patricia à hachage. Hash-consing aide à reconnaître des sous-arbres structurellement identiques, et aide à construire des caches efficaces pour les opérations précédentes en rendant la comparaison bon marché.

Les arborescences Patricia ne peuvent pas utiliser un type arbitraire en tant que clé (généralement, elles sont présentées avec ints en tant que clés). Mais vous pouvez parfois contourner cette limitation en numérotant à la création chaque valeur que vous avez l'intention d'utiliser comme clé.

Answer 2

Je ne sais pas OCaml (syntaxe sage), mais en général vous pouvez le faire de deux façons:

1. Si votre langue a un support pour un ensemble-structure de données, puis de convertir les deux listes en jeux et utilisez l'opération set-intersection. Plus généralement: Triez les deux listes, puis analysez les listes triées, ce qui rend la recherche des doublons beaucoup plus efficace. Vous prenez n log (n) pour le tri et pouvez trouver les doublons en temps linéaire alors.

Answer 3

Mon OCaml est pas le meilleur, mais je piraté cette fonction ensemble, ce qui coupera les listes triées:

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

qui devrait fonctionner en O (n + m) temps. Fondamentalement, il vérifie le premier élément de chaque liste. Si elles sont égales, il stocke le résultat de l'appel récursif à leurs queues, puis vérifie si la tête du résultat stocké est égale aux têtes des listes. Si ce n'est pas le cas, il l'insère, sinon c'est un doublon et il l'ignore.

Si elles ne sont pas égales, il suffit d'avancer celui qui est le plus petit.

Answer 4

Comme @Frank suggéré, vous pouvez utiliser des ensembles pour résoudre ce problème, bien qu'il ne soit pas la meilleure réponse jamais, mais voici un code court liste montrant comment cela pourrait être réalisé en 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;; 

la sortie est:

3 
5 
7 
- : unit =() 

Answer 5

Si vos listes ne contient que des nombres entiers d'une taille limitée, il y a aussi une solution en O (n):

1.) Créer un tableau de booléens de la taille de y ou la plus grande valeur entière plus 1 dans vos listes d'origine (p. dans votre exemple '9 + 1'); définissez tous les champs sur false;

let m = Array.create 10 false

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

2.) itérer sur la première liste: Pour chaque élément que vous rencontrez, définissez le booléen avec le décalage 'vrai' respectif; dans votre exemple, cela donnerait

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

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

3.) filtre sur la deuxième liste, en ne gardant que les éléments dont le champ correspondant dans le tableau est vrai

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

->[3; 5; 7]