Les tables de hachage en Factor sont des tableaux associatifs, c'est-à-dire des collections de paires key/value avec une recherche en O(1). Elles font partie de la famille plus large des assocs.
H{ { "coal" 1 } { "wood" 2 } } .
H{ } est une table de hachage vide. Les tables de hachage sont mutables : elles grandissent et rétrécissent quand on ajoute et retire des clés. Pense à clone d'abord si tu veux laisser la table d'origine intacte. Afficher une table de hachage montre ses entrées, mais leur ordre n'est pas lié à l'ordre d'insertion : les tables de hachage ne sont pas ordonnées.
at (dans assocs) lit une valeur et renvoie f si la clé est absente :
at ( key assoc -- value/f )
key? ( key assoc -- ? )
"coal" H{ { "coal" 1 } { "wood" 2 } } at . ! => 1
"gold" H{ { "coal" 1 } { "wood" 2 } } at . ! => f
set-at ajoute ou écrase ; delete-at supprime ; change-at exécute une quotation sur la valeur courante. Toutes les trois modifient la table sur place :
set-at ( value key assoc -- )
delete-at ( key assoc -- )
change-at ( key assoc quot: ( old -- new ) -- )
H{ } clone 5 "coal" pick set-at .
! => H{ { "coal" 5 } }
inc-at, le raccourci pour compterinc-at (également dans assocs) ajoute 1 à la valeur existante d'une clé, en l'insérant à 1 si elle est absente. Parfait pour tenir un décompte :
inc-at ( key assoc -- )
H{ } clone "coal" over inc-at .
! => H{ { "coal" 1 } }
assoc-each parcourt chaque paire ( key value -- ) ; cache renvoie la valeur d'une clé, en la calculant une seule fois avec la quotation fournie si la clé est absente.
assoc-each ( assoc quot: ( key value -- ) -- )
cache ( key assoc quot: ( key -- value ) -- value )
cache est le motif « chercher ou créer » en un seul mot, pratique quand on construit une table de hachage à partir d'un flux de clés et qu'on ne veut pas gérer le cas de l'entrée manquante à chaque site d'appel.
Quand l'entrée est une séquence de clés et que tu veux mettre à jour la table de hachage une fois par clé, parcours la séquence avec each et utilise une quotation frite '[ _ … ] (issue de fry) pour incorporer la table de hachage dans le corps de la boucle. Par exemple, pour supprimer une liste de clés :
{ "wood" "iron" } H{ { "coal" 5 } { "wood" 3 } { "iron" 2 } } clone
[ '[ _ delete-at ] each ] keep .
! => H{ { "coal" 5 } }
'[ _ delete-at ] capture la table de hachage située au-dessus d'elle sur la pile, de sorte qu'à chaque itération each n'a plus qu'à fournir la clé. keep exécute la quotation tout en préservant la table de hachage pour le . final.
map>assoc (dans assocs) applique une quotation à chaque élément d'une séquence et rassemble les résultats ( elt -- key value ) dans un assoc du type de l'exemplaire :
map>assoc ( seq quot: ( elt -- key value ) exemplar -- assoc )
{ "wood" } [ dup length ] H{ } map>assoc .
! => H{ { "wood" 4 } }
keys et values (dans assocs) renvoient uniquement les clés ou uniquement les valeurs ; >alist renvoie les paires { key value }.
keys ( assoc -- keys )
values ( assoc -- values )
>alist ( assoc -- alist )
H{ { "wood" 11 } { "coal" 7 } } keys . ! the keys (order not guaranteed)
H{ { "wood" 11 } { "coal" 7 } } values . ! the matching values
keys et values se correspondent : la valeur à une position donnée appartient à la clé à la même position.
sort-keys (dans sorting) renvoie les paires { key value } triées par clé :
H{ { "wood" 11 } { "coal" 7 } } sort-keys .
! => { { "coal" 7 } { "wood" 11 } }
>hashtable (dans hashtables) est l'inverse de >alist : il transforme n'importe quel assoc, le plus souvent un alist de paires { key value }, en une table de hachage avec une recherche en O(1).
>hashtable ( assoc -- hashtable )
{ { "coal" 7 } { "wood" 11 } } >hashtable .
! => H{ { "wood" 11 } { "coal" 7 } } (entry order not guaranteed)
Pratique quand tu as assemblé ou transformé une liste de paires et que tu veux la replier dans une table de hachage pour retrouver des entrées par clé.
Tu es le commissaire de bord du navire, chargé de gérer l'inventaire du garde-manger. L'inventaire est une table de hachage où chaque clé est le nom d'un objet et où la valeur correspond à la quantité en stock.
Définis create-inventory de sorte qu'elle prenne une séquence de noms d'objets et renvoie une table de hachage qui associe chaque nom unique à son nombre d'occurrences.
{ "coal" "wood" "wood" "diamond" "diamond" "diamond" } create-inventory .
! => H{ { "coal" 1 } { "wood" 2 } { "diamond" 3 } }
Définis add-items de sorte qu'elle prenne un inventaire et une séquence d'objets et renvoie un nouvel inventaire dont les quantités ont été incrémentées pour chaque objet listé. L'inventaire d'origine ne doit pas être modifié.
H{ { "coal" 1 } } { "wood" "iron" "coal" "wood" } add-items .
! => H{ { "coal" 2 } { "wood" 2 } { "iron" 1 } }
Définis decrement-items de sorte qu'elle prenne un inventaire et une séquence d'objets et renvoie un nouvel inventaire dont les quantités ont été diminuées de un pour chaque objet listé. Les quantités ne doivent jamais descendre en dessous de zéro, et les objets qui ne sont pas déjà dans l'inventaire doivent être ignorés (aucune entrée négative n'est insérée).
H{ { "coal" 3 } { "diamond" 1 } { "iron" 5 } }
{ "diamond" "coal" "iron" "iron" } decrement-items .
! => H{ { "coal" 2 } { "diamond" 0 } { "iron" 3 } }
Définis remove-item de sorte qu'elle prenne un inventaire et un objet et renvoie un nouvel inventaire dans lequel cet objet a été supprimé. Si l'objet n'est pas présent, renvoie une copie inchangée.
H{ { "coal" 2 } { "wood" 1 } { "diamond" 2 } } "coal" remove-item .
! => H{ { "wood" 1 } { "diamond" 2 } }
Définis list-inventory de sorte qu'elle prenne un inventaire et renvoie un tableau de paires { name quantity } ne contenant que les objets dont la quantité est supérieure à zéro, trié par ordre alphabétique du nom.
H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
Inscris-toi sur Exercism pour apprendre et maîtriser Factor avec 47 concepts163 exercices, et un vrai mentorat humain, le tout gratuitement.