袜子配对 版权说明:《Bad Choices》是由Ali Almossawi著作的一套计算思维书籍,可以通过https://bookofbadchoices.com/访问本书英文版本。书中通过一系列人物的故事场景,以插画的方式展示了一个个现实生活中遇到的问题,进而引出了一些计算思维的问题,内容丰富且非常有趣。本书的目标读者是计划学习编程的儿童、学生,通过阅读本书可以开拓眼界,培养计算思维习惯。
本章背景故事(请孩子阅读,家长伴听)

有这样一位新来的保姆BM,惊奇的发现主人家有这么一大堆不同颜色、大小的袜子堆积在一起,而按照主人要求,她需要把这些袜子都分拆出来。
工作目标: 将这一堆袜子进行匹配挑出
你可以采用的方法:
方法一:拿起第一只袜子,在袜子堆里逐件查找它的配对,找到后放在一边。然后拿起第二只袜子,在堆里找它的匹配,然后是第三只,以此类推。
方法二:挑选一只袜子,放在旁边的小区域,作为未匹配袜子。随意拿起另一只袜子,如果这只与未匹配袜子中的任何一个能够匹配,则将配对的袜子放到完成区;否则,将这只袜子也添加到未匹配的袜子区,并按照一定的特征比如颜色或者大小堆在一起,以此类推;

好了,现在我们可以动手准备了,请你找到笔和纸、袜子(可选)或者其他你觉得可以替代的道具。
你可以按照上面的两种方法,先进行一些实验,看看哪种方法会更快?并思考为什么?
实验完成再接着往下看哦!
袜子配对 分析过程(请家长+孩子分段阅读思考)
人类的记忆是非常独一无二的,你有没有想过生物特征记忆对人类有多重要? 一个人靠在椅子上,手放在她的额头,闭上眼睛,想起一首诗、一个方程式或一个电话号码——这就是典型的人类。 想象一下,如果没有这种特征,就必须像痴呆症患者一样度过挣扎的一生。
对于刚刚起步的初学者,你最终将重复许多相同的工作。 就像在电影《记忆碎片》中一样,因为只能记住几分钟前发生的事情,每天早上,主角都必须再次费劲力气收集必要的信息。
接下来我们就了解一下记忆对于解决问题的速度有何益处。
一种情况是,如果这个袜子堆中袜子的数量很少,比如只有四双,那么用任何一种方法BM都会很快完成。
可是,现在想象一下BM面前摆着数百只袜子的时候:
如果她选择方法一,她一次又一次遇到同一只旧袜子的机会是相当高的,因为她从来没有把它从堆里拿出来。当她第一次遇到它时,她根本没有从中收集到任何信息。
然而,使用第二种方法时,她将未匹配袜子放在未匹配区,从而确保她只遇到一次袜子。因此,第二种方法最终会更快,因为它依赖于记忆(memory),或者叫做查找表(lookup table)或者缓存(cache),而这种方法也常被称为“用记忆换时间”。
言归正传,查找表(lookup table)通常可以被看做是一系列具有唯一标识的数组(有序的元素序列),每个标识都指向一些相关的键值,你也可以在其中查找。在这种情况下,我们的键值很可能是“颜色”。比如,当BM遇到一只红色的袜子时,她会在她未匹配袜子堆中查找“红色”,如果她找到“红色”区域,她可能会寻找其他标识,比如大小号,然后从那里找到匹配的袜子并带走。否则,她会用单独的红色袜子创建一个新的“红色”区域。
下图可以看出两种方法的在速度上的差异,横轴为袜子的数量,纵轴是消耗的时间。可以看出,随着袜子数量的增加,方法 1 明显比方法 2 耗用时间更多,也就是更慢。

除了上述两种方法以外,还有其他很多方法进行挑选,但是因为以上两种方法最具特点,所以其他方法的曲线会落在这两条曲线之间。例如使用抽屉原理(鸽巢原理),每次拿出6只袜子做匹配,这是因为人们短期记忆的能力是在6个左右为宜;
但是,另一个情况又发生了。
如果我们的袜子特征很多,比如颜色、大小、样式、材质、等等,这时候会造成我们的cache很大,而每拿到一个袜子就去比对时候要扫描整个数组,因为你这双袜子可能是在最后一个,解决这个问题的办法就是关联数组或者哈希表(hash table)。
1953 年,在 IBM 工作期间,数学家 Hans Peter Luhn 提出了一个想法,帮助缓解数组查找中固有的潜在缓慢性。它有时被称为关联数组、字典或哈希表。哈希表与数组的功能完全相同,是根据关键码值(Key value)而直接进行访问的数据结构,直观的理解,就是所有哈希表中的元素放置都是按照f(x)函数,任何一个袜子x来了,就给放到f(x)的位置,所以可以直接找到,它们被称为常数时间寻找,因为查找不再依赖于未匹配袜子堆数组的长度。
我们在这个故事中的最大收获是,我们重用信息知识,这样可以加快速度,当我们遇到大量重复事项时尤其重要。
今天学习结束了,下面一起来通过实验体会一下cache的方法吧!
袜子配对 本章延申练习(请家长+孩子共同完成)
从家里找出一副扑克牌,试试用今天学到的两个方法将对应花色的牌匹配出来,比如10的黑桃、红心、方块、梅花四张为一套,并记录你所耗得时间,比较和体会这一现象。