Parcours
/
Factor
Factor
/
Exercices
/
Le garde-manger du commissaire
Le garde-manger du commissaire

Le garde-manger du commissaire

Exercice d'apprentissage

Introduction

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.

Littéraux de tables de hachage

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.

Lecture

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

Écriture

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 compter

inc-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 } }

Itération et insertion paresseuse

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.

Applique une mise à jour de table de hachage sur une séquence de clés

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.

Construis une table de hachage à partir d'une séquence

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 } }

Clés, valeurs et paires

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 } }

Des paires à une table de hachage

>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é.

Instructions

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.

1. Construis un inventaire à partir d'une liste

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 } }

2. Ajoute d'autres objets

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 } }

3. Décrémente les quantités

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 } }

4. Supprime complètement un objet

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 } }

5. Liste les objets disponibles

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 } }
Modifie via GitHub Le lien s'ouvre dans une nouvelle fenêtre ou un nouvel onglet
Factor Exercism

Prêt à commencer Le garde-manger du commissaire ?

Inscris-toi sur Exercism pour apprendre et maîtriser Factor avec 47 concepts163 exercices, et un vrai mentorat humain, le tout gratuitement.