Discussion :

[Invité]

Bonjour à tous
Je me souvient vaguement avoir lu quelque part (sur ce forum ou dans un livre je sais plus ...) que la concaténation des listes en OCaml est beaucoup plus lourde qu'une autre méthode pour faire des choses équivalentes ...

C'est un peu confus mais en gros je cherche de la documentation sur comment est traduit le @ par le compilo.

Ce qui m'a conduit à cette reflexion, c'est que j'ai besoin d'ajouter un élément en fin de liste, et non pas en début de liste, ce que nous fait en un cycle d'horloge (ou pas) un petit cons :

Code :

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

1
2
1 :: [2;3] ;;
- : int list = [1;2;3]

Et je me suis dit que c'était dommage d'utiliser une concaténation pour ajouter un élément en fin de liste (qu'on auras d'abord mis dans une liste à un élément) si elle est beaucoup plus lourde qu'un cons ...

Exemple :

Code :

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

1
2
[2;3] @ [4] ;;
- : int list = [2;3;4]

Vous, vous faites comment ?

[Garulfo]

La concaténation impose que tu te rendes en fin de liste.
À chaque fois tu vas reparcourir ta liste.

Dans ton cas, travailles avec une liste à l'envers autant que possible.

[Steki-kun]

C'est même pire que ça je crois. Sauf erreur, à cause de la persistance, ajouter en fin de liste implique (en général) de recopier tout le reste de la liste, et pas seulement le traverser, non ?
Dans un cas trivial comme [2; 3]@[4], où la liste [2; 3] va être jetée tout de suite derrière, peut-être le compilo fait un truc sioux mais dans un exemple réel, ça doit aggraver l'effet d'un tail-consing.

[LLB]

C'est un peu confus mais en gros je cherche de la documentation sur comment est traduit le @ par le compilo.

@ est un simple opérateur dont le code se trouve dans pervasives.ml.

Ce qui m'a conduit à cette reflexion, c'est que j'ai besoin d'ajouter un élément en fin de liste, et non pas en début de liste, ce que nous fait en un cycle d'horloge (ou pas) un petit cons :

Si ta fonction n'est pas appelée souvent ou si tu as moins de 1000 éléments, il y a des chances que tu ne remarques pas la différence.

Sauf erreur, à cause de la persistance, ajouter en fin de liste implique (en général) de recopier tout le reste de la liste, et pas seulement le traverser, non ?

En effet... Sans copie, ajouter en fin génèrerait un effet de bord sur la liste.

Vous, vous faites comment ?

Très souvent, on s'en passe bien. Parfois, tu peux appeler List.rev. Ou alors, il faut utiliser un autre type que la liste.

As-tu un exemple concret à nous soumettre ?

[gorgonite]

il n'est pas impossible d'avoir des listes qui se concatènent en temps constant... donc tout dépend ^^

[alex_pi]

il n'est pas impossible d'avoir des listes qui se concatènent en temps constant... donc tout dépend ^^

La contrepartie étant de ne plus avoir de structure persistante, et de perdre la première liste

[gorgonite]

La contrepartie étant de ne plus avoir de structure persistante, et de perdre la première liste

c'est pour cela que tout dépend

[SpiceGuid]

• ou bien tu n'as besoin que d'ajouter en fin de liste et alors il te suffit d'utiliser la liste "à l'envers" (l'ajout se fait en temps constant)
• ou bien tu as besoin d'ajouter à la fois au début et à la fin, dans ce cas la structure de données est une queue de Chris Okasaki (l'ajout se fait en temps amorti constant)

[Garulfo]

C'est même pire que ça je crois. Sauf erreur, à cause de la persistance, ajouter en fin de liste implique (en général) de recopier tout le reste de la liste, et pas seulement le traverser, non ?
Dans un cas trivial comme [2; 3]@[4], où la liste [2; 3] va être jetée tout de suite derrière, peut-être le compilo fait un truc sioux mais dans un exemple réel, ça doit aggraver l'effet d'un tail-consing.

Complètement d'accord. Mais si j'ai bien compris le problème, il ne fait que rajouter 1 élément en fin de liste. Mais peut être me trompes-je !

[Garulfo]

il n'est pas impossible d'avoir des listes qui se concatènent en temps constant... donc tout dépend ^^

La contrepartie étant de ne plus avoir de structure persistante, et de perdre la première liste

c'est pour cela que tout dépend

Et tu augmentes les risques de modifications par effet de bord.
Dangereux.

De plus la question portait sur @ non ?

[Jedai]

Le principal problème de la concaténation, c'est qu'on peut facilement créer des situations où on doit recopier plusieurs fois certains éléments inutilement, par exemple ceci :

Code :

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

(xs @ ys) @ zs

recopie deux fois les éléments de xs alors que :

Code :

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

xs @ (ys @ zs)

