[Ocaml] Eliminer les doublons dans une ('a * 'b)list [Résolu]

Envoyé par gorgonite

pas cool... pourtant l'optimisation existe belle et bien, j'avais pensé qu'elle serait déjà dans ocaml

J'avoue ne pas bien voir comment tu veux optimiser ça, sachant que tu as besoin d'attendre la valeur de retour pour construire ta structure. Tu aurais un lien expliquant de quoi tu parles ?

[pcaboche]

Envoyé par Dark3

Je trouve que tu n'as pas beaucoup de tolérance envers moi, mais je te remercie quand même.
Je ne te demandais pas la solution mais juste un peu d'aide comme ce forum nous le propose quand on a un souci.

Je me range du coté de gorgonite: le problème du Caml, c'est qu'on ne peut pas donner "un peu" d'aide.

Si on apporte "un peu" d'aide, c'est qu'on a résolu le problème et donc ça n'a plus d'intérêt. Ce qu'il est important de comprendre, ce sont les principes de la programmation fonctionnelle (ce que gorgonite a essayé de faire). Le problème, c'est que quand on essaye d'inculquer ces principes, les gens se sentent agressés, ont l'impression qu'on se moque d'eux, ce qui est faux (en réalité, on essaye juste de savoir s'ils ont compris et non s'ils ont l'impression d'avoir compris, ce qui est totalement différent).

Envoyé par alex_pi

J'avoue ne pas bien voir comment tu veux optimiser ça, sachant que tu as besoin d'attendre la valeur de retour pour construire ta structure. Tu aurais un lien expliquant de quoi tu parles ?

