第 14 课作业

为下面的作业问题实践这些思想，你首先应该

(load "~cs61as/lib/concurrency.scm")

练习 1

Abelson 和 Sussman，练习 3.38、3.39、3.40、3.41、3.42、3.44、3.46、3.48。

练习 2：链式 MapReduce

编写函数 real-most-frequent，它接收键值对表，其中键是文件名，值是该文件中的行（就像我们的 all-songs 例子）。我们的输出又是单个键值对的表。你可以重用本课中目前为止定义的任何函数。

>(real-most-frequent all-songs)
((i . 4))

练习 3：用流实现 MapReduce

我们目前的 mapreduce 处理的是表。现实中的 mapreduce 处理的是非常庞大的数据集：大到表根本装不下。一种解决方法是让 mapreduce 处理流（stream）而不是表。你可以从这里找到我们处理流的 mapreduce 版本，或者它在 “~cs61as/lib/mapreduce/streammapreduce.scm”。

有什么变化？我们的 map、sort-into-buckets 和 filter 现在处理流了。作为用户，你需要提供什么？mapper 和 reducer，就像你之前做的那样。mapper 和 reducer 有什么变化？没有。mapper 和 reducer 的行为不变。你可以加载文件并尝试 (mapreduce mapper reducer 0 all-songs)，其中 mapper 和 reducer 是你在课中定义的那些。它们的工作方式完全相同。唯一的区别是：如果 all-songs 很大，我们之前的版本会直接崩溃，而我们的流版本仍然能够处理它。

练习 4：你想成为宝可梦大师吗？

你可以访问包含全部 744 只宝可梦（Pokemon）数据的流，在这里和 “~cs61as/lib/mapreduce/pokemon_data”。streammapreduce.scm 应该会自动加载它，并把变量 “data” 定义为你的输入。键是宝可梦的全国编号，值是一个表，包含地区编号、名字、名字（是的，它出现两次），以及它们拥有的其余类型。例如第一个元素是 (1 1 bulbasaur bulbasaur grass poison)，所以它的全国编号是 1，地区编号是 1，名字是 bulbasaur，拥有的类型是 ‘grass’ 和 ‘poison’。一只宝可梦可以有 1 种或 2 种类型。下面是只有一个类型的例子：(4 4 charmander charmander fire)。加载文件后，你可以在解释器中输入 (ss data) 查看输入。

定义 mapper、reducer 和 base-case，使得用 (mapreduce mapper reducer base-case data) 调用 mapreduce 时，返回一个键值对表，其中键是不同的类型，值表示具有该类型的宝可梦在数据集中出现的次数。最终结果应产生如下内容（顺序不限）：

((grass . 86) (dragon . 39) (normal . 99) (flying . 93) (poison . 59) (ice . 35) (fire . 58) (ghost . 37) (psychic . 77) (electric . 47) (water . 124) (fairy . 35) (bug . 70) (steel . 42) (ground . 62) (rock . 54) (fighting . 45) (dark . 44))

提交作业！

相关说明请参见这份指南。它涵盖了基本终端命令和作业提交。

提交时遇到任何问题，随时请教助教！