ne les recopie qu'une seule fois.
(l'associativité de @ rend les parenthèses de cette dernière version superflues)

Ce cas est très simple, mais en pratique en écrivant des fonctions récursives ou dans certaines situations en impératif, on peut se retrouver à utiliser @ de façon répétée dans le mauvais sens et ainsi flinguer sa complexité...

C'est une bonne idée de toujours vérifier qu'on n'utilise pas @ ainsi, c'est souvent assez facile à corriger.

--
Jedaï

[Jedai]

• ou bien tu n'as besoin que d'ajouter en fin de liste et alors il te suffit d'utiliser la liste "à l'envers" (l'ajout se fait en temps constant)
• ou bien tu as besoin d'ajouter à la fois au début et à la fin, dans ce cas la structure de données est une queue de Chris Okasaki (l'ajout se fait en temps amorti constant)

Dans le genre tu as aussi une certaine variante des Finger-Tree, qui te donne d'excellentes complexités pour plein d'opérations mal supportée par les listes (d'un autre côté, le facteur constant est assez fort tout de même, l'intérêt n'est donc pas toujours aussi évident qu'on pourrait le penser). Je vous donne un lien vers la doc de la version Haskell, où vous pourrez trouver les complexités des opérations.

--
Jedaï

[Invité]

LLB : je ma fait des fonctions de base que j'utiliserait souvant dans elles doivent être bien pensées.
Deux exemples :
1) garder les éléments positifs d'une liste

Code :

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

1
2
3
4
5
6
7
let elements_positifs (liste) =
	let rec elements_positifs_2 (liste, compteur_liste_vide) =
		if liste = [] 
			then compteur_liste_vide 
			else elements_positifs_2 (List.tl liste, if List.hd liste >= 0 then compteur_liste_vide @ [head liste] else compteur_liste_vide) in
 
	elements_positifs_2 (liste, []) ;;

2) doubler les éléments d'une liste

Code :

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

1
2
3
4
5
6
7
let double (liste) =
	let rec double_2 (liste, compteur_liste_vide) =
		if liste = []
			then compteur_liste_vide
			else double_2 (List.tl liste, compteur_liste_vide @ [(List.hd liste);(List.hd liste)]) in
 
	double_2 (liste, []) ;;

En fait je construit toutes mes fonctions selon ce principe, en récursion terminale, et ça me donne toujours des listes à l'envers alors j'utilise la concaténation ...
Une solution intermédiaire qui m'aie venue à l'idée serait d'obtenir une liste à l'envers avec des cons puis de la retourner une seule fois à la fin avec une fonction reverse, ce qui fait que le travail n'est fait qu'une seule fois (alors que dans mes fonctions actuelles il y a une concaténation à chaque appel récursif).

Donc garulfo , oui , j'utilise toujours un ajout d'un seul élément en fin de liste comme principe de base dans mes fonctions récursives.

>il n'est pas impossible d'avoir des listes qui se concatènent en temps constant... donc tout dépend ^^
>>La contrepartie étant de ne plus avoir de structure persistante, et de perdre la première liste
>>>c'est pour cela que tout dépend

C'est quoi votre solution mystère ?

[Jedai]

Ces fonctions sont horribles... Elles tombent complètement dans la catégorie que je présente, tu as transformé du O(n) en O(n^2) !

Une solution intermédiaire qui m'aie venue à l'idée serait d'obtenir une liste à l'envers avec des cons puis de la retourner une seule fois à la fin avec une fonction reverse, ce qui fait que le travail n'est fait qu'une seule fois (alors que dans mes fonctions actuelles il y a une concaténation à chaque appel récursif).

Ce serait déjà beaucoup mieux, tu en reviendrait à du O(n), ça reste tout de même plus lent que la solution non-récursive terminale. La récursivité terminale, c'est bien, mais ce n'est pas indispensable ! Sauf si tu as des listes énormes à manipuler, tu n'auras aucun problème avec les fonctions suivantes :

Code :

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

1
2
3
4
let keep_positives xs = filter (fun x -> x >= 0) xs
let double xs = concat (map (fun x -> [x; x]) xs)
 
let double_for_big_list xs = concat (rev (rev_map (fun x -> [x ; x]) xs))