Ce que gorgonite a voulu dire (je pense), c'est que le compilateur est théoriquement en mesure d'optimiser ce genre de fonction (il existe un algo pour ce cas là), mais que l'optimisation n'a pas été implémentée en Caml (peut-être dans d'autres langages fonctionnels).

Envoyé par pcaboche

Ce que gorgonite a voulu dire (je pense), c'est que le compilateur est théoriquement en mesure d'optimiser ce genre de fonction (il existe un algo pour ce cas là), mais que l'optimisation n'a pas été implémentée en Caml (peut-être dans d'autres langages fonctionnels).

Je pense aussi, et justement, j'aimerais savoir de quel algo il parle, parce que comme ça, je ne vois pas dutout ce que l'on peut optimiser dans ce cas, et que ça m'intéresse donc !

[InOCamlWeTrust]

Pour information, ocamlopt n'optimise presque rien. Les seules "optimisations" faites concernent la récursivité terminale ainsi que l'ordonnancement des calculs entiers et flottants dans certains cas très précis, pour éviter à avoir à allouer sur le tas via le GC et optimiser le temps de calcul en exploitant les possibilités des processeurs et en réordonnant les instructions machines (mais seulement sur certains processeurs, pas sur les x86...). Il y a un document sur internet écrit par Xavier Leroy, mais je ne me souviens plus du lien... et sinon, il y a les sources !

Une autre optimisation désirable concernerait la chasse aux valeurs dans les fonctions pouvant être allouées de façon sûre sur la pile, comme en C, et non sur le tas.

[gorgonite]

pour l'algo je pensais à un truc du style

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let rec fact n = 
match n with
   0 -> 1
   |_ -> n * fact (n-1)
;;

let fact2 n =
   let rec aux a b =
       match a with
          0 -> b
          |_ -> aux (a-1) (a*b)
   in
fact n 1
;;

le but de cette méthode est de réussir à construire aux "automatiquement", ce qui est simple pour les cas d'appels "récursifs simples" avec des types de données connues (liste, entier) car on sait quoi faire dans l'accumulateur

[gorgonite]

pour l'algo je pensais à un truc du style

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let rec fact n = 
match n with
   0 -> 1
   |_ -> n * fact (n-1)
;;

let fact2 n =
   let rec aux a b =
       match a with
          0 -> b
          |_ -> aux (a-1) (a*b)
   in
aux n 1
;;

le but de cette méthode est de réussir à construire aux "automatiquement", ce qui est simple pour les cas d'appels "récursifs simples" avec des types de données connues (liste, entier) car on sait quoi faire dans l'accumulateur

[InOCamlWeTrust]

Ca va pour des types scalaires pour lesquels les opérations sont commutatives, mais qu'en est-il pour des manipulations sur des listes, quand l'ordre des éléments doit être conservé ?

Quand je faisais de la géométrie algorithmique en OCaml, je devais manipuler de très grands jeux de données, des listes énormes pour lesquelles toute fonction récursive non terminale échouait lamentablement en Stack Overflow. Heureusement, l'ordre des éléments dans les listes que je manipulais n'avait pas vraiment d'importance, et donc je pouvais utiliser ce genre de méthodes ; je concaténais aussi en utilisant List.rev_append, extrêmement utile. Aujourd'hui, je travaille dans le domaine des maillages en C, donc le problème ne se pose plus.

Tout ça pour dire que je ne suis pas certain qu'il existe un algorithme pouvant transformer ce genre de problèmes de façon générale... mais je ne suis pas un expert en compilation non plus.

Envoyé par gorgonite

... ce qui est simple pour les cas d'appels "récursifs simples" avec des types de données connues (liste, entier) car on sait quoi faire dans l'accumulateur

Oui, on est d'accord.

[gorgonite]

Envoyé par InOCamlWeTrust

Tout ça pour dire que je ne suis pas certain qu'il existe un algorithme pouvant transformer ce genre de problèmes de façon générale... mais je ne suis pas un expert en compilation non plus.

ça doit exister... mais l'algo serait NP-difficile

je parlais de la transformation d'une fonction primitive ne faisant qu'un appel récursif, et utilisant des types simples


pour ce qui est des listes, l'accumulateur est effectivement une solution qui inverse le résultat... il faut alors inverser en temps linéaire à la fin, si besoin il y a

Envoyé par InOCamlWeTrust

Pour information, ocamlopt n'optimise presque rien.

Euh... Je me permets d'émettre un doute :-) Parce qu'un compilo qui n'optimise "presque rien" et qui arrive à des performance aussi proche du C en partant d'un langage fonctionnel, c'est de la magie noir :-) J'espère que Xavier Leroy ne va pas lire ton post, il risque de se faire une petite crise cardiaque ! Après, c'est vrai que le compilo n'a pas beaucoup évolué depuis 4 ans, donc il n'est sans doute pas à la pointe de la pointe en matière d'optimisation de derière les fagots, mais tout de même !

Envoyé par InOCamlWeTrust

Tout ça pour dire que je ne suis pas certain qu'il existe un algorithme pouvant transformer ce genre de problèmes de façon générale... mais je ne suis pas un expert en compilation non plus.

Recherche faite, ça s'appelle "récursion terminale modulo cons". Il y a eu un papier là dessus dans POPL (Principle of programming language) en 98, mais je n'ai pas encore eu le temps de jeter un oeil. Il semble que ça ait été discuté plusieurs fois sur la mailing list Caml, mais a priori sans jamais mener à quelque chose de concret. Si j'ai bien compris, le principe est de faire passer à la fonction appelée l'endroit où elle doit mettre son résultat ainsi que la valeur de retour. En gros dans le cas d'une liste, le premier appel connait la valeur de retour (le premier élément de la liste) et fait passer à l'appel suivant sa propre adresse, pour qu'il puisse modifier la référence, et ainsi de suite. Ca a l'air amusant :-) Et C'est émulable via la module Obj (beurk) de Caml

Vali valou !

[gorgonite]

Envoyé par alex_pi

Recherche faite, ça s'appelle "récursion terminale modulo cons". Il y a eu un papier là dessus dans POPL (Principle of programming language) en 98, mais je n'ai pas encore eu le temps de jeter un oeil.

ça doit être là que je l'ai lu effectivement... où quelqu'un a parlé de ce papier pendant un de mes cours

Envoyé par alex_pi

Parce qu'un compilo qui n'optimise "presque rien" et qui arrive à des performance aussi proche du C en partant d'un langage fonctionnel, c'est de la magie noir :-)

il est clair qu'ocamlopt optimise plus que ghc par défaut...
mais il est vrai aussi que -ccopt est parfois bien utile

[InOCamlWeTrust]

Envoyé par alex_pi

Euh... Je me permets d'émettre un doute :-) Parce qu'un compilo qui n'optimise "presque rien" et qui arrive à des performance aussi proche du C en partant d'un langage fonctionnel, c'est de la magie noir :-) J'espère que Xavier Leroy ne va pas lire ton post, il risque de se faire une petite crise cardiaque ! Après, c'est vrai que le compilo n'a pas beaucoup évolué depuis 4 ans, donc il n'est sans doute pas à la pointe de la pointe en matière d'optimisation de derière les fagots, mais tout de même !

C'est Xavier Leroy lui-même qui le dit.

http://caml.inria.fr/pub/old_caml_si...numerical.html

Envoyé par Document

Author: Xavier Leroy

Si OCaml est si performant, c'est entre autres grâce à son Garbage Collector, plus efficace en moyenne que de lamentables appels à malloc(), et ses routines internes sur-optimisées.

Par contre, -ccopt n'a aucun sens si tu ne compiles pas des fichiers .c avec ocamlopt (avec GHC, je ne sais pas) : aucun code C n'est engendré par ocamlopt.

[gorgonite]

Envoyé par InOCamlWeTrust

