Complexité d'un parcours d'arbre

Bonjour,

J'ai une fonction, je peux l'écrire de deux façons différentes, et je cherche la meilleur en complexité.
Note : c'est de la prog fonc, donc sans affectation.

Le contexte :
Les arbres lexicographiques i.e. des arbres n-aires où chaque noeud est étiqueté par un booléen indiquant si le sous-arbre qui commence à ce noeud contient le mot vide, et chaque branche est étiqueté par des lettres.

Grosso-modo, mon type est défini comme ceci :

Code:

---

1 2 3 4 5

type 'a lextree = { has_epsilon : bool ; table : 'a table } and 'a table = ('a * 'a lextree) list ;;

---

Globalement ça dit que lextree est une structure avec un booléen et une table, et que la table contient une liste de couple (lettre, arbre).

J'ai écrit une fonction qui prend un arbre t et un début de mot w et qui doit retourner la liste des mots (sous forme de liste de liste de lettres) contenu dans t en les préfixant par w.

Elle est actuellement écrite comme ceci (à peu de choses près) :

Code:

---

1 2 3 4 5 6 7 8 9

iterate t w: Si t.epsilon alors ajouter le mot w à la liste résultat fsi   pour chaque couple (x, lex) de t.table iterate lex w@[x] fpour

---

Le @ représente l'opération de concaténation. C'est à dire qu'il parcours la liste w pour y ajouter la liste contenant uniquement l'élément x. Et bien sûr, comme on est dans un langage fonctionnel, il va y avoir autant de création de cellules de liste qu'il y avait de lettres dans w.

Elle n'apparaît pas ici, mais en fait il y a une liste résultat en paramètre supplémentaire à la fonction pour ajouter les mots sans faire de concaténation.

J'ai essayé de déterminer la complexité de cette fonction en nombre de création de cellules de liste.
Si on appel n le nombre de mots dans le lextree, et m la taille moyenne d'un mot. (as-t-on m ~= log n ?)
On a au minimum n créations de cellules pour ajouter les mots dans la liste résultat.
Ce à quoi il faut rajouter le nombre de création de cellules dûes aux concaténations de w et [x].
Pour rappel l1@l2 crée autant de cellules qu'il y en avait dans l1.
J'ai envie de dire n*m^2, mais je suis pas sûr.


La deuxième version consiste à stocker w à l'envers pour avoir juste une création de cellule à la place de la concaténation quand on rajoute une lettre dans w.
Par contre, il faudra remettre la liste à l'endroit avant de l'ajouter dans la list, et ça c'est en O(m). Donc rien que remettre les listes à l'endroit avant concaténation dans la liste résultat donne un algo en O(n*m). Ce à quoi il faut rajouter la construction de cellules pour rajouter les lettres au début de w quand on descend les appels récursifs.
Mais là, pour ça je bug un peu.
Comme c'est un arbre, on réutilise le w en paramètre, donc y'a beaucoup moins que n*m opérateur cons (ou ::, construction de cellule) pour construire le mot...


Je pense qu'au final les deux algos ont des complexité équivalentes, mais juste pour le fun, j'aimerai savoir ce que c'est.


Merci d'avance.

Voyons, en Haskell j'écrirais ça comme ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

module Main () where import Data.List import qualified Data.Map as M   data Dict = Dict { epsilon :: Bool, table :: M.Map Char Dict } deriving (Read, Show, Ord, Eq)   listWords (Dict False ds) = concatMap (\(c,d) -> map (c:) $ listWords d) $ M.toList ds listWords (Dict True ds) = "" : listWords (Dict False ds)   empty = Dict False M.empty   list2Dict = foldr addWord empty   addWord [] d = d { epsilon = True } addWord (c:cs) d = d { table = M.alter addChain c (table d) } where addChain Nothing = Just $ addWord cs empty addChain (Just d) = Just $ addWord cs d

---

(où j'ai remplacé ta liste de paires par une Map, nettement plus efficace... et surtout une interface plus agréable pour les mises à jours)

La partie importante de ton point de vue est :

Code:

---

1 2 3 4

listWords (Dict False ds) = concatMap (\(c,d) -> map (c:) $ listWords d) $ M.toList ds listWords (Dict True ds) = "" : listWords (Dict False ds)

---

Qui correspond à ton code et a la meilleure complexité possible. Bien sûr ce n'est pas tail récursif, mais quelle taille fait le plus grand mot de ton dictionnaire ? Assez pour faire exploser ta pile ? Normalement on devrait en être très très loin.

--
Jedaï

Désolé, je lis assez mal le haskell. En fait je connais pas du tout. :P

La fonction est déjà écrite

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

let iterate_dictionary d w = (* l représente la liste de mots en cours de construction *) let rec aux d w l = let ll = List.fold_right (fun (x, t) l -> aux t (w @ [x]) l ) (iterate d.table) l in if has_epsilon d then w::ll else ll in aux d w [] ;;

---

Ma question concerne simplement sa complexité.
La fonction iterate_dictionary prend un dico et un début de mot.
Je défini une sous-fonction aux qui prend en plus un paramètre l, la liste de mots déjà calculée.
Cette fonction aux parcours la table de droite à gauche (pour garder les mots triés) puis elle rappelle aux sur tous les sous-arbres trouvés, bien entendu en rajoutant la lettre x à la fin du mot w de telle sorte que la récursion suivante ait un paramètre w qui a simplement une lettre en plus.
Une fois la table parcourue, je rajoute w dans la liste résultat si le dico contenait epsilon.

À priori on ne s'amuse pas à mettre des mots assez longs pour faire exploser la pile.
Cela dit, j'ai quand même une liste de mots de tests assez conséquente (plusieurs centaines de milliers de mots).

Code:

---

w @ [x]

---

Dès que tu vois ça dans un morceau de code qui va souvent être répété, tu dois te dire : horreur qu'ai-je fait !

La complexité de ton opération dépend pas mal de la structure de ton arbre mais au pire, elle sera effectivement en O(n*m^2) où n est le nombre de mots et m est la longueur maximale de ces mots...

Ton autre idée, d'ajouter à l'envers puis d'inverser tous les mots est meilleure, elle sera en O(n*m), tout comme mon code, sauf que le tien aura probablement de plus grosse constantes (il y a une opération d'inversion en plus).

--
Jedaï

La première version utilisait une autre concaténation pour la liste de mots. :)
Mais là, je me demandais si ça allait réellement faire descendre la complexité de changer ce @.

J'ai quand même du mal à visualiser la complexité de la fonction donnée :
Si à chaque noeud de l'arbre possède k fils.

Le nombre de création de cellules en descendant les appels récurifs va être un truc genre :
1*k // premier étage, je crée une liste d'une seule cellule pour construire le w suivant.
+ 2*k*k // 2 parce qu'il faut reconstruire la liste qui contenait déjà un élément, k*k parce que c'est le nombre de lettres à cet étage. (un "étage" compte toutes les branches de profondeur i)
+ 3*k*k*k
+ ...
+ m*k^m // On s'arrête à m parce que c'est la taille moyenne des mots.
= O(k^m) // Je suis absolument pas sûr

Est-ce que k n'est pas une fonction de n, le nombre de mots ?
Si c'est le cas, ça nous fait une fonction en O(n^m). C'est pas mal mauvais...


Sans concaténation (donc avec des mots renversés) :
k // Premier étage, on ajoute une lettre en début de list
+ k*k // deuxième étage, on rajoute une lettre en début de mot
+ ...
+ k^m
+ k^m * m // Pour chaque mot dans les feuilles, on le met à l'endroit.

Sauf que maintenant que j'y réfléchis, je crois que k^m = n, le nombre de mots.

Bref, je me perd dans mes calculs... :s