笨辦法學 Python · 續 練習 17：字典

練習 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

  對資料結構有什麼影響？

破壞它

你的大腦可能當機了，要休息一下，然後嘗試破壞這個代碼。這個實作很容易被資料淹沒和壓倒。奇怪的邊界情況如何呢？你可以将任何東西添加為一個鍵，或者隻是字元串？會造成什麼問題？最後，你是否可以對代碼暗中耍一些花招，使其看起來像是正常工作，但實際上是以一些機智的方式來破壞它？