Par contre, -ccopt n'a aucun sens si tu ne compiles pas des fichiers .c avec ocamlopt (avec GHC, je ne sais pas) : aucun code C n'est engendré par ocamlopt

d'expérience, je peux affirmer que c'est faux... pas plus tard que cette semaine, j'ai compilé avec ocamlopt -ccopt -02, et sur une moyenne pour 1000 exécutions, j'ai gagné 1s (l'exécution durant en tout 10s) sur le temps de calcul par rapport à ocamlopt tout court. et pourtant je ne passais pas par du code c...

[InOCamlWeTrust]

ocamlopt ne crache pas du code C : pour m'être plongé dans les sources du compilateur (version 3.09.3) je peux l'affirmer ; tu as de plus le manuel qui l'explique très bien. Les temps d'exécution dépendent de plus de beaucoup de choses, et surtout du système ; si tu as des accès à des périphériques, tu ne peux déjà plus rien comparer, à cause du cache essentiellement (la première exécution peut être très lente mais la deuxième très rapide), et si ça swap, idem.

Si tu ne me crois pas, demande directement à la Caml Team, à moins qu'entre temps ils aient changé, mais ça m'étonnerait... ou qu'il y ait une subtilité dans le code, un passage qui m'ait échappé.

[gorgonite]

Envoyé par InOCamlWeTrust

Les temps d'exécution dépendent de plus de beaucoup de choses, et surtout du système ; si tu as des accès à des périphériques, tu ne peux déjà plus rien comparer, à cause du cache essentiellement (la première exécution peut être très lente mais la deuxième très rapide), et si ça swap, idem.

merci, mais je sais relativement bien comment calculer un temps d'exécution réaliste pour un programme donné...


mon programme ne travaillait qu'en mémoire, sans aucun accès à un périphérique, et les données tenaient également en mémoire (100mo de données et 2Go de Ram sous un linux en ligne de commande en éteignant la plupart des démons non indispensables)... pour ce qui est de la mise en cache, sur une moyenne de 1000 exécutions consécutives, le phénomène a quand même du avoir lieu pour les deux programmes, donc cela ne compte pas vraiment

[InOCamlWeTrust]

C'était exactement le même code, la même commande d'exécution, les mêmes commandes de compilation ?

Si je revois les mecs de Caml je leur poserai la question, mais ça m'a l'air très louche ton truc.

[gorgonite]

Envoyé par InOCamlWeTrust

C'était exactement le même code, la même commande, les mêmes commandes de compilation ?

ben oui, tout pareil... mais ne te prends pas la tête pour cela, je demanderais moi-même quand je les verrais

[InOCamlWeTrust]

Je viens de poser la question ce matin dans le car à un mec du projet Gallium.

La seule explication plausible selon lui serait que l'option -O2 ait été passée en argument à l'assembleur et au linker, qui se seraient chargé d'effectuer de petites optimisations (certains assembleurs sont capables d'optimiser un peu le code).

Selon la personne, sur la mailing list de Caml des personnes auraient déjà constaté ce phénomène.

Sinon, si tu veux voir si le code engendré avec -ccopt -O2 est le même que celui engendré sans, tu peux prendre deux fichiers .ml, compiler avec -S, récupérer les deux codes assembleur et faire un diff dessus.

[gorgonite]

Envoyé par InOCamlWeTrust

Sinon, si tu veux voir si le code engendré avec -ccopt -O2 est le même que celui engendré sans, tu peux prendre deux fichiers .ml, compiler avec -S, récupérer les deux codes assembleur et faire un diff dessus.

pas trop, nan... le code asm généré par un compilateur est moche, à la limite de l'illisible, j'ai déjà donné durant mon stage

[InOCamlWeTrust]

Ouais mais diff il s'en fout, lui, que le code assembleur soit moche !

Sérieusement : il faudrait faire un diff sur le code assembleur, puis sur les fichiers binaires pour voir si ils sont égaux au non.

Si les codes assembleur sont les mêmes mais que les fichiers objets ou exécutables sont différents, alors c'est que l'assembleur et/ou le linker ont pris en compte l'option -O2.

On m'a aussi un peu parlé des orientations futures concernant Caml et autres.

[jurik42]

Ton algorithme est assez lent, puisqu'il s'exécute en O(n²).

Voici un algorithme linéaire :

Code :

1
2
3
4
5
6
7
8
9
10
let _HASH_TABLE_SIZE = 997 (* taille de la table de hachage *)
let delete_doublons l =
  let h = Hashtbl.create _HASH_TABLE_SIZE in
  let rec delete_rec = function
    | (a, _) :: l when Hashtbl.mem h a -> delete_rec l (* si a est déjà marqué, on le supprime *)
    | (a, _) as e :: l ->
      Hashtbl.add h a ();                              (* sinon on le marque *)
      e :: delete_rec l
    | [] -> []
  in delete_rec l