练习 17：字典

原文：Exercise 17: Dictionary

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

你应该熟悉 Python 的dict类。无论什么时候，你编写这样的代码：

cars = {'Toyota': 4, 'BMW': 20, 'Audi': 10}

你在使用字典，将车的品牌（“丰田”，“宝马”，“奥迪”）和你有的数量（4，20，10）关联起来。现在使用这种数据结构应该是你的第二本能，你可能甚至不考虑它是如何工作的。在本练习中，你将通过从已经创建的数据结构，实现自己的Dictionary来了解dict的工作原理。你在本练习中的目标是，根据我在这里写的代码实现自己的Dictionary版本。

挑战性练习

在本练习中，你将完全记录并理解我编写的一段代码，然后尽可能地，根据记忆编写自己的版本。本练习的目的是，学习剖析和理解复杂的代码。能够内在化或记忆，如何创建一个简单的数据结构（如字典）是很重要的性。我发现，学习剖析和理解一段代码的最好方法是，根据自己的学习和记忆来重新实现它。

将其看做一个“原件”类。原件来自绘画，其中你绘制一幅由他人创作的画，优于创作它的副本。这样做会教你如何绘画并且提高你的技能。代码和绘画是相似的，因为所有的信息都为复制准备好了，所以你可以通过复制他们的工作，轻松地向别人学习。

制作一份“代码大师的副本”

要创建一份“代码大师副本”，你将遵循这个的流程，我称之为 CASMIR 流程：

• 复制代码，使其正常工作。你的副本应该完全一样。这有助于你了解它，并强制你仔细研究它。
• 使用注释来标注代码，并为所有代码写一个分析，确保你了解每一行以及它的作用。这可能涉及到你编写的其他代码，来将整个概念结合在一起。
• 使用简洁的说明，为这个代码的工作原理总结一般结构。这是函数列表和每个函数的作用。
• 记住这个算法和关键代码段的简洁描述。
• 根据记忆实现可以实现的东西，当你用尽细节时，回顾你的笔记和原始代码来记住更多内容。
• 当你需要从你的记忆中复制的时候，重复此过程多次。你的记忆中的副本并不必须是完全一样的，但应接近，并通过你创建的相同测试。

这样做将使你深入了解数据结构的工作原理，但更为重要的是，帮助你内在化和回忆此数据结构。你终将能够理解该概念，并在需要创建数据结构时实现数据结构。这也是训练你的大脑，在未来记住其他的数据结构和算法。

警告

我要做的唯一的警告是，这是一个很简单，愚蠢，缓慢的Dictionary实现。你真的复制了一个简单愚蠢的Dictionary，它具有所有的基本元素和作用，但需要大量改进来用于生产。当我们到达练习 19 并研究性能调整时，会进行这些改进。现在，只需实现这个简单的版本，就可以了解数据结构的基础知识。

复制代码

首先我们查看Dictionary的代码，你需要复制它：

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，你可以键入此代码并使其正常工作。记住，在开始标注之前，它必须是完美的副本。你可以做的最糟糕的事情，是标注我的代码的破损或不正确的副本。

为了帮助你获得正确的代码，我写了一个快速和简陋的小型测试脚本：

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对数据结构有什么影响？

破坏它

你的大脑可能宕机了，要休息一下，然后尝试破坏这个代码。这个实现很容易被数据淹没和压倒。奇怪的边界情况如何呢？你可以将任何东西添加为一个键，或者只是字符串？会造成什么问题？最后，你是否可以对代码暗中耍一些花招，使其看起来像是正常工作，但实际上是以一些机智的方式来破坏它？