Discussion :

[InOCamlWeTrust]

Les points "d'optimisation" que tu veux aborder ne sont même pas de l'ordre du détail : inverser l'ordre des cas dans le filtrage, ça fait peut-être gagner 1 ms sur une exécution d'une heure et qui ne fait que ça (et encore...), et définir les fonctions sous forme abstraite ou curryfiée est une pratique que seuls les créateurs du langage peuvent conseiller dans certains cas très obscurs, mais eux seuls sont à même de savoir pourquoi.

Par contre, comme dit plus haut, le plus important dans un code est la consistance : nommer les mêmes choses de la même façon, dans le même ordre, etc... Tu gagnes en lisibilité, et ça oui, ça fait gagner du temps ! pas les petites optimisations...

OCaml est un langage dont on tire toute sa puissance, en termes de performances, quand on code de façon LISIBLE et NATURELLE, et pas forcément concise comme en Haskell.

Crois-moi : code simplement, de façon lisible, et tu auras les programmes les plus rapides. Si ça avait été un autre langage, ça aurait été différent.

[gasche]

Un conseil : arrête de jouer les über-optimiseurs de la mort, et essaie d'écrire du code clair.

Il y a plusieurs niveaux de performance à prendre en compte quand on mesure la rapidité d'un programme. Le premier, et probablement le plus important dans probablement tous les cas, est celui de la complexité algorithmique. Prendre un peu soin de la complexité algorithmique peut permettre des gains énormes : passer de O(n²) à O(n) apporte une augmentation de performance significative dès que les données que tu manipules sont un peu grosses.

Il existe des optimisations plus "bas niveau" puisqu'elles jouent non pas sur la complexité, mais la représentation du programme par le compilateur. La récursion terminale en est sans doute l'exemple le plus courant.

Mon conseil, c'est de rester pour l'instant aux optimisations "haut niveau" : apprend la complexité des opérateurs que tu utilises (cons est O(1), @ est O(taille du premier argument), ^ est O(taille de la somme des deux chaines), et ça aurait du suffire à répondre à ta question dès le départ), et arrête de t'occuper du reste.

La tail-récursion, c'est bien gentil, mais pourquoi coder dès le début une version tail-récursive moins claire, alors que tu n'as aucune idée de si cela va te servir ?
(Par ailleurs, pour les algorithmes naturellement non tail-récursifs comme filter, la version non-tail-rec est souvent plus rapide pour des listes de taille petite voire moyenne)
Bien sûr, il existe des algorithmes "naturellement" tail-récursifs, comme rev ou fold_left. Pour ceux là, il est évident que la formulation tail-récursive est la meilleure. Mais en règle général, tu ferais mieux de passer moins de temps à fantasmer sur le code natif généré, et coder une version claire, simple et non tail-récursive au départ.
Si par la suite tu identifies un problème de performance dans cette partie précise du code, tu pourras très facilement savoir si la non-tail-récursion pose problème (un simple coup de profiler suffit). Mais en attendant, pourquoi écrire une version alambiquée de ton code, alors qu'à priori ça ne sert à rien ? Contente toi d'avoir un complexité crédible, et d'avoir un code le plus clair possible.
Il y a même des cas où la complexité du code passe après sa simplicité. Par exemple, si tu veux indexer une structure par des clés de type quelconque, et que tu sais que cette structure compte très peu d'éléments ou ne sera utilisée qu'une fois dans ton programme, il est totalement inutile d'aller chercher des arbres équilibrés ou des tables de hachage, alors qu'une simple liste associative fait l'affaire.

Je ne parle pas de tes idées d'optimisation de la fin (lambda anonymes ou fonctions déclarées ? Ordre des motifs dans le filtrage ?), qui sont tout simplement ridicules. On ne mange plus de viande de mammouth crue, et on s'autorise à nommer des variables inutiles dans un filtrage, si on trouve ça plus clair.


Edit : grillé par InOCamlWeTrust !
Par ailleurs, le compilateur optimise évidemment les filtrages, et l'ordre des motifs sans gardes n'a donc aucune importance sur le temps d'exécution (qui est, il me semble, en O(1) quelle que soit la taille du motif, s'il est bien disjonctif).

[corrector]

Il y a un truc qui me fait rigoler, dans la librairie pervasives.ml, c'est que dans les pattern matching , ils définissent des variables qui ne sont pas réutilisées (au lieu de _ ) , et ils mettent les exceptions en premier ...

Par exemple, pour la fonction List.hd :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let hd = function
    [] -> failwith "hd"
  | a::l -> a

Je croit que je vait plutôt utiliser

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let hd = function
    a::_ -> a
  | [] -> failwith "hd"

Comme ça la condition d'erreur est pas évaluée systématiquement et on économise la définition d'une variable.

Même en C++, où ne peut vraiment pas dire que la pratique des micro-optimisations (plus ou moins bidons) soit inexistante, je n'ai jamais vu un programmeur évoquer l'idée de ne pas nommer un paramètre pour gagner en temps d'exécution.

Concernant l'ordre, sans aller regarder dans le code du compilateur (ce que je n'ai pas l'intention de faire), je suis absolument certain que tout match non dégénéré sur une liste va être compilé comme un (et un seul) if then else :

if list.tag = Nil then ... else ...

[InOCamlWeTrust]

Concernant l'ordre, sans aller regarder dans le code du compilateur (ce que je n'ai pas l'intention de faire), je suis absolument certain que tout match non dégénéré sur une liste va être compilé comme un (et un seul) if then else :

if list.tag = Nil then ... else ...

Je ne suis pas allé voir précisémentce que le compilateur crache pour ce genre de code, mais je n'en mettrais surtout pas ma main à couper !

[Jedai]

Au final un pattern-matching est compilé vers des tables de saut, des branchements, etc... L'ordre des patterns est pas mal remanié entre temps, et ne correspond pas directement à l'ordre initial. Vous pouvez consultez "Optimizing Pattern Matching" (ICFP 2001) pour tous les détails de la procédure actuelle.

Par exemple, cette fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let g = function
  | [] -> 1
  | x::xs -> x

comme celle ci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let g = function
  | x::xs -> x
  | [] -> 1

sont toutes deux compilées vers le même code assembleur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
.L101:
        cmpl    $1, %eax
        je      .L100
        movl    (%eax), %eax
        ret
.L100:
        movl    $3, %eax
        ret

(3 "=" 1, parce que les variables de OCaml sont taguées)

--
Jedaï

[corrector]

Je ne suis pas allé voir précisément ce que le compilateur crache pour ce genre de code, mais je n'en mettrais surtout pas ma main à couper !

Indépendamment de ta main, tu vois une autre possibilité?