(filter est récursive terminale apparemment, je suppose qu'elle fait un rev en interne)
--
Jedaï

[InOCamlWeTrust]

Quand j'ai débuté le Caml, j'utilisais souvent la concaténation. Je l'utlisais et je savais que je ne devais pas l'utiliser, car c'est horrible en temps et en mémoire (recopie de liste). Avec le temps, j'ai commencé à coder sans concaténation, et aujourd'hui je me rends compte qu'il s'agit d'un opérateur/fonction que je n'utilise plus du tout, tout simplement parce qu'il existe en général toujours une meilleure alternative.

Avant d'utiliser la concaténation, il faut se poser les questions suivantes :

- Est-ce que j'ai vraiment besoin de concaténer ? Est-ce qu'un simple ajout en tête de liste ne suffirait pas ?

- Si oui, les éléments de la liste ne peuvent-ils pas être ordonnés différemment ? J'ai eu beaucoup de cas de code où, finalement, l'ordre des éléments dans les listes n'intervenait pas : dans ce cas, il faut utiliser List.rev_append.

- Si l'ordre importe et que l'on doit, par exemple, ajouter les éléments successivement en fin de liste, c'est peut-être qu'il faudrait construire la liste dans l'autre sens, afin de ne plus avoir à les ajouter en fin mais en tête. Si à la fin de l'algorithme il faut parcourir la liste en sens inverse une ou deux fois pour récupérer les éléments, alors celà ne coûtera rien, au regard du temps gagné, à prendre la liste miroir.

- Sinon, pourquoi ne pas utiliser une autre strucutre de données ?

C'est le genre de truc que l'on acquiert avec l'expérience : il n'y a pas de recette magique.

Cependant, il y a une bonne pratique : ne JAMAIS utiliser la concatrénation de liste via l'opérateur @, mais UNIQUEMENT via la fonction dédiée, afin de n'en pas abuser.

[LLB]

(filter est récursive terminale apparemment, je suppose qu'elle fait un rev en interne)

En effet.

hellfoust : regarde le code de la bibliothèque standard. Le fichier list.ml est très simple à lire et combien de nombreux exemples. Sers t'en comme modèle, tu verras ils n'utilisent pas de concaténation (ou alors, juste dans le cas d'arrêt).

[alex_pi]

En fait je construit toutes mes fonctions selon ce principe, en récursion terminale, et ça me donne toujours des listes à l'envers alors j'utilise la concaténation ...

C'est bien joli de vouloir faire du récursif terminal, mais quand pour ça tu utilises l'oppérateur de concaténation qui lui n'est *pas* récursif terminal, tu perds clairement tout !

Je suis par ailleurs parfaitement d'accord avec les autres conseils qui t'ont été donné :-)

[Invité]

Ok,en fait , la clé c'est ... lire les librairies standards ! (surtout pervasives.ml et list.ml)
Il faut télécharger le source de OCaml pour y avoir accès , c'est pour ça que j'ai pas percuté plus tôt

C'est super pratique , on peut voir les fonctions de base (leur définition est un nom entre guillemets) et les fonctions formées à partir de ces fonctions de base (comme la concaténation) pour juger si elles sont légères ou pas. J'ai de quoi bosser maintenant

Merci à tous pour vos réponses !


IOCWT : les listes sont faciles à utiliser, et pour les types à déclarer soit même ... faut d'abord maitriser les types de base je pense.

alex_pi : c'est sur, et je voit maintenant que @ n'est pas terminal dans la librairie, et puis à présent je vais seulement retourner les listes à la fin : j'aurait la récursion terminale et les cons

Est-ce qu'a l'exécution, le fait de définir les fonctions temporaires de cette façon

Code :

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

(fun x -> x*x) 5 ;;

est plus léger que

Code :

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

1
2
let carre (x) = x*x in
carre (5) ;;

?
------------------------------------------------------

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'enfin je dit ça, peut-être que les mecs sont plus doués que moi en OCaml

[Invité]

La fonction List.rev_append est utilse lorsqu'on veut concaténer deux listes et que l'ordre des éléments n'as pas d'importance.
Mais on peut s'en inspirer pour faire une fonction concaténation plus légère , au lieu de

Code :

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

1
2
3
4
let rec (@) l1 l2 =
  match l1 with
    [] -> l2
  | hd :: tl -> hd :: (tl @ l2)

on peut avoir

Code :

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

1
2
3
4
5
let (@@) liste1 liste2 =
	let rec concatenation_aux (liste1_a_lenvers, liste2) = match liste1_a_lenvers with
		  tete :: queue -> concatenation_aux (queue, (tete :: liste2))
		| [] -> liste2 in
	concatenation_aux (List.rev liste1, liste2) ;;

[LLB]

IOCWT : les listes sont faciles à utiliser, et pour les types à déclarer soit même ... faut d'abord maitriser les types de base je pense.

En effet. Apprends déjà à bien te servir des types de base. Tu pourras appliquer son conseil plus tard.

Est-ce qu'a l'exécution, le fait de définir les fonctions temporaires de cette façon [...] est plus léger que [...]

Non. C'est vraiment de l'ordre du détail. Code de la façon la plus claire et lisible, et tout ira bien.

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

Pour la définition de valeur : tu t'en fiches, j'ose espérer que le compilateur génère le même code, qu'on donne un nom ou pas à la valeur inutilisée. C'est principalement une question de style.

Tu peux remarquer que la décomposition de la liste est très fréquent dans le module et qu'elle est toujours faite pareil. Nommer la queue de la liste sert dans certains cas, pas dans d'autres. Mais leur code reste à peu près consistant.

La décomposition, quel que soit l'ordre dans le code, doit tester si la liste est vide ou non. Je ne sais pas s'il y a une quelconque différence de performances, mais ça me semble cohérent de tester d'abord si la liste est vide. Là encre, ce n'est qu'une question de style. Remarque aussi qu'ils mettent leurs motifs toujours dans le même ordre, quelle soit la position de l'exception.