轨道
/
Factor
Factor
/
练习
/
事务长的储藏室
事务长的储藏室

事务长的储藏室

学习练习

简介

Factor 中的哈希表是关联数组,即由key/value键值对组成的集合,查找复杂度为 O(1)。它们属于更庞大的 assocs家族。

哈希表字面量

H{ { "coal" 1 } { "wood" 2 } } .

H{ }是空哈希表。哈希表是可变的,会随着你添加和删除键而增长或缩小。如果你不想改动原来的哈希表,先clone一下。打印哈希表会显示它的各个条目,但顺序与插入顺序无关:哈希表是无序的。

读取

at(位于 assocs)读取一个值,如果键不存在则返回f:

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添加或覆盖;delete-at删除;change-at对当前值运行一个 quotation。这三个都会修改原哈希表:

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,计数快捷方式

inc-at(同样位于 assocs)会把某个键的现有值加 1,键不存在时则以 1 插入。非常适合用来计数:

inc-at ( key assoc -- )
H{ } clone "coal" over inc-at .
! => H{ { "coal" 1 } }

迭代与惰性插入

assoc-each遍历每一个( key value -- )键值对;cache返回某个键对应的值,若该键不存在,则用传入的 quotation 计算一次。

assoc-each ( assoc quot: ( key value -- ) -- )
cache      ( key assoc quot: ( key -- value ) -- value )

cache用一个词就实现了“查找或创建”模式,当你从一连串键构建哈希表、又不想在每个调用点都处理条目缺失的情况时,它非常方便。

对一串键批量更新哈希表

当输入是一串键,而你想为每个键更新一次哈希表时,用each遍历这个序列,并使用 fried quotation '[ _ … ](来自 fry)把哈希表烘焙进循环体。例如,删除一组键:

{ "wood" "iron" } H{ { "coal" 5 } { "wood" 3 } { "iron" 2 } } clone
[ '[ _ delete-at ] each ] keep .
! => H{ { "coal" 5 } }

'[ _ delete-at ]会捕获栈中位于它上方的哈希表,这样每次迭代时each只需提供键即可。keep在运行 quotation 的同时保留哈希表,供最后的.使用。

从序列构建哈希表

map>assoc(位于 assocs)把一个 quotation 映射到序列上,并将( elt -- key value )的结果收集成一个 assoc,其类型与 exemplar 相同:

map>assoc ( seq quot: ( elt -- key value ) exemplar -- assoc )
{ "wood" } [ dup length ] H{ } map>assoc .
! => H{ { "wood" 4 } }

键、值与键值对

keys和values(位于 assocs)只返回键或只返回值;>alist返回{ 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和values是对齐的:某个位置上的值属于同一位置上的键。

sort-keys(位于 sorting)返回按键排序后的{ key value }键值对:

H{ { "wood" 11 } { "coal" 7 } } sort-keys .
! => { { "coal" 7 } { "wood" 11 } }

从键值对回到哈希表

>hashtable(位于 hashtables)是>alist的逆操作:它把任意 assoc(最常见的是由{ key value }键值对组成的 alist)转换成支持 O(1) 查找的哈希表。

>hashtable ( assoc -- hashtable )
{ { "coal" 7 } { "wood" 11 } } >hashtable .
! => H{ { "wood" 11 } { "coal" 7 } }   (entry order not guaranteed)

当你已经组装或转换了一组键值对,想把它重新折叠成哈希表以便按键查找条目时,这个函数很好用。

说明

你是船上的事务长,负责管理食品储藏室的库存。库存是一个哈希表,其中每个键是物品名称,值是该物品的库存数量。

1. 根据列表构建库存

定义create-inventory,接收一个物品名称序列,返回一个哈希表,将每个不重复的名称与其计数配对。

{ "coal" "wood" "wood" "diamond" "diamond" "diamond" } create-inventory .
! => H{ { "coal" 1 } { "wood" 2 } { "diamond" 3 } }

2. 添加更多物品

定义add-items,接收一个库存和一个物品序列,返回一个新的库存,其中每个列出的物品的计数都加了一。原有的库存不应被修改。

H{ { "coal" 1 } } { "wood" "iron" "coal" "wood" } add-items .
! => H{ { "coal" 2 } { "wood" 2 } { "iron" 1 } }

3. 减少计数

定义decrement-items,接收一个库存和一个物品序列,返回一个新的库存,其中每个列出的物品的计数都减了一。计数绝不能降到零以下,库存中原本没有的物品应被略过(不会插入负数条目)。

H{ { "coal" 3 } { "diamond" 1 } { "iron" 5 } }
{ "diamond" "coal" "iron" "iron" } decrement-items .
! => H{ { "coal" 2 } { "diamond" 0 } { "iron" 3 } }

4. 完全移除一个物品

定义remove-item,接收一个库存和一个物品,返回一个移除了该物品的新库存。如果该物品不存在,返回一个未改动的副本。

H{ { "coal" 2 } { "wood" 1 } { "diamond" 2 } } "coal" remove-item .
! => H{ { "wood" 1 } { "diamond" 2 } }

5. 列出可用的物品

定义list-inventory,接收一个库存,返回一个由{ name quantity }对组成的数组,其中只包含数量大于零的物品,并按名称的字母顺序排序。

H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
通过 GitHub 编辑 链接将在新窗口或新标签页中打开
Factor Exercism

准备好开始 事务长的储藏室 了吗?

注册 Exercism,借助 47 个概念163 个练习 和真人导师指导,学习并掌握 Factor,全部免费。