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

Scheme Discussion :

Supprimer les doublons d'une liste


Sujet :

Scheme

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

    Informations forums :
    Inscription : Mai 2009
    Messages : 2
    Points : 1
    Points
    1
    Par défaut Supprimer les doublons d'une liste
    Bonjour, je dois trouver une fonction qui me permet de supprimer les doublons d'une liste déja triée
    ex : '(1 1 2 3 5 5) = 1 2 3 5

    sur papier j'avais fait ça je pensais que ça marchait mais en l'executant sur dr scheme j'ai vu que c'etait pas bon , est ce que quelqu'un peut me dire ce qui ne va pas ? Merci d'avance et bon aprem
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    (define CreerEnsemble
      (lambda (l)
        (if (null? (cdr l))
            l
            (if (= (car l)(car (CreerEnsemble (cdr l))))
                  (CreerEnsemble (cdr l))
                  (cons (car l)(car(CreerEnsemble (cdr l))))))))

  2. #2
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Salut,

    utilises la balise code pour présenter ton code. C'est pas lisible là.
    Sinon plutôt que le code, commence par présenter ton algorithme. L'erreur est plus souvent là que dans le code. Après, vu que ce que tu demandes est une question de cours, il faut que tu indiques dans quel contexte se pose la question. Car ton prof attends peut-être que tu utilises certains outils.

  3. #3
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2009
    Messages
    2
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2009
    Messages : 2
    Points : 1
    Points
    1
    Par défaut
    il n'y a pas de contexte puisque mon prof fait greve et nous balance des exos alors qu'on a jamais eu de cours !!!! je vous jure j'en ai trop marre, je connais rien de ce langage, j'ai eu aucun cours et je passe des heures a faire des trucs qui ne marchent meme pas, donc la question c'est juste "creer un ensemble qui permet de trier et de supprimer les doublons d'une liste"

    l'idée qaue j'avais eu sur papier c'était de comparer le (car l) et le (car (cdr l))
    par exemple la premiere etape pour une liste de type (1 1 2) c'est de comparer 1 avec 1 , si 1 = 1 alors on a l qui devient (1 2) mais tout ça je ne sais pas comment ca fonctionne en scheme

    désolée si je me suis enervee au debut mais je comme a craquer sérieusement, c'est pas facile de se mettre a ce langage seul ...

  4. #4
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Citation Envoyé par bibi206 Voir le message
    il n'y a pas de contexte puisque mon prof fait greve et nous balance des exos alors qu'on a jamais eu de cours !!!! je vous jure j'en ai trop marre, je connais rien de ce langage, j'ai eu aucun cours et je passe des heures a faire des trucs qui ne marchent meme pas, donc la question c'est juste "creer un ensemble qui permet de trier et de supprimer les doublons d'une liste"
    Ok prends les devants... lis un des livres que tout informaticien devrait lire un jour : SICP
    et inspire toi aussi de celui-ci HTDP.

    Je me demande si les meilleurs cours de programmation ne sont pas écrits pour Scheme… les mauvaises langues diront que c'est parce que c'est un langage de merde et qu'il faut compenser. Mais c'est des mauvaises langues

    Citation Envoyé par bibi206 Voir le message
    l'idée qaue j'avais eu sur papier c'était de comparer le (car l) et le (car (cdr l))
    par exemple la premiere etape pour une liste de type (1 1 2) c'est de comparer 1 avec 1 , si 1 = 1 alors on a l qui devient (1 2) mais tout ça je ne sais pas comment ca fonctionne en scheme

    désolée si je me suis enervee au debut mais je comme a craquer sérieusement, c'est pas facile de se mettre a ce langage seul ...
    Pas plus difficile que de se mettre au C tout seul sans faire de la programmation digne de Toxic Avenger ! Mais toujours est-il que, revenons à ton problème, ta comparaison n'est pas efficace. Ainsi si la liste est (1 2 1) ta comparaison de 1 et 2 te dit que c'est des éléments distincts. Conclusion tu gardes le 1.

    Ton problème est avant tout d'ordre algorithmique et non de l'ordre de la programmation. Il te faut trouver un bon algorithme. Une idée ?

  5. #5
    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
    Citation Envoyé par Garulfo Voir le message
    Pas plus difficile que de se mettre au C tout seul sans faire de la programmation digne de Toxic Avenger ! Mais toujours est-il que, revenons à ton problème, ta comparaison n'est pas efficace. Ainsi si la liste est (1 2 1) ta comparaison de 1 et 2 te dit que c'est des éléments distincts. Conclusion tu gardes le 1.
    Il a dit que sa liste initiale était déjà trié, donc il lui faut bien un équivalent du "uniq" d'Unix, pas un "nub" à la Haskell.

    En Haskell je découperais ça en deux fonctions mutuellement récursives :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    uniq [] = []
    uniq (car : cdr) = car : uniq (dropWhile (\y -> y == car) cdr)
    
    dropWhile predicat [] = []
    dropWhile predicat (car : cdr) = 
      if predicat car then dropWhile predicat cdr else (car : cdr)
    (sachant que (:) est cons en infixe et [] une liste vide, (\y ...) est un lambda, j'ai volontairement pas mal dévié du style Haskell typique pour être un peu plus proche de Scheme)

    En bref dropWhile supprime la tête de liste récursivement tant que le prédicat est vrai sur cette tête de liste.

    Avec ceci et un petit effort tu devrais être capable de trouver un algorithme correct et de transcrire cette solution en Scheme.

    --
    Jedaï

    PS : En vérité, en Haskell typique la solution serait plutôt :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    uniq = map head . group

  6. #6
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Citation Envoyé par Jedai Voir le message
    En Haskell je découperais ça en deux fonctions mutuellement récursives :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    uniq [] = []
    uniq (car : cdr) = car : uniq (dropWhile (\y -> y == car) cdr)
    
    dropWhile predicat [] = []
    dropWhile predicat (car : cdr) = 
      if predicat car then dropWhile predicat cdr else (car : cdr)
    (sachant que ( est cons en infixe et [] une liste vide, (\y ...) est un lambda, j'ai volontairement pas mal dévié du style Haskell typique pour être un peu plus proche de Scheme)

    En bref dropWhile supprime la tête de liste récursivement tant que le prédicat est vrai sur cette tête de liste.

    Avec ceci et un petit effort tu devrais être capable de trouver un algorithme correct et de transcrire cette solution en Scheme.

    --
    Jedaï
    J'ai malheureusement quelques doutes :
    il n'y a pas de contexte puisque mon prof fait greve et nous balance des exos alors qu'on a jamais eu de cours !!!! je vous jure j'en ai trop marre, je connais rien de ce langage, j'ai eu aucun cours et je passe des heures a faire des trucs qui ne marchent meme pas ..........

    désolée si je me suis enervee au debut mais je comme a craquer sérieusement, c'est pas facile de se mettre a ce langage seul ...
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  7. #7
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Il a dit que sa liste initiale était déjà trié, donc il lui faut bien un équivalent du "uniq" d'Unix, pas un "nub" à la Haskell.
    Ah oui ! Au temps pour moi, je me suis égaré.
    Dans ce cas, je reviens sur mes propos et je reprends où tu as laissé ton idée : « l'idée qaue j'avais eu sur papier c'était de comparer le (car l) et le (car (cdr l)) » ! L'idée est bonne. Pourquoi ne pas l'avoir écrit comme ça dans ton test au lieu de celui que tu as mis ?
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    (= (car l)(car (CreerEnsemble (cdr l))))
    Même en étant nul en Scheme, on peut se rendre compte que tu n'as pas comparer (car l) et (car (cdr l)), n'est-ce pas ?

    Donc commences par corriger le test. Ensuite, donne la suite de ton algorithme :
    Si le premier élément est égal au deuxième élément
    alors ????
    sinon ????

    Et tu verras que ce n'est pas difficile de transcrire.

    Citation Envoyé par Trap D Voir le message
    Citation Envoyé par Jedai Voir le message
    Avec ceci et un petit effort tu devrais être capable de trouver un algorithme correct et de transcrire cette solution en Scheme.
    J'ai malheureusement quelques doutes
    Je partage ces doutes. Il me semble que si le cours de Scheme est lacunaire, pour le moins, il ne faut pas trop espérer comprendre Haskell en plus d'un Scheme non compris.

  8. #8
    Membre confirmé Avatar de KindPlayer
    Profil pro
    Inscrit en
    Février 2007
    Messages
    471
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 471
    Points : 477
    Points
    477
    Par défaut Vite fait, pas optimisé..
    avec une fonction auxiliaire memb? qui verifie qu'un element x appartient a une liste

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    (define (memb? x liste)
      (if (null? liste) #f
          (or (eq? (car liste) x) (memb? x (cdr liste)))))
    
    (define (delete-doublons liste)
      (if (null? liste)
        '()
         (let loop ((acc '()) (l liste)) ;; on utilise une liste d'accumulation pour stocker les elements deja rencontres dans l
            (if (null? l) 
                acc
                (if (memb? (car l) acc)
                    (loop acc (cdr l))
                    (loop (cons (car l) acc) (cdr l)))))))
    La science est ce que nous comprenons suffisamment bien pour l'expliquer à un ordinateur. L'art, c'est tout ce que nous faisons d'autre.
    Donald E. Knuth

  9. #9
    Membre confirmé Avatar de KindPlayer
    Profil pro
    Inscrit en
    Février 2007
    Messages
    471
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 471
    Points : 477
    Points
    477
    Par défaut Precision
    cette fonction est valable pour une liste quelconque (triée ou pas)
    La science est ce que nous comprenons suffisamment bien pour l'expliquer à un ordinateur. L'art, c'est tout ce que nous faisons d'autre.
    Donald E. Knuth

  10. #10
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    @KindPlayer...

    formidable, comme ça il n'a pas à réfléchir. C'est sûr que ça va l'aider à apprendre.

    De plus, c'est loin d'être une belle et une bonne solution. Ça fonctionne mais c'est un style très patate : un équivalent à memb? existe; en lisp on n'écrit pas (if (null? liste) #f qqchose) c'est une preuve de méconnaissance; on n'écrit pas non plus des if imbriqués quand on peut utiliser un cond. Ce qui est le cas. Finalement, on préfère les itérateurs si possible (quoique là ça pourrait être mal venu).

  11. #11
    Membre confirmé Avatar de KindPlayer
    Profil pro
    Inscrit en
    Février 2007
    Messages
    471
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 471
    Points : 477
    Points
    477
    Par défaut
    désolé pour mon style patate ca fait un bout de temps que j'ai pas fait de scheme, pour cond je savais plus... Pourquoi on peut pas ecrire (if (null ? liste) #f .. ? On écrit quoi à la place ?
    Enfin ce qui m'interesse surtout au dela de question de style ou de syntaxe, c'est de savoir s'il y a un algorithme qui évite de reparcourir une liste. Ma solution est clairement inefficace quand la liste contient peu de doublons. Une solution serait peut etre de trier d'abord ? As-tu une solution efficace à proposer ?

    L'algo un peu mieux écrit:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    (define (delete-doublons liste)
      (if (null? liste)
        '()
         (let loop ((acc '()) (l liste))
            (cond ( (null? l) acc )
                  ( (memq (car l) acc) (loop acc (cdr l)) )
                  ( (loop (cons (car l) acc) (cdr l)) )
            )
         )
      )
    )
    La science est ce que nous comprenons suffisamment bien pour l'expliquer à un ordinateur. L'art, c'est tout ce que nous faisons d'autre.
    Donald E. Knuth

  12. #12
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Citation Envoyé par KindPlayer Voir le message
    désolé pour mon style patate ca fait un bout de temps que j'ai pas fait de scheme, pour cond je savais plus... Pourquoi on peut pas ecrire (if (null ? liste) #f .. ? On écrit quoi à la place ?
    On peut. L'habitude est d'utiliser un and. L'expression (and e1 e2) évalue e1, retourne #f si e1 s'évalue en #f et retourne l'évaluation de e2 sinon. Étant donné que tout ce qui n'est pas #f est considéré comme #t dans un test, l'habitude est d'utiliser uniquement des and et des or dans ce genre de cas.
    Il faut remarquer cependant que dans ce cas, le if sera légèrement plus rapide. Le and fournie un code plus conforme à ce qu'on aurait dans une spéc.

    Donc
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    (define [est-membre? x liste]
      (and [not (null? liste)]
           [or (eq? (car liste) x) 
               (est-membre? x (cdr liste))]))
    ou on peut utiliser memq qui fait exactement ça. Ceci soulève le problème de l'utilisation de eq? comme prédicat d'égalité. Dans notre cas, j'aurais utilisé eqv? et donc memv? plutôt. Si on utilise que des nombres, c'est le prédicat = qu'il faut utiliser.

    Ainsi pour une liste de dix millions d'élément où le dernier élément est celui recherché, mon ordinateur me donne les temps suivants pour la recherche
    Code : 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
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    > (define (longue-liste taille)
        (let loop [(acc (list 2)) (n (- taille 1))]
          (if [< n 1]
              acc
              (loop (cons 1 acc) (- n 1)))))
            
    > (define L (longue-liste 10000000))
    
    > (length L)
    10000000
    
    > (time (memq 2 L))
    cpu time: 63 real time: 63 gc time: 0
    (2)
    > (time (memv 2 L))
    cpu time: 100 real time: 102 gc time: 0
    (2)
    > (time (member 2 L))
    cpu time: 439 real time: 444 gc time: 0
    (2)
    > (time (memb? 2 L))
    cpu time: 3299 real time: 3332 gc time: 0
    #t
    > (time (est-membre? 2 L))
    cpu time: 3825 real time: 3904 gc time: 0
    #t
    Le temps est en milli-secondes bien sûr. On voit que memq est bien plus performant. La raison est que les listes en Scheme ne sont pas représentées comme des listes en mémoire interne. C'est pourquoi le temps d'accès à un élément précis n'est pas linéaire
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    > (time (list-ref L 1000000))
    cpu time: 0 real time: 0 gc time: 0
    1
    > (time (list-ref L 9000000))
    cpu time: 44 real time: 45 gc time: 0
    1
    Citation Envoyé par KindPlayer Voir le message
    Enfin ce qui m'interesse surtout au dela de question de style ou de syntaxe, c'est de savoir s'il y a un algorithme qui évite de reparcourir une liste. Ma solution est clairement inefficace quand la liste contient peu de doublons. Une solution serait peut etre de trier d'abord ? As-tu une solution efficace à proposer ?
    Exact. C'est là où le bât blesse. Ton algo possède une faiblesse au niveau de la complexité. Mais même plus facilement, tu fais un premier if inutile. Ta boucle loop traite le cas de la liste nulle.

    Comme me l'a fait remarquer Jedai — ce qui démontre que tu n'as pas lu le fil avant de répondre — la liste est déjà triée pour ce problème particulier. L'algorithme de bibi était probablement bon à qqs détails prés.

    Dans le cas général, la meilleure technique en Scheme est d'utiliser un filter. C'est lui qui filtrera les bons éléments à venir à l'aide d'une fonction qui mémorisera (imperative style inside donc) les éléments parcourus. Ou alors, pour se passer d'un filtre utilisant de l'impératif, on le recode mais l'appel récursif modifie le prédicat en y ajoutant l'élément à ne pas filtrer. Vois-tu le principe ? Ceci ne change pas la complexité a priori pourtant. Mais si on utilise une structure performante pour tester l'appartenance, cela peut devenir plus efficace d'utiliser la première approche. La deuxième est la meilleure d'un point de vue paradigme fonctionnel pur.

    Encore une fois, l'idéal est le passage par des opérateurs de Scheme préexistant car ils sont plus performants que ceux que tu vas écrire à la main en général.

    Mon algorithme est le même que le tien, mais j'utilise la première approche dont je te parlais. Les résultats pour la longue liste dont je parlais (c'est-à-dire 9999999 de 1 et un 2 à la fin) donne
    • pour ta fonction : cpu time: 5062 real time: 5102 gc time: 0
    • pour la mienne : cpu time: 2659 real time: 2665 gc time: 0

    avec une liste qui génère 9999999 nombres aléatoires entre 0 et 9 puis qui met un 10 à la fin, on obtient
    • pour ta fonction : cpu time: 19365 real time: 19495 gc time: 0
    • pour la mienne : cpu time: 4500 real time: 4541 gc time: 0

    finalement, pour une liste de 20 000 000 d'éléments tirés aléatoirement entre 0 et 999, j'obtiens
    • pour ta fonction : cpu time: 3164477 real time: 3193840 gc time: 0
    • pour la mienne : cpu time: 401702 real time: 404357 gc time: 0

    52 minutes pour ta fonction, 7 minutes pour la mienne.
    Convaincant, non ?

    Voici ma fonction:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    (define (eliminer-les-doublons liste)
      (define p? (let* [(ensemble '())
                        (appartient? {lambda (x) (member x ensemble)})
                        (ajoute {lambda (x) (set! ensemble (cons x ensemble)) ensemble})]
                   {lambda (element) (and [not (appartient? element)]
                                          (ajoute element))}))
        (filter p? liste))

  13. #13
    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
    Juste pour dire que la deuxième approche (fonctionnelle pure) est parfaitement viable, pour preuve le code suivant :
    Code Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    nubSet xs = go xs empty
        where
          go [] _ = []
          go (x:xs) set
              | x `member` set = go xs set
              | otherwise      = x : go xs (insert x set)
    qui est parfaitement pur et utilise un arbre binaire équilibré (persistant et fonctionnel) met moins de 5s pour traiter la liste de 20 000 000 d'éléments aléatoires entre 0 et 999.

    Citation Envoyé par Garulfo
    Le temps est en milli-secondes bien sûr. On voit que memq est bien plus performant. La raison est que les listes en Scheme ne sont pas représentées comme des listes en mémoire interne. C'est pourquoi le temps d'accès à un élément précis n'est pas linéaire
    Tu as déjà affirmé ceci à d'autres occasion et il me semble qu'à l'époque une exploration d'une implémentation de Scheme avait démontré qu'au moins celle-ci utilisait effectivement des listes chaînées pour représenter ses listes. Ton argument de vitesse n'est pas non plus très convaincant : le elem de Haskell a des performances extrêmement similaires à ton memq (testé) sur des listes d'entiers alors même que les listes en Haskell sont vraiment des listes chaînées simples et les entiers sont boxés.
    Ce qui ne veut pas dire que ton affirmation soit toujours fausse, on peut effectivement imaginer que les listes soient quelque peu enrichies en sous-main pour mieux supporter certaines opérations courantes, simplement les performances que tu nous montres ne sont pas un argument suffisant pour en être certain.

    --
    Jedaï

  14. #14
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Juste pour dire que la deuxième approche (fonctionnelle pure) est parfaitement viable[...]met moins de 5s pour traiter la liste de 20 000 000 d'éléments aléatoires entre 0 et 999.
    Tu compares Haskell à Scheme. Le premier est nettement plus performant, d'autant que les temps, que je donnais, étaient issus de l'interpréteur. En Haskell, je n'aurais pas eu le même discours,.

    Citation Envoyé par Jedai Voir le message
    Tu as déjà affirmé ceci à d'autres occasion et il me semble qu'à l'époque une exploration d'une implémentation de Scheme avait démontré qu'au moins celle-ci utilisait effectivement des listes chaînées pour représenter ses listes. Ton argument de vitesse n'est pas non plus très convaincant : le elem de Haskell a des performances extrêmement similaires à ton memq (testé) sur des listes d'entiers alors même que les listes en Haskell sont vraiment des listes chaînées simples et les entiers sont boxés.
    Ce qui ne veut pas dire que ton affirmation soit toujours fausse, on peut effectivement imaginer que les listes soient quelque peu enrichies en sous-main pour mieux supporter certaines opérations courantes, simplement les performances que tu nous montres ne sont pas un argument suffisant pour en être certain.

    --
    Jedaï
    Je ne vois pas où tu veux en venir. Si on fait comme à fait KindPlayer en implémentant soi même la méthode de recherche, on perd du temps. C'est tout ce que je montrais avec les temps d'exécution. Il faut utiliser les itérateurs et les opérateurs fournis par le langage. Je ne partais pas dans d'autres considérations notamment sur d'autres langages que Scheme.

    Les performances que je montre devrait convaincre qu'il faut utiliser memq au lieu d'une fonction créée pour l'occasion, non ? En quoi n'est-ce pas convaincant ? Dans cet ordre d'idée l'algorithme purement fonctionnelle pourrait même être efficace en Scheme si on utilise cons, memq et les autres opérateurs de liste, car les listes ne sont pas « juste des listes ». D'ailleurs dans ton algorithme tu n'utilises pas des listes simples, mais un arbre binaire équilibré. Ça va dans ce sens. Il n'y a pas d'arbre binaire équilibré par défaut en Scheme; enfin, pas que je connaisse.

    Je n'ai pas essayé de montrer que l'approche non pur était meilleure que l'approche pure car le combat était injuste puisque Kindplayer utilisait sa propre fonction d'appartenance. Peut-être aurais-je dû le préciser.

    Donc je ne comprends pas vraiment ce que tu essais de dire ?
    Voici mes conclusions :
    • en Scheme, il faut utiliser les opérateurs et les itérateurs fournis car ils sont plus performants que ceux fait à la main — ça pourrait être étendu dans d'autre langage mais pas toujours pour les raisons de performance;
    • d'un point de vue purement algorithmique, en utilisant une approche purement fonctionnel, il faudrait utiliser autre chose qu'une liste chainée pour mémoriser les valeurs parcourues.

    N'es-tu pas d'accord ?

    C'est vrai que j'aurais pû préciser partout « en Scheme » mais étant dans le forum Scheme et répondant à une question de TP pour Scheme, ça me semblait un peu redondant

    Citation Envoyé par Jedai Voir le message
    il me semble qu'à l'époque une exploration d'une implémentation de Scheme avait démontré qu'au moins celle-ci utilisait effectivement des listes chaînées pour représenter ses listes.
    Une implémentation de Scheme peut-être… mais en MzScheme, j'en doute. Or je suppose que la majorité des personnes ici utilise MzScheme. Serais-je dans l'erreur depuis tout ce temps ?

  15. #15
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Voilà des chiffres pour la version fonctionnelle pure :
    cpu time: 383227 real time: 392362 gc time: 2204
    et celle avec un set!
    cpu time: 405750 real time: 419674 gc time: 105

    C'est du même ordre. C'est exactement l'algo de KindPlayer mais juste avec member au lieu de memb?. Et ça change tout donc.

    Jedai: J'ai l'impression que ce qui te dérangeait c'était que je sous-entendais qu'il valait mieux une version impérative. Est-ce ça ? Ce n'était pas du tout ce que je voulais dire.

  16. #16
    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
    Citation Envoyé par Garulfo Voir le message
    Je ne vois pas où tu veux en venir. Si on fait comme à fait KindPlayer en implémentant soi même la méthode de recherche, on perd du temps. C'est tout ce que je montrais avec les temps d'exécution. Il faut utiliser les itérateurs et les opérateurs fournis par le langage. Je ne partais pas dans d'autres considérations notamment sur d'autres langages que Scheme.
    Tout à fait d'accord dans ce cas. (notons que dans d'autres langages la différence n'est pas aussi flagrante, par exemple en Haskell, pratiquement toute la librairie de base est écrite en Haskell, évidemment la nature compilée du langage y fait beaucoup)

    Citation Envoyé par Garulfo Voir le message
    Les performances que je montre devrait convaincre qu'il faut utiliser memq au lieu d'une fonction créée pour l'occasion, non ? En quoi n'est-ce pas convaincant ? Dans cet ordre d'idée l'algorithme purement fonctionnelle pourrait même être efficace en Scheme si on utilise cons, memq et les autres opérateurs de liste, car les listes ne sont pas « juste des listes ».
    C'est en effet convaincant, à part sur le fait que les listes ne soient pas "juste des listes".

    Citation Envoyé par Garulfo Voir le message
    Je n'ai pas essayé de montrer que l'approche non pur était meilleure que l'approche pure car le combat était injuste puisque Kindplayer utilisait sa propre fonction d'appartenance. Peut-être aurais-je dû le préciser.
    Je trouvais ton message effectivement un peu ambigu sur ce point, ce qui est la principale raison pour laquelle j'ai ajouté une solution pure et précisé que ses performances étaient parfaitement acceptables.

    Citation Envoyé par Garulfo Voir le message
    Donc je ne comprends pas vraiment ce que tu essais de dire ?
    Voici mes conclusions :
    • en Scheme, il faut utiliser les opérateurs et les itérateurs fournis car ils sont plus performants que ceux fait à la main — ça pourrait être étendu dans d'autre langage mais pas toujours pour les raisons de performance;
    • d'un point de vue purement algorithmique, en utilisant une approche purement fonctionnel, il faudrait utiliser autre chose qu'une liste chainée pour mémoriser les valeurs parcourues.

    N'es-tu pas d'accord ?
    J'approuve totalement, mon point était surtout sur le fait qu'il ne fallait pas prendre tes résultats comme une indication que la solution purement fonctionnelle était inefficiente.


    Citation Envoyé par Garulfo Voir le message
    Une implémentation de Scheme peut-être… mais en MzScheme, j'en doute. Or je suppose que la majorité des personnes ici utilise MzScheme. Serais-je dans l'erreur depuis tout ce temps ?
    Code C : 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
    17
    typedef struct Scheme_Simple_Object
    {
      Scheme_Inclhash_Object iso;
     
      union
        {
          struct { mzchar *string_val; int tag_val; } char_str_val;
          struct { char *string_val; int tag_val; } byte_str_val;
          struct { void *ptr1, *ptr2; } two_ptr_val;
          struct { int int1; int int2; } two_int_val;
          struct { void *ptr; int pint; } ptr_int_val;
          struct { void *ptr; long pint; } ptr_long_val;
          struct { struct Scheme_Object *car, *cdr; } pair_val; // <--- this line
          struct { mzshort len; mzshort *vec; } svector_val;
          struct { void *val; Scheme_Object *type; } cptr_val;
        } u;
    } Scheme_Simple_Object;
    Ca ressemble diablement à une liste chaînée pourtant...

    J'ai aussi examiné une portion du code de traitement, c'est une liste chaînée et voilà tout, et memq :
    Code C : 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
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    #define GEN_MEM(name, scheme_name, comp) \
    static Scheme_Object * \
    name (int argc, Scheme_Object *argv[]) \
    { \
      Scheme_Object *list, *turtle; \
      list = turtle = argv[1]; \
      while (SCHEME_PAIRP(list)) \
        { \
          if (comp (argv[0], SCHEME_CAR (list))) \
    	{ \
              return list; \
    	} \
          list = SCHEME_CDR (list); \
          if (SCHEME_PAIRP(list)) { \
            if (comp (argv[0], SCHEME_CAR (list))) \
    	  { \
                return list; \
    	  } \
            if (SAME_OBJ(list, turtle)) break; \
            list = SCHEME_CDR (list); \
            turtle = SCHEME_CDR (turtle); \
            SCHEME_USE_FUEL(1); \
          } \
        } \
      if (!SCHEME_NULLP(list)) { \
        scheme_raise_exn(MZEXN_FAIL_CONTRACT, \
    		     "%s: not a proper list: %V", #scheme_name, \
    		     argv[1]); \
      } \
      return (scheme_false); \
    }
     
    GEN_MEM(memv, memv, scheme_eqv)
    GEN_MEM(memq, memq, SAME_OBJ)
    GEN_MEM(member, member, scheme_equal)
    Une recherche d'élément parfaitement classique, en O(n).

    Globalement, j'ai l'impression que tu sous-estime les listes chaînées : c'est une structure de donnée efficace pour la plupart des besoins des listes en Scheme et elle a l'avantage d'être simple à maintenir et manipuler. On pourrait imaginer rajouter un peu de magie pour accélérer les accès aléatoires mais d'un autre côté, quelqu'un qui utilise les listes pour cela en Scheme est mal parti de toute façon.

    --
    Jedaï

  17. #17
    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
    Citation Envoyé par Garulfo Voir le message
    Jedai: J'ai l'impression que ce qui te dérangeait c'était que je sous-entendais qu'il valait mieux une version impérative. Est-ce ça ? Ce n'était pas du tout ce que je voulais dire.
    En fait tu ne le sous-entendais pas et je ne l'ai pas perçu comme ça, c'est juste que ton message pouvait être mésinterprété ainsi facilement.

    --
    Jedaï

  18. #18
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Citation Envoyé par Jedai Voir le message
    En fait tu ne le sous-entendais pas et je ne l'ai pas perçu comme ça, c'est juste que ton message pouvait être mésinterprété ainsi facilement.
    --
    Jedaï
    Ok. À la relecture, tu as effectivement raison. Merci de la précision

  19. #19
    Membre confirmé Avatar de KindPlayer
    Profil pro
    Inscrit en
    Février 2007
    Messages
    471
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 471
    Points : 477
    Points
    477
    Par défaut
    Merci pour vos explications. En effet dans ma fonction le premier test est inutile. J'avais corrigé entretemps mon code en remplacant l'appel à ma fonction memb? par memq. Je sais qu'il faut de préférence utiliser les fonctions prédéfinies. Mais il fallait que je me replonge dans le R5RS (ce que j'ai fini par faire d'ailleurs!)
    La science est ce que nous comprenons suffisamment bien pour l'expliquer à un ordinateur. L'art, c'est tout ce que nous faisons d'autre.
    Donald E. Knuth

  20. #20
    Inactif  
    Profil pro
    Inscrit en
    Juillet 2005
    Messages
    1 958
    Détails du profil
    Informations personnelles :
    Âge : 58
    Localisation : France

    Informations forums :
    Inscription : Juillet 2005
    Messages : 1 958
    Points : 2 467
    Points
    2 467
    Par défaut
    Citation Envoyé par KindPlayer Voir le message
    [...]Mais il fallait que je me replonge dans le R5RS (ce que j'ai fini par faire d'ailleurs!)
    Attention, on est passé au R6RS. Personnellement, j'en suis content. Certaines formes de let sont plus agréables à utiliser; les modules sont plus systématiques; il y a une distinction entre liste mutable et liste non mutable; un système de typage — très souple cependant rien à voir avec ocaml — fait son entrée; il y a un mode paresseux — que je n'ai pas vraiment testé par contre; les extensions syntaxiques sont mieux faites… un vrai changement quoi.

Discussions similaires

  1. Réponses: 16
    Dernier message: 03/06/2014, 08h39
  2. Supprimer les doublons d'une liste déroulante
    Par zanzie dans le forum Flash
    Réponses: 1
    Dernier message: 11/04/2011, 09h34
  3. Supprimer les doublons dans une liste
    Par inforum dans le forum SL & STL
    Réponses: 2
    Dernier message: 22/11/2009, 16h21
  4. [E-03] Supprimer les doublons d'une liste
    Par Loki83 dans le forum Macros et VBA Excel
    Réponses: 5
    Dernier message: 05/12/2008, 17h34
  5. Réponses: 10
    Dernier message: 19/09/2006, 04h15

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