# 练习 17：字典 > 原文：[Exercise 17: Dictionary](https://learncodethehardway.org/more-python-book/ex17.html) > 译者：[飞龙](https://github.com/wizardforcel) > 协议：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻译](https://translate.google.cn/) 你应该熟悉 Python 的`dict`类。无论什么时候，你编写这样的代码： ```py cars = {'Toyota': 4, 'BMW': 20, 'Audi': 10} ``` 你在使用字典，将车的品牌（“丰田”，“宝马”，“奥迪”）和你有的数量（4，20，10）关联起来。现在使用这种数据结构应该是你的第二本能，你可能甚至不考虑它是如何工作的。在本练习中，你将通过从已经创建的数据结构，实现自己的`Dictionary`来了解`dict`的工作原理。你在本练习中的目标是，根据我在这里写的代码实现自己的`Dictionary`版本。 ## 挑战性练习 在本练习中，你将完全记录并理解我编写的一段代码，然后尽可能地，根据记忆编写自己的版本。本练习的目的是，学习剖析和理解复杂的代码。能够内在化或记忆，如何创建一个简单的数据结构（如字典）是很重要的性。我发现，学习剖析和理解一段代码的最好方法是，根据自己的学习和记忆来重新实现它。 将其看做一个“原件”类。原件来自绘画，其中你绘制一幅由他人创作的画，优于创作它的副本。这样做会教你如何绘画并且提高你的技能。代码和绘画是相似的，因为所有的信息都为复制准备好了，所以你可以通过复制他们的工作，轻松地向别人学习。 ## 制作一份“代码大师的副本” 要创建一份“代码大师副本”，你将遵循这个的流程，我称之为 CASMIR 流程： + 复制代码，使其正常工作。你的副本应该完全一样。这有助于你了解它，并强制你仔细研究它。 + 使用注释来标注代码，并为所有代码写一个分析，确保你了解每一行以及它的作用。这可能涉及到你编写的其他代码，来将整个概念结合在一起。 + 使用简洁的说明，为这个代码的工作原理总结一般结构。这是函数列表和每个函数的作用。 + 记住这个算法和关键代码段的简洁描述。 + 根据记忆实现可以实现的东西，当你用尽细节时，回顾你的笔记和原始代码来记住更多内容。 + 当你需要从你的记忆中复制的时候，重复此过程多次。你的记忆中的副本并不必须是完全一样的，但应接近，并通过你创建的相同测试。 这样做将使你深入了解数据结构的工作原理，但更为重要的是，帮助你内在化和回忆此数据结构。你终将能够理解该概念，并在需要创建数据结构时实现数据结构。这也是训练你的大脑，在未来记住其他的数据结构和算法。 > 警告 > 我要做的唯一的警告是，这是一个很简单，愚蠢，缓慢的`Dictionary`实现。你真的复制了一个简单愚蠢的`Dictionary `，它具有所有的基本元素和作用，但需要大量改进来用于生产。当我们到达练习 19 并研究性能调整时，会进行这些改进。现在，只需实现这个简单的版本，就可以了解数据结构的基础知识。 ## 复制代码 首先我们查看`Dictionary`的代码，你需要复制它： ```py from dllist import DoubleLinkedList class Dictionary(object): def __init__(self, num_buckets=256): """Initializes a Map with the given number of buckets.""" self.map = DoubleLinkedList() for i in range(0, num_buckets): self.map.push(DoubleLinkedList()) def hash_key(self, key): """Given a key this will create a number and then convert it to an index for the aMap's buckets.""" return hash(key) % self.map.count() def get_bucket(self, key): """Given a key, find the bucket where it would go.""" bucket_id = self.hash_key(key) return self.map.get(bucket_id) def get_slot(self, key, default=None): """ Returns either the bucket and node for a slot, or None, None """ bucket = self.get_bucket(key) if bucket: node = bucket.begin i = 0 while node: if key == node.value[0]: return bucket, node else: node = node.next i += 1 # fall through for both if and while above return bucket, None def get(self, key, default=None): """Gets the value in a bucket for the given key, or the default.""" bucket, node = self.get_slot(key, default=default) return node and node.value[1] or node def set(self, key, value): """Sets the key to the value, replacing any existing value.""" bucket, slot = self.get_slot(key) if slot: # the key exists, replace it slot.value = (key, value) else: # the key does not, append to create it bucket.push((key, value)) def delete(self, key): """Deletes the given key from the Map.""" bucket = self.get_bucket(key) node = bucket.begin while node: k, v = node.value if key == k: bucket.detach_node(node) break def list(self): """Prints out what's in the Map.""" bucket_node = self.map.begin while bucket_node: slot_node = bucket_node.value.begin while slot_node: print(slot_node.value) slot_node = slot_node.next bucket_node = bucket_node.next ``` 该代码使用你现有的`DoubleLinkedList`代码来实现`dict`数据结构。如果你不完全了解`DoubleLinkedList`，那么你应该尝试使用代码复制过程，让我们更好地理解它。一旦你确定你了解`DoubleLinkedList`，你可以键入此代码并使其正常工作。记住，在开始标注之前，它必须是完美的副本。你可以做的最糟糕的事情，是标注我的代码的破损或不正确的副本。 为了帮助你获得正确的代码，我写了一个快速和简陋的小型测试脚本： ```py from dictionary import Dictionary # create a mapping of state to abbreviation states = Dictionary() states.set('Oregon', 'OR') states.set('Florida', 'FL') states.set('California', 'CA') states.set('New York', 'NY') states.set('Michigan', 'MI') # create a basic set of states and some cities in them cities = Dictionary() cities.set('CA', 'San Francisco') cities.set('MI', 'Detroit') cities.set('FL', 'Jacksonville') # add some more cities cities.set('NY', 'New York') cities.set('OR', 'Portland') # print(out some cities print('-' * 10) print("NY State has: %s" % cities.get('NY')) print("OR State has: %s" % cities.get('OR')) # print(some states print('-' * 10) print("Michigan's abbreviation is: %s" % states.get('Michigan')) print("Florida's abbreviation is: %s" % states.get('Florida')) # do it by using the state then cities dict print('-' * 10) print("Michigan has: %s" % cities.get(states.get('Michigan'))) print("Florida has: %s" % cities.get(states.get('Florida'))) # print(every state abbreviation print('-' * 10) states.list() # print(every city in state print('-' * 10) cities.list() print('-' * 10) state = states.get('Texas') if not state: print("Sorry, no Texas.") # default values using ||= with the nil result # can you do this on one line? city = cities.get('TX', 'Does Not Exist') print("The city for the state 'TX' is: %s" % city) ``` 我希望你也可以正确地键入这个代码，但是当你进入大师副本的下一个阶段时，你会把它变成一个正式的自动测试，你可以运行`pytest`。现在，只要让这个脚本工作，就可以让`Dictionary`类工作，之后你可以在下一个阶段清理它。 ## 标注代码 确保我的代码的副本完全一样，并通过测试脚本。然后，你可以开始标注代码，并研究每一行来了解其作用。一个非常好的方式是，编写一个“正式”的自动化测试，并在你工作时标注代码。获取`dictionary_test.py`脚本，并将每个部分转换成一个小型测试函数，然后标注`Dictionary`类。 例如，`test_dictionary.py`中的第一部分测试创建一个字典，并执行一系列`Dictionary.set`调用。我会把它转换成一个`test_set`函数，然后在`dictionary.py`文件中标注`Dictionary.set`函数。当你标注`Dictionary.set`函数时，你必须潜入到`Dictionary.get_slot`函数中，然后是`Dictionary.get_bucket`函数，最后是`Dictionary.hash_key`。这迫使你通过一个测试和有组织的方式，来标注和了解`Dictionary`类的大段代码。 ## 总结数据结构 你现在可以总结你在`dictionary.py`中，通过标注代码所学到的内容，并将`dictionary_test.py`文件重写为真正的`pytest`自动测试。你的摘要应该是数据结构的清晰和细微描述。如果你可以把它写在一张纸上，那么你做得很好。并不是所有的数据结构都可以简明扼要地总结出来，但是保持摘要简洁将有助于你记住它。你可以使用图表，图纸，单词，或你能够记住的任何内容。 此摘要的目的是为你提供一组快速注解，你可以“挂载”更多的细节，当你的记忆进行到下一步的时候。摘要不一定包括所有内容，但应该包括一些细节，可以触发你对“标注”阶段的代码的记忆，从而触发你对“复制”阶段的记忆。这被称为“分块”，你可以将更详细的记忆和信息附加到信息的细微碎片。在撰写摘要时记住这一点。少即是多，但太少没有用。 ## 记忆摘要 你可以用任何方式记住摘要和带标注的代码，但我将给出一个基本的记忆过程，你可以使用它。老实说，记住复杂的东西是每个人的不断尝试和犯错的过程，但有些技巧有帮助： + 确保你有一个纸质的笔记本，以及摘要和代码的打印。 + 花3分钟，只需阅读摘要并尝试记住它。静静地看着它，大声读出来，然后闭上眼睛，重复你所读的内容，甚至尝试记住纸上的单词的“形状”。听起来很愚蠢，但相信我，它完全奏效。记住你的大脑比你想象的更好。 + 把摘要翻过来，并尝试从你记住的内容中再次写出来，当你卡住时，将其快速翻过来并查看。在你快速瞥见之后，把摘要翻过来，并尝试完成更多。 + 一旦从（大部分）记忆中写出了摘要的副本，请使用摘要，花另一个 3 分钟，试图记住带标注的代码。仅仅阅读摘要的一部分，然后再看看代码的相关部分，并尝试记住它。甚至每个函数只能花 3 分钟。 + 一旦你花时间试图记住带标注的代码，把它翻过去，使用摘要，尝试回忆你笔记本中的代码。同样，当你陷入困境时，快速把标注翻过来并查看。 + 继续这样做，直到你可以在纸上写出代码的完整副本。你纸上的代码不一定是完美的 Python 代码，但应该非常接近原始代码。 看起来这可能是无法实现，但是当你这么做时，你会感到惊讶。完成此操作后，你也会惊讶于你了解了字典的概念。这不是简单的记忆，而是建立一个概念图，当你尝试自己实现字典时，你可以实际使用它。 > 警告 > 如果你是那种担心记不住任何东西的人，那么这个练习会为你将来带来巨大的帮助。能够遵循流程来记住某些东西，有助于克服任何记忆的挫折。你并不是沉浸在“失败”中，而是可以在坚持中看到缓慢的改进。当你这样做，你会看到改善你的回忆的方式和黑魔法，并且你会做得更好。你只需要相信我，这似乎是一种缓慢的学习方式，但它比其他技术要快得多。 ## 从记忆中实现 现在是时候走到你的电脑旁边 - 把你的纸质笔记放在另一个房间或地板上 - 并根据记忆尝试你的第一个实现。你的第一次尝试可能完全是一场灾难，也可能完正确。你最可能不习惯从记忆中实现任何东西。只要放下任何你记得的东西，当你到达你的记忆的彼端，回到另一个房间，记忆更多东西。经过几次到你的记忆空间的旅行，你会进入它，记忆会更好地流出来。你完全可以再次访问你的记忆笔记。这一切都关于，试图保持代码的记忆并提高自己的技能。 我建议你首先写下你的想法，无论是测试，代码还是两者。然后使用你可以回忆的内容，来实现或回忆代码的其他部分。如果你首先坐下来并记住`test_set`函数名和几行代码，然后把它们写下来。当他们在你的头脑中，立即利用它们。一旦你完成了，尽你最大的努力，使用这个测试来记住或实现`Dictionary.set`函数。你的目标是使用任何信息来构建或者其它信息。 你也应该尝试，用你对`Dictionary `的理解来实现代码。不要简单以摄影方式来回忆每一行。这实际上是不可能的，因为没有人有摄影记忆（去查一下，没有人）。大多数人的记忆都不错，能够触发他们可以使用的概念性理解。你应该做同样的事情，并使用你的`Dictionary`的知识来创建自己的副本。在上面的示例中，你知道`Dictionary.set`以某种方式运行，你需要一种方法来获取插槽（链表节点）和桶（链表本身）...所以这意味着，你需要`get_slot`和`get_bucket`。你不是以摄影方式记住每个字符；而是记住所有关键概念并使用它们。 ## 重复 这个练习最重要的部分是，重复几次这个流程，使其没有错误，才能使其更好。你会对这本书中的其他数据结构这样做，所以你会得到大量的练习。如果你必须回去记忆 100 次才行，也是可以的。最终你只需要做 50 遍，然后下一次只有 10 遍，然后最终你将能够轻易从记忆中实现一个`Dictionary `。尽管继续尝试，并尝试像冥想那样接近它，所以你这样做的时候可以放松。 ## 深入学习 + 我的测试非常有限。写一个更广泛的测试。 + 练习 16 的排序算法如何有助于这个数据结构？ + 当你将键和值随机化，用于这个数据结构时，会发生什么？排序算法有帮助吗？ + `num_buckets`对数据结构有什么影响？ ## 破坏它 你的大脑可能宕机了，要休息一下，然后尝试破坏这个代码。这个实现很容易被数据淹没和压倒。奇怪的边界情况如何呢？你可以将任何东西添加为一个键，或者只是字符串？会造成什么问题？最后，你是否可以对代码暗中耍一些花招，使其看起来像是正常工作，但实际上是以一些机智的方式来破坏它？