# 練習 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`對數據結構有什么影響？ ## 破壞它 你的大腦可能宕機了，要休息一下，然后嘗試破壞這個代碼。這個實現很容易被數據淹沒和壓倒。奇怪的邊界情況如何呢？你可以將任何東西添加為一個鍵，或者只是字符串？會造成什么問題？最后，你是否可以對代碼暗中耍一些花招，使其看起來像是正常工作，但實際上是以一些機智的方式來破壞它？