私信发送成功
Watch Star Fork

龙哥盟飞龙 / lmpythw-zh

克隆/下载
一键复制 编辑 原始数据 按行查看 历史
ex17.md 14.83 KB wizardforcel 提交于 2017-08-08 10:54 . ex18.

练习 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_slotget_bucket。你不是以摄影方式记住每个字符;而是记住所有关键概念并使用它们。

重复

这个练习最重要的部分是,重复几次这个流程,使其没有错误,才能使其更好。你会对这本书中的其他数据结构这样做,所以你会得到大量的练习。如果你必须回去记忆 100 次才行,也是可以的。最终你只需要做 50 遍,然后下一次只有 10 遍,然后最终你将能够轻易从记忆中实现一个Dictionary。尽管继续尝试,并尝试像冥想那样接近它,所以你这样做的时候可以放松。

深入学习

  • 我的测试非常有限。写一个更广泛的测试。
  • 练习 16 的排序算法如何有助于这个数据结构?
  • 当你将键和值随机化,用于这个数据结构时,会发生什么?排序算法有帮助吗?
  • num_buckets对数据结构有什么影响?

破坏它

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

评论 ( 0 )

你可以在登录后,对此项目发表评论

4_float_left_people 4_float_left_close