Utilisation des listes

 

Jack.R, 2006-09-04. Un rappel sur l'utilisation des listes


Pourquoi

Parce que lorsque j'ai débuté en Tcl/Tk, elles m'ont posé quelques problèmes :


Le résumé

Le nom de la liste n'est utilisé que:

Dans tous les autres cas, on travaille sur le contenu de la liste.

linsert, lreplace et lsort ne modifient pas la liste existante mais retournent une liste modifiée.


Un exemple vaut mieux qu'un long discours

   set Unites [ list "un" "deux" "quatre" "cinq" "six" "sept" "8" ]
   puts "La liste Unites contient : $Unites"
   puts ""

   # llength retourne le nombre d'éléments de la liste
   set NbElements [ llength $Unites ]
   puts "Elle contient $NbElements éléments."

   # lindex retourne l'élément à l'index donné. Attention commence à 0
   puts "Leur numérotation commence à 0, on a donc:"
   puts " - élément 0: [ lindex $Unites 0 ] "
   puts " - élément 3: [ lindex $Unites 3 ] "
   puts ""

   # lsearch retourne la position d'un élément
   set Position [ lsearch $Unites "quatre" ]
   puts "L'élément \"quatre\" se trouve en position $Position"
   puts ""

   # linsert retourne la liste modifiée mais ne touche pas la liste existante
   # Si on veut modifier la liste existante, il faut la réaffectée
   puts "On ajoute \"trois\""
   set Unites [ linsert $Unites 2 "trois" ]
   puts "La liste Unites contient maintenant: $Unites"
   puts ""

   # lappend ajoute en fin de liste existante
   puts "On ajoute \"neuf\""
   lappend Unites "9"
   puts "La liste Unites contient maintenant: $Unites"
   puts ""

   # lreplace retourne la liste modifiée mais ne touche pas la liste existante
   # Si on veut modifier la liste existante, il faut la réaffectée
   puts "Oops, on corrige"
   set Unites [ lreplace $Unites 7 8 "huit" "noeuf" ]
   puts "La liste Unites contient maintenant: $Unites"
   puts ""

   # lset modifie la liste existante
   puts "Re oops, on re-corrige"
   lset Unites 8 "neuf"
   puts "La liste Unites contient maintenant: $Unites"
   puts ""

   set Dizaines [ list "dix" "vingt" "trente" "quarante" "cinquante" \
   	   "soixante" "soixante dix" "quatre-vingt" "quatre-vingt dix" ]
   puts "La liste Dizaines contient : $Dizaines"
   puts ""

   # join met bout à bout les éléments de la liste en les séparant par
   # le séparateur fourni
   puts "Si on joint les éléments par un \"-\", on obtient:"
   set Texte [ join $Dizaines "-" ]
   puts $Texte
   puts ""

   # split convertit une chaîne en une liste en utilisant le séparateur
   # fourni comme délimiteur d'éléments
   puts "Si maintenant on sépare ce texte sur les \"-\", on obtient:"
   puts [ split $Texte "-" ]
   puts "Observez ce que sont devenus quatre-vingt et quatre-vingt dix"
   puts ""

   # concat met bout à bout les listes
   set Cumul [ concat $Unites $Dizaines ]
   puts "Mettons nos deux listes bout à bout (concaténation)."
   puts "On obtient : $Cumul"
   puts "alors que les listes originales n'ont pas bougées"
   puts "Unites: $Unites"
   puts "Dizaines: $Dizaines"
   puts ""

   # lsort trie la liste en fonction des options fournies
   # Si on veut modifier la liste existante, il faut la réaffectée
   puts "Trions notre liste Unites en ascii de façon décroissante"
   set Triee [ lsort -ascii -decreasing $Unites ]
   puts "Triee: $Triee"
   puts "Unites: $Unites"
   puts ""

Trie d'une liste en fonction d'une autre

On dispose d'une liste de valeurs que l'on souhaite réorganiser (trier). La réorganisation est décrite par une autre liste qui indique la position que doit prendre l'élément de même index de la liste de valeurs.

On a:

On veut:

La première idée consiste à utiliser une boucle for. En remplacant la boucle for par un foreach on obtient un gain de performance significatif (test ci-dessous). Si vous avez d'autres idée d'optimisation, n'hésitez pas.

   proc init {} {
     # Nombre d'elements a trier
     set ::max 10000
     # Nombre de repetition du trie
     set ::nb 800
     # Liste des valeurs
     set ::srcList {}
     expr { srand(73) }
     for { set i 0 } { $i < $::max } { incr i } {
       set n [expr {int(rand() * $::max)}]
       lappend ::srcList $n
     }
     # Liste des positions
     set ::idxList {}
     expr { srand(25) }
     for { set i 0 } { $i < $::max } { incr i } {
       set n [expr {int(rand() * $::max)}]
       lappend ::idxList $n
     }
     # Liste des valeurs triees
     set ::dstList [ split [ string repeat "1" $::max ] "" ]
   }

   proc sortFor {} {
     for { set i 0 } { $i < $::max } { incr i } {
       set idx [ lindex $::idxList $i ]
       set value [ lindex $::srcList $i ]
       lset ::dstList $idx $value
     }
     set result [ join $::dstList "" ]
   }

   proc sortForeach {} {
     foreach idx $::idxList value $::srcList {
       lset ::dstList $idx $value
     }
     set result [ join $::dstList "" ]
   }

   # Trie par boucle for
   init
   set timeStart [ clock clicks -milliseconds ]
   for { set i 0 } { $i < $nb } { incr i } {
     sortFor
   }
   set elapse [ expr { [ clock clicks -milliseconds ] - $timeStart } ]
   puts "sortFor: $elapse millisecondes"

   # Trie par boucle foreach
   init
   set timeStart [ clock clicks -milliseconds ]
   for { set i 0 } { $i < $nb } { incr i } {
     sortForeach
   }
   set elapse [ expr { [ clock clicks -milliseconds ] - $timeStart } ]
   puts "sortForeach: $elapse millisecondes"

Discussion


Catégorie Exemple | Catégorie Conseils pour débutants