IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Caml Discussion :

Suppression doublon dans une listes des couples de valeurs


Sujet :

Caml

  1. #1
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2012
    Messages
    4
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2012
    Messages : 4
    Points : 0
    Points
    0
    Par défaut Suppression doublon dans une listes des couples de valeurs
    Bonjour.

    Je débute un peu en Ocaml et je me retrouve face à un problème. J'ai en effet une liste de couple (x,y) et j'aurais aimé obtenir la liste épurer de tout les couples qui ont la même valeur de y mais une valeur de x différente; et par la suite supprimé les doublons de couples identiques. Ainsi pour une liste (1,3),(2,4),(2,3),(2,4),(3,5) par exemple, le résultat que j'aimerais serais (2,4),(3,5).

    Je pensais faire quelque chose comme ça (pour la partie suppression des couples avec un Y identique et un X différent):

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    let liste_pur = List.find_all (fun (x,y) -> not (
       List.exists (fun (x',y') -> (y=y') && not(x=x')) liste_assig)
    ) liste_assig ;;
    Ce qui semble marcher. Par contre je ne vois pas comment supprimer les doublons. J'ai dût mal à en visualiser le procédé. Je suis donc ouvert à toutes solutions.

  2. #2
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Bonjour.

    Ceci est un problème intéressant en termes d'algorithmie d'une part (donc indépendamment du langage) et en termes de programmation Caml (implémentation).

    Par exemple, une question à se poser est "est-ce que l'ordre de la liste en retour a de l'importance ?" (= est-ce que les éléments peuvent être retournés dans le désordre ?).

    Si l'ordre n'a pas d'importance, alors tu peux trouver une implémentation ayant une complexité proche de O(n) en utilisant une structure de données telle que HashTable :
    http://caml.inria.fr/pub/docs/manual...f/Hashtbl.html

    Une HashTable offre d'excellentes performances tant qu'on n'a pas besoin de la redimensionner (sinon ça tombe à O(n)).

    Ton algorithme devrait donc ressembler à ceci :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    Mesurer la longueur len de ta liste l
     
    Créer une Hashtbl h de capacité len (le nombre maximum d'éléments en retour)
     
    Pour chaque élément (x, y) de la liste l:
    - vérifier si l'entrée pour y existe dans h, et mettre à jour cette entrée en conséquence
     
    À la fin, parcourir h avec un Hashtbl.fold pour retourner la liste d'éléments n'apparaîssant qu'une seule fois
    Les performances devraient être bonnes, mais l'ordre n'est pas garanti.


    Si l'ordre a de l'importance, alors la complexité devient O(n^2) et il y a plusieurs façons de procéder :

    - solution 1 (non récursive terminale) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    Pour la liste vide [] -> liste vide []
     
    Pour une liste ((x, y) as head)::tail ->
      Réduire tail
      Chercher un élément (x1, y) dans tail (réduite), 3 possibilités (à implémenter):
      - (_, y) n'existe pas
      - (x1, y) existe et x égale x1
      - (x1, y) existe et x différent de x1
    EDIT: En fait, l'opération de "réduction" est plus compliquée que ça, car elle doit indiquer si des "doublons" ont été détectés ou non. Un peu comme pour la solution avec HashTable, mais en O(n).


    - solution 2 :

    On utilise un "accumulateur" (acc), au départ vide [].
    On ajoute des éléments en tête de acc au fur et à mesure. À la fin, on "renverse" acc ( List.rev acc ) pour avoir les éléments dans le bon ordre.

    EDIT: complément d'info (mais je ne vais pas vous donner la solution)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    Pour une liste ((x, y) as head)::tail  :
      Vérifier s'il existe un élément (x1, y) dans tail , 3 possibilités (à prendre en compte) :
      - (_, y) n'existe pas
      - (x1, y) existe et x égale x1
      - (x1, y) existe et x différent de x1
      
    Liste vide [] -> "Renverser" acc
    Contrainte supplémentaire : vérifier s'il est possible d'implémenter cette solution de manière récursive terminale.


    Chacune de ces solutions permet de voir des aspects très différents :
    - solution "hashtable" : hashtbl, variants, fold
    - solution 1 : récursivité
    - solution 2 : récursivité et accumulateurs

    EDIT:

    Il existe encore une autre solution possible :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    Pour une liste ((x, y) as head)::tail ->
      Séparer tail en 2 listes ( List.partition ) :
      - l1, la liste des éléments (x1, y1) tels que y1 = y
      - l2, les autres éléments
     
      Vérifier si, pour tout élément (x1, y1) de l1 on a x1 = x.
      En déduire si (x, y) fait partie de la solution ou non (et l'ajouter le cas échéant à l'accumulateur acc)
     
      Appeler récursivement la fonction sur l2
     
    Pour la liste vide [] -> "Renverser" acc
    Le but ici est de supprimer des valeurs au fur et à mesure (vérifier ce que cela donne niveau performances).


    Bref, un exercice très intéressant...
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

  3. #3
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Je ne vois pas vraiment pourquoi en conservant l'ordre on aurait besoin de O(n²) ? Pourquoi ne pas simplement utiliser le Hash comme filtre lors d'une deuxième passe sur la liste d'origine après l'avoir rempli par une première passe comme tu l'as décrite ? Chaque passe étant en O(n) le tout est en O(n).

    Je résume :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    Créer un Hash de Set de bonne taille
    Parcourir la liste et ajouter l'élément x au Set à la clé y pour chaque paire (x,y) rencontrée
    Filtrer la liste en ne gardant (x,y) que si la taille du Set en y est 1 (et supprimer ce Set pour filtrer les doublons suivants)
    Mon OCaml est rouillé mais en Haskell (qui est très similaire), j'écrirais :

    Code Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    module DistilleList (distille) where
    import Data.List (foldl')
    import qualified Data.Map.Strict as M
    import qualified Data.IntSet as S
     
    distille xs = reverse . fst . foldl' go ([],byYthenX) $ xs
      where
        byYthenX = foldl' (\m (x,y) -> M.alter (Just . createOrInsert x) y m) M.empty xs
     
        createOrInsert x Nothing  = S.singleton x
        createOrInsert x (Just s) = S.insert x s
     
        go original@(acc, mapOfSets) p@(x,y) =
          if S.size (M.findWithDefault S.empty y mapOfSets) == 1
          then (p:acc, M.delete y mapOfSets)
          else original

    Deux passes à travers la liste, chaque traitement d'un élément devrait être en O(log n * log n) parce que Data.Map et Data.IntSet sont des structures de données persistentes (mais en OCaml il est possible d'utiliser un Hash pour éviter ce coût), le coût total est donc en O(n log n log n) (ou O(n) avec une HashTable en OCaml). On peut également utiliser un type plus approprié que Set pour se débarrasser d'un log n, comme "None | Only a | Several".

    --
    Jedaï

  4. #4
    Rédacteur
    Avatar de pcaboche
    Homme Profil pro
    Inscrit en
    Octobre 2005
    Messages
    2 785
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Singapour

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 785
    Points : 9 716
    Points
    9 716
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Je ne vois pas vraiment pourquoi en conservant l'ordre on aurait besoin de O(n²) ? Pourquoi ne pas simplement utiliser le Hash comme filtre lors d'une deuxième passe sur la liste d'origine après l'avoir rempli par une première passe comme tu l'as décrite ? Chaque passe étant en O(n) le tout est en O(n).
    Oui, c'est vrai.

    Je n'y avait juste pas pensé.
    "On en a vu poser les armes avant de se tirer une balle dans le pied..."
    -- pydévelop

    Derniers articles:

    (SQL Server) Introduction à la gestion des droits
    (UML) Souplesse et modularité grâce aux Design Patterns
    (UML) Le Pattern Etat
    Autres articles...

Discussions similaires

  1. suppression de doublons dans une liste
    Par awalter1 dans le forum Général Python
    Réponses: 4
    Dernier message: 31/07/2012, 16h27
  2. Enlever des doublons dans une liste
    Par frites.saucisse dans le forum Général Python
    Réponses: 8
    Dernier message: 23/06/2010, 22h03
  3. [Toutes versions] Gestion des doublons dans une liste technique.
    Par Lorenzogazier dans le forum Requêtes et SQL.
    Réponses: 7
    Dernier message: 02/04/2009, 23h45
  4. [MySQL] Comment éviter des doublons dans une liste déroulante ?!
    Par L'anonyme_connu dans le forum PHP & Base de données
    Réponses: 3
    Dernier message: 12/03/2008, 12h14
  5. Réponses: 13
    Dernier message: 01/08/2006, 17h59

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo