Comment puis-je réaliser l'intersection de deux listes en OCaml?

Quand j'ai deux listes en OCaml, par exemple

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

et

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

Est-il un moyen efficace pour obtenir l'intersection de ces deux listes?
I. e.:

[3; 5; 7]

Parce que je n'aime pas la numérisation de chaque élément de la liste e2 pour chaque élément de la liste e1, créant ainsi un grand Oh de l'ordonnance n^2.

OriginalL'auteur vstrien | 2010-03-04

  1. 8

    Comme Franck et Rémi dit, la conversion de vos listes de jeux (à partir de stdlib module Set) les coûts de n log(n), et puis se met en fournit un linéaire de la mise en œuvre d'intersection. Franck a également mentionné l'alternative équivalente à trier les listes, puis traverser une manière synchronisée. Ce sont à peu près la même (et par la façon dont, dans les deux cas, vous devez être en mesure de fournir un total de la commande sur les éléments de votre liste).

    Si les intersections sont une partie importante de votre algorithme et vous voulez être le plus rapide dans le cas de deux ensembles d'éléments qui ne sont que légèrement différentes, vous devez passer à un fusionnables structure comme Patricia arbres. Voir les fichiers pt* dans http://www.lri.fr/~filliatr/ftp/ocaml/ds/ .

    Si vous avez besoin d'intersection pour être le plus rapide dans tous les cas, vous avez la possibilité d'utiliser hachage consed Patricia arbres. Hash-consing aide à reconnaître structurellement identiques sous-arbres, et contribuent à la construction efficace de cache pour les opérations précédentes en faisant la comparaison à bas prix.

    Patricia arbres ne peuvent pas utiliser un type arbitraire comme clé (généralement, ils sont présentés avec des entiers comme les touches). Mais parfois il est possible de contourner cette limitation en numérotation à la création de chaque valeur que vous souhaitez utiliser en tant que clé.

    OriginalL'auteur Pascal Cuoq

  2. 5

    Mon OCaml n'est pas le meilleur, mais j'ai piraté le cette fonction qui croiseront 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 doit s'exécuter 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 à leur queue, puis vérifie pour voir si la tête de la stockées résultat est égal à la têtes de listes. Si elle ne l'est pas, il l'insère, sinon c'est un doublon et il l'ignore.

    Si elles ne sont pas égaux, c'est juste avances celle qui est la plus petite.

    La fonction semble bien pour moi. J'ai la plus petite des remarques. Si vous écrivez | h3::t3 as l -> h1::l au lieu de | h3::t3 -> h1::(h3::t3), vous pouvez enregistrer le compilateur l'attribution d'un nouveau inconvénients de cellules pour créer une nouvelle liste identique à celui qu'il possède déjà. Le compilateur pourrait faire cette optimisation elle-même, mais il ne sera probablement pas.
    Bon appel, je vais modifier mon post et ajouter que.

    OriginalL'auteur Niki Yoshiuchi

  3. 3

    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 de discbased, puis de convertir les deux listes dans les Jeux et l'utilisation de la configuration de l'intersection de l'opération.

    2. Plus généralement: Trier les deux listes, puis analyser la listes triées, ce qui permet de trouver les doublons beaucoup plus efficace. Vous prenez n log(n) pour le tri et peut trouver les doublons dans le temps linéaire alors.

    OCaml n'ont mis en fonctionnement: caml.inria.fr/pub/docs/manual-ocaml/libref/Set.S.html Notez que bot solution sont équivalent en terme de complexité (avec ocaml set).

    OriginalL'auteur Frank

  4. 3

    @Frank a suggéré, que vous pouvez utiliser pour résoudre ce problème, même si elle n'est pas la meilleure réponse, jamais, mais voici un court exemple de code montrant comment cet objectif pourrait être atteint 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 = ()

    OriginalL'auteur 0xFF

  5. 1

    Si votre liste ne contient que des entiers de taille limitée, il est aussi une solution en O(n):

    1.) Créer un tableau de booléens de la taille de vous le plus grand entier valeur de + 1 à vos listes initiales (par exemple, dans l'exemple "9+1'); définir tous les champs de faux;

    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éfinir le booléen avec le décalage à 'true', 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 au cours de la deuxième liste, 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]

    OriginalL'auteur lambdapower