Skip to content


Stanford CS Education Library

Not everyone is lucky enough to enjoy a posh education at Stanford, but it shouldn’t prevent you to go to their Stanford CS Education Library and go through the material there. Pretty basic but good stuff. Currently dealing with Binary Trees (with a focus on C), and I am using this as Erlang tutorials, the DIY variant… There’s probably a good implementation of a binary tree [in the Chapter about Tuples of the Erlang doc], but I didn’t cheat and did it all on my own :D


Binary Search Tree

I have now a semi-functioning implementation of a binary search tree [a last minute "upgrade" of the code borked the lookup function, sigh]. It can, so far, create and add nodes to a parent, left or right; lookup a node well, when I fix the code that is…; calculate the maximum depth, minimum and maximum values, and the overall count of nodes; and mirror the tree – for some reason it took me more than 5 minutes, must be tired…

Note to self: unit tests are fine, as long as they don’t have bugs… Trying to debug a perfectly functioning piece of code because the unit test is bugged is a perfectly rotten way of spending time in front of the ‘puter…

I will probably open soon a code repository for all my Erlang efforts – learning CVS on the way, it cannot hurt. If and when, I’ll post the url.

I wonder how fast my bst would be if I dumped 22,000+ XML nodes, parsed to strings… Not that it would make sense, but it would sure be fun to try!

Erlang

Posted in Articles, Code, Erlang.


12 Responses

Stay in touch with the conversation, subscribe to the RSS feed for comments on this post.

  1. Christian says

    Salut,

    En tant que prof de programmation fonctionnelle, je suis emu de lire ce blog… Je me surprends a imaginer mes eleves faire de meme… Et puis je chute de 10 000 metres et je me reveille:-)

    J’ai parcouru le lien vers Stanford et ce n’est pas une presentation fonctionnelle des arbres binaires de recherche! Ce n’est donc pas bon pour ton apprentissage, qui consiste (1) a oublier les pointeurs, la gestion de la memoire (2) apprendre l’algebre.

    Mon site incomplet contient un cours sur Objective Caml et surtout des exercices qui sont une meilleure introduction, et il y en a de bien meilleures ailleurs.

    Quant a utiliser les ABR comme dictionnaire de noeuds XML, c’est pas dit que ca soit interessant. Quelles sont sont les clefs? Et puis, deja, il faut des arbres AVL (une variante equilibree des ABR), pas de simples ABR. Et puis c’est pas dit que ca se comporte bien. Parfois une table de hachage fait mieux l’affaire. C’est la une lecon des langages fonctionnels: il faut utiliser les paradigmes qui conviennent le mieux pour des situations donnees.

    N’oublie pas d’etudier Subversion. C’est une nette amelioration sur CVS, tout en lui ressemblant comme un frere. Je ne peux plus m’en passer.

    Bonne chance et amuse-toi bien!

  2. dda says

    Christian선생님 :-)

    Je vois que je vais devoir reformuler mon post. Il est vrai que je l’ai écrit très tard, après mon dernier marathon erlanguien… Je me suis mal exprimé ! Ce que je voulais dire c’est :
    1. il y a une bonne ressource générale de programmation dispo à Stanford CS Edu;

    2. n’ayant jamais eu de formation “académique” en informatique [mais ayant 25 ans de programmation derrière moi... ;-)], il me manque des chapitres parfois, en tout cas théoriques, et appliquer la théorie dans ces matériaux à mon apprentissage d’Erlang. Ergo, par exemple, comment créer un arbre binaire sans regarder la doc d’Erlang… Un moyen comme un autre de vérifier que j’ai bien intégré les notions de pattern matching et de tail recursion. Apparemment, pas trop mal ! Admettons que je cherche, à l’aube de mes 40 ans, à me rassurer sur la taille de mon… cerveau !

    3. La référence dans la dernière partie à XML était de l’humour, lié à mes efforts récents de parser des monstrueux fichiers, comme tu le sais… L’idée m’est venue – à quatre heures du matin, excusable, donc – et si je balançais les 22,000+ nœuds du fichier xxxx.xml dans un bst [tiens, on dit ABR en francaoui... Arbre Binaire de Recherche] ?. Cela ne m’apporterait rien, puisque les éléments de ce fichier n’ont pas de relation aborescente de ce type. Mais quand on veut tester du code, surtout en vitesse, il faut des bons gros test cases, et un fichier XML de 35Mo me semblait approprié ! Quant aux clefs, j’avais pensé au hash md5 du contenu… On fait ce qu’on peut, à ces heures tardives !

    J’ai vaguement lu au sujet des arbres AVL – là en français les initiales des trois gugusses ne changent pas ;-) – mais je n’ai pas encore approfondi la quoueshtionne, une chose à la fois… Mais c’est au programme ! Quant aux hash tables, ça fera partie du programme, même si dans mon super parseur Erlang je les utilise déjà “sans le savoir” [contre l'avis de la documentation] : je store les différents éléments d’un nœud dans le process dictionary jusqu’au moment où j’ai un nœud complet. Et je soupçonne fort que les dictionnaires sont à base de hash table. C’est le cas dans les autres langues, pourquoi pas ici ? Me trompè-je ?

    Quant à tes matériaux, je me rue dessus. Il se trouve que je suis intéressé par la compilation et l’interprétation, ça tombe à pic !

    Non à l’horrible anglicisme interprèteur !
    Christian++

  3. Christian says

    dda, en fait je suis un de tes admirateurs secrets, depuis une serie de commentaires que tu as pondu chez la Marmotte l’an dernier, ou tu as montre a quel point la linguistique est quelque chose de beau et puissant, sans compter la maitrise du coreen, des caracteres chinois, de l’histoire et de la psychologie de l’autochtone.

    Il n’est pas besoin qu’il existe une “relation arborescente” naturelle entre elements d’un ensemble pour pouvoir les placer dans un arbre de recherche, il suffit juste d’avoir un ordre total sur l’ensemble (tu peux comparer toute paire d’elements). C’est toi qui choisi la relation d’ordre.

    Les dictionnaires sont souvent implantes a base de tries, en francais arbres digitaux. Je cause un poil de ca dans mon cours Information Retrieval (le mot anglais trie provient de la troncature de retrieval). Les tables de hachages ne sont pas indiquees dans le cas des dictionnaires humains, me semble-t-il, a cause de la faible dispersion des codes de hachages (beaucoup de mots sont proches, par exemples partagent des prefixes a la pelle et une fonction a du mal a les disperser dans la table). Une table de hachage n’est efficace qu’en moyenne (par rapport au pire des cas), et a la condition d’avoir une bonne (dans un sens statistique) fonction de hachage — sinon gare au paradoxe des anniversaires (la probabilite d’avoir deux personnes au moins ayant meme date anniversaire est superieure a 50% des que le groupe compte plus de 23 personnes), et pourtant elles sont toutes independantes!

    Je connais un dictionnaire de sanscrit par Gerard Huet, une grosse pointure… en logique formelle et programmation fonctionnelle, qui emploie la technique du trie (optimisee pour partager les suffixes). Cf. la page de G. Huet ainsi que ses publis de linguistiques informatique. Tu vas adorer ce qu’il fait!

    Malheureusement, je ne comprends pas le jargon linguistique… J’aimerais comprendre la linguistique, vraiment. Je sens qu’il a encore matiere a croiser l’info et la linguistique de facon innovante. Bon, mais je comprends les langages fonctionnels, c’est deja ca. Je te felicite de vouloir comprendre les deux!

    Ah, oui, interpreteur, quelle horreur. J’aime les langues. (Si tu lis l’espagnol, tu peux toujours acheter ma traduction de Pablo Neruda chez Gallimard, qui est bilingue.)

    Allez, hop! Je retourne a mon probleme (J’essaie de faire accepter a Yacc une grammaire d’un langage vraiment abominable depuis deux semaines. En fait j’utilise un generateur d’analyseurs syntaxique plus puissant (LR(1)) mais c’est dur dur quand meme.) L’idee est de traduire ce langage vers les schemas XML.

    Bon courage! [Et rassure-toi a propos de ton cerveau...]

  4. dda says

    Et en plus j’ai des fans maintenant !… :-)

    arbres de recherche : hmmmm. Donc je pourrais mettre mes nœuds dans l’arbre dans l’ordre où ils arrivent, donc. La difficulté serait de bien balancer les branches, de façon à ne pas avoir un arbre qui penche tout du côté gauche… Hmmm… Partir de 1, et chaque fois que l’on descend, multiplier cet accumulateur par 2 et vérifier que l’on a stocké (accumulateur) nœuds à ce niveau avant de descendre d’un niveau. Mouais mouais mouais…

    La table de hash marcherait bien dans mon cas je pense, car j’ai des clefs uniques pour chaque nœud – un bête numéro à la con. C’est d’ailleurs ce que j’utilisais dans la première version de mon parseur, avant de changer pour une bdd sqlite3 en mémoire [beaucoup plus rapide].

    L’espagnol ne fait pas encore partie de mon paquetage… ça viendra peut-être un jour !

  5. Christian says

    Si les clefs sont entrees dans l’arbre de recherche dans l’ordre (croissant ou decroissant), alors tu obtiens une liste… triee, heureusement, mais tout a fait ininteressante. On prouve qu’en moyenne l’arbre est equilibre ou presque, ceci dit. Donc: dans le pire des cas, ce n’est pas terrible, mais en moyenne c’est bon. Un arbre equilibre implique un acces a un noeud en un temps proportionnel a la hauteur du noeud, qui est alors un logarithme de l’arite de chaque noeud (deux si binaire), en la supposant fixe. Pour garantir un temps logarithmique dans le pire des cas, il faut utiliser un AVL ou un arbre rouge-noir, par exemple. Malheureusement, c’est plus complique que tu ne le decris, il faut faire des rotations de sous-arbres de facon a garantir l’invariant qui dit que la difference de hauteur maximale entre deux sous-arbres freres est toujours au plus un (en valeur absolue). Tu peux te reporter Elements d’algorithmique pour une bonne presentation des arbres rouge-noir.

    Si tes clefs sont uniques, ca n’implique pas que la table de hachage soit indiquee: si les clefs sont trop dispersees (sur l’ensemble des entiers), tu dois allouer (enfin, la lib qui te fourni la table) un tableau, donc un bout de memoire contigue, qui va etre sous-utilisee, car trouee… En fait, comme le paradoxe des anniversaires le suggere, les collisions de clefs sont rapidement tres probables, meme si les clefs sont dispersees uniformement. La gestion des elements dont les clefs sont en collisions peuvent etre simplement chaines (et donc accedes sous une meme clef, puis recherche dans cet arbre de collisions) ou, fin du fin, stockes dans un arbre de recherche equilibre (ceinture et bretelles).

    Je ne sais pas si je suis clair…

  6. dda says

    Je me disais bien que j’avais une vision simpliste des choses… :-) Et voilà-t-y pas que les arbres se prennent pour Stendahl… [Entre parenthèses tes liens ne passent pas. Mets les en clair je modifierai].

    Pour les clefs, je comprends l’histoire de la dispersion de mes entiers – mais je n’ai pas ce souci, a priori. Et je n’aurai pas de collision, bikoze le logiciel qui produit se fichier se sert de ses clefs pour y retrouver ses cochons. Donc clefs uniques. Et mon approche Vikingesque de la collision de clefs serait l’écrasement des données précédentes :D Sans blague !

    Tu es très clair, merci pour toutes ces explications… Que de choses à apprendre…

  7. Christian says

    Ah oui, j’ai lu le source HTML et je constate que je ne connais pas HTML. C’est pourquoi je m’interesse a XML:-)

    Le lien escamote vers le bouquin d’algo est Elements d’algorithmique. Quant a mon cours Information Retrieval, il contient quelques infos utiles sur les arbres digitaux (pour les dictionnaires). Au passage, si tu t’interesses a la recherche de chaines de caracteres dans du texte, ma presentation de l’algo de (Knuth,)Morris et Pratt est meilleure que celle de ce bouquin (une boucle en moins, non mais).

  8. dda says

    Le lien d’élément d’algorithmique n’est toujours pas passé…
    Quant à ton cours je me suis jeté dessus – pas trop le temps, mais un cours qui a un chapitre sur les DFA, je prends…

  9. Christian says

    Je ne comprends decidement pas pourquoi… C’etait

    http://www-igm.univ-mlv.fr/~berstel/Elements/Elements.html

    Berstel et Chretienne etaient mes profs a Paris VI, au siecle dernier. J’adore leur style, c’est rare de lire un textbook aussi bien redige, pas d’anglicisme, un francais impeccable qui ne prend pas le lecteur pour un lecteur de “Metro”, une structure logique, des definitions pour tous les concepts, une composition en LaTeX et des figures vraiment claires (attention, un automate est faux, ceci dit), en particulier le chapitre sur les arbres.

    Quant aux automates finis, j’ai fait pas mal de redites entre mon cours de compilation (en anglais) et celui de recherche d’information, avec quelques differences dans le focus.

    Ma presentation, comme toutes mes presentations, a volontairement un cachet algebrique, meme si ce n’est pas une veritable theorie algebrique des automates (c-a-d. j’utilise des ensembles, mais aussi des fonctions), car cela permet de s’abstraire des boucles et des pointeurs. Apres, libre a chacun d’implanter tout cela comme il veut ou peut (avec un langage fonctionnel, une presentation algebrique facilite toujours la tache, meme s’il faut parfois renoncer au tout fonctionnel pour des raisons d’efficacite). En tout cas, c’est la base de la base que tu as la, et j’ai bosse tres dur pour la rendre accessible (toutes les figures sont codees en LaTeX, en plus).

    Si tu veux en savoir plus, ou plus sur un sujet particulier, n’hesite pas a me le demander ici ou par courrier.

    Par exemple, si tu prevois d’appliquer la theorie des automates a la recherche efficate de texte dans du texte, il y a un excellent bouquin en francais la-dessus (les chercheurs francais sont tres bons dans ce domaines) que je peux te recommander.

    En pensant a toi, j’ai mis en ligne quelques supports de plus. Il manque les sources, car je dois comprendre comment les integrer dans ma moulinette perso qui met automatiquement a jour mon site a partir de ma base Subversion de documents LaTeX.

    Amuse-toi bien!

  10. dda says

    Moi qui n’ai jamais été passionné par les maths… J’ai fait A2 qui plus est… Dur dur ! Il va falloir que je reprenne des cours intensifs !

    En fait, c’est la faute de mes profs [ce ne peut pas être de ma faute, voyons !] : il n’ont jamais sû répondre à une question simple, que je leur posais souvent, du moins avant de décrocher. À quoi ça sert ? Désarmant n’est-ce-pas ?

    Je suis passionné entre autres par les expressions régulières [?], les regex quoi, et j’ai toujours voulu en savoir plus sur “comment ça marche”. Mais la plupart du temps, les implémentations sont du type PCRE/NFA, et j’ai eu du mal à trouver de la doc abordable [du code source quoi :-)] sur les DFA. Mais si j’avais été à P6 au lieu de P7 j’en saurais plus à l’heure qu’il est…

    Je vois bien comment un automate pourrait être plus facile/moins difficile à écrire en langage fonctionnel [enfin je n'en connais qu'un et si peu...]. Ce ne serait pas forcément plus rapide/efficace – difficile de faire mieux qu’en pur C je pense, enfin si y’aurait bien l’assembleur, mais je chipote nostalgiquement, là – avec du pattern matching [désolé pour les anglicismes, tout mon vocabulaire me vient de "là-bas"] à ne plus quoi savoir en faire.

    Encore merci pour tout !

  11. Christian says

    Les maths servent a resoudre des problemes, comme par exemple tuer le temps (avant qu’il nous tue). Ou alors elles ne servent a rien, comme la musique, l’architecture, l’informatique (on peut vivre sans), ca depend du point de vue. L’informatique est a tort consideree par les eleves ingenieurs comme une branche du bricolage, au mieux de l’artisanat, mais pas des sciences. Inquietant, pour des ingenieurs. J’ai tendance a penser que le succes des maths est tel qu’on ne le voit pas. C’est ca la veritable marque du succes, comme l’apparition de l’oxygene dans la biosphere. On peut poser son regard n’importe ou et, comme dans The Matrix, on pourrait voir le code si on savait regarder. Quelle immeuble sans maths? Quel telephone? Et en meme temps, heureusement qu’on ne voit pas tout ca tout le temps. Un musicien professionnel m’a avoue un jour qu’il n’aimait pas ecouter de la musique car il ne pouvait s’empecher d’entendre les notes…

    Aborder les automates et les expressions regulieres par le code source, c’est encore prendre l’informatique par le bout du bricolage. Au mieux, on deviendra bricoleur, mais, en tant que tel, on ne sera jamais capable de construire l’equivalent logiciel d’un barrage. Pour passer a l’echelle, pour abstraire de nouveaux problemes, il faut de la theorie, et les automates sont la voie royale pour demontrer en quoi la theorie est efficiente.

    Dans mon cours de compilation en anglais je presente la compilation des expressions regulieres vers les automates asynchrones (epsilon-NFA), et leur transformation en NFA puis DFA. Mais attention, en pratique, ce n’est peut-etre pas comme ca qu’il faut proceder, a cause de l’explosion possible du nombre d’etat (la determinisation est exponentielle dans le pire des cas, comme je le montre dans le cours Information Retrieval).

    Quant a l’interet d’utiliser un langage fonctionnel pour implanter des automates, tout depend du type d’automate, du type d’application et du type de langage, ce n’est pas si simple. Evidemment, C est tres rapide. Mais si l’efficacite etait le seul critere, on pondrait de l’assembleur soi-meme, comme tu dis, et il y a de vraies bonnes raisons de ne pas faire cela (pas tout le temps). Si le type d’application est la recherche d’occurrences de chaines dans des chaines, et si les automates sont des DFAs, alors C est une bonne idee. Mais si les automates sont des automates a pile tres compliques pour generer des analyseurs syntaxiques, j’y reflechirais a deux fois avant d’envisager C (meme si ca se fait, par exemple Yacc).

    L’inconvenient d’Erlang est l’absence de typage strict et fort a la compilation. Mais cette option a ses fans, comme pour Scheme et LISP. Moi j’accepte de ceder un peu de liberte contre une aide sans faille (d’aucuns diraient faciste:-) du compilateur.

    On peut traduire pattern matching par filtrage de motifs.

    L’interet d’une presentation algebriciste (osons) des automates et autre est qu’elle permet de s’abstraire d’un modele de machine ou de calcul particulier. Pas de memoire, pas de temps. Comme en maths. Tu deroules une equation jusqu’a trouver le resultat. Ca permet de comprendre le concept. Apres, et seulement apres, tu codes, et, la, tu fais autrement si tu juges que c’est plus efficace, par exemple, ou parce que tu n’as pas le choix (contraintes exterieures). Alors, evidemment, tu ne fais pas comme ca pour programmer un menu ou des widgets, attention, ce n’est pas de la religion, il faut etre pragmatique sans etre ignorant (donc connaitre la theorie et, eventuellement, ne pas s’en servir expres).

    A mon avis, si on est bon en grammaire et en linguistique, comme toi, on n’a pas de mal a piger l’algebre des langages fonctionnels et la compilation (le calcul symbolique, en somme). Ca demande “seulement” d’oublier tout ce qu’on croit savoir sur la programmation et de lire les bons livres.

    Et apres les langages fonctionnels, il faudrait jeter un petit coup d’oeil a la programmation a logiques, comme Prolog. C’est vraiment puissant et deconcertant. Tellement de belles choses a decouvrir…

  12. Christian says

    Ah oui, j’oubliais. Dans mon cours d’intelligence artificielle, hormi les reseaux de neurones, tout le reste peut t’interesser car il s’agit essentiellement d’une approche fonctionnelle de la programmation, mais sans se fonder sur un langage particulier. Il s’agit de specifications algebriques (comme des modules, si tu preferes, avec interfaces (appelees ici signatures) et en-tetes (appelees ici type abstraits)). Je traite en long, large et en travers tout ce qu’on peut faire avec une ou des piles, file d’attente et les parcours d’arbres. Tout ca sans pointeurs, c’est-a-dire sans les mains! :-)

You must be logged in to post a comment.