首頁猿問實現嵌套字典的最佳方法是什么？

實現嵌套字典的最佳方法是什么？

Python 算法與數據結構

慕娘9325324 2019-06-14 16:14:26

實現嵌套字典的最佳方法是什么？我有一個數據結構，實質上相當于一個嵌套字典。假設它看起來是這樣的：{'new jersey': {'mercer county': {'plumbers': 3, 'programmers': 81}, 'middlesex county': {'programmers': 81, 'salesmen': 62}}, 'new york': {'queens county': {'plumbers': 9, 'salesmen': 36}}}現在，維護和創建它是非常痛苦的；每次我有一個新的州/縣/專業時，我都必須通過討厭的嘗試/捕捉塊創建底層字典。此外，如果我想遍歷所有的值，我必須創建惱人的嵌套迭代器。我還可以使用元組作為鍵，如下所示：{('new jersey', 'mercer county', 'plumbers'): 3, ('new jersey', 'mercer county', 'programmers'): 81, ('new jersey', 'middlesex county', 'programmers'): 81, ('new jersey', 'middlesex county', 'salesmen'): 62, ('new york', 'queens county', 'plumbers'): 9, ('new york', 'queens county', 'salesmen'): 36}這使得迭代這些值變得非常簡單和自然，但是進行聚合和查看字典的子集(例如，如果我只想逐州進行)在語法上是比較痛苦的?；旧希袝r我想把嵌套字典看作是一個平面字典，有時我想把它看作一個復雜的層次結構。我可以在一個類中完成這一切，但似乎已經有人這樣做了?；蛘?，似乎有一些非常優雅的句法結構來做到這一點。我怎么能做得更好？增編：我知道setdefault()但它并沒有提供清晰的語法。另外，您創建的每個子字典都需要有setdefault()手動設置。

查看完整描述

3 回答

撒科打諢

TA貢獻1934條經驗獲得超2個贊

在Python中實現嵌套字典的最佳方法是什么？

實施__missing__在.上dict類來設置和返回一個新實例。

這種方法是可用的。(并記錄在案)自從Python2.5之后，和(對我來說特別有價值)很漂亮的指紋就像個普通的白癡，而不是丑陋的打印一個自動形象的默認：

class Vividict(dict):
    def __missing__(self, key):
        value = self[key] = type(self)() # retain local pointer to value
        return value                     # faster to return than dict lookup

(注self[key]是在任務的左邊，所以這里沒有遞歸。)

說你有一些數據：

data = {('new jersey', 'mercer county', 'plumbers'): 3,
        ('new jersey', 'mercer county', 'programmers'): 81,
        ('new jersey', 'middlesex county', 'programmers'): 81,
        ('new jersey', 'middlesex county', 'salesmen'): 62,
        ('new york', 'queens county', 'plumbers'): 9,
        ('new york', 'queens county', 'salesmen'): 36}

以下是我們的使用代碼：

vividict = Vividict()for (state, county, occupation), number in data.items():
    vividict[state][county][occupation] = number

現在：

>>> import pprint>>> pprint.pprint(vividict, width=40){'new jersey': {'mercer county': {'plumbers': 3,
                                  'programmers': 81},
                'middlesex county': {'programmers': 81,
                                     'salesmen': 62}},
 'new york': {'queens county': {'plumbers': 9,
                                'salesmen': 36}}}

批評

對這類容器的批評是，如果用戶拼錯了密鑰，我們的代碼可能會悄然失敗：

>>> vividict['new york']['queens counyt']{}

此外，我們的數據中還有一個拼寫錯誤的縣：

>>> pprint.pprint(vividict, width=40){'new jersey': {'mercer county': {'plumbers': 3,
                                  'programmers': 81},
                'middlesex county': {'programmers': 81,
                                     'salesmen': 62}},
 'new york': {'queens county': {'plumbers': 9,
                                'salesmen': 36},
              'queens counyt': {}}}

說明：

我們只是提供我們類的另一個嵌套實例Vividict無論何時訪問密鑰，但缺少密鑰。(返回值賦值很有用，因為它避免了我們在DECT上額外調用getter，而且不幸的是，我們不能在設置它時返回它。)

注意，這些是與最不正確的答案相同的語義，但在代碼-nosklo實現的一半行中：

class AutoVivification(dict):
    """Implementation of perl's autovivification feature."""
    def __getitem__(self, item):
        try:
            return dict.__getitem__(self, item)
        except KeyError:
            value = self[item] = type(self)()
            return value

示范使用

下面只是一個示例，說明如何輕松地使用這個dict創建嵌套的dict結構。這可以快速地創建一個層次化的樹結構，就像您想要的那樣。

import pprintclass Vividict(dict):
    def __missing__(self, key):
        value = self[key] = type(self)()
        return value

d = Vividict()d['foo']['bar']d['foo']['baz']d['fizz']['buzz']d['primary']['secondary']['tertiary']['quaternary']pprint.pprint(d)

產出：

{'fizz': {'buzz': {}},
 'foo': {'bar': {}, 'baz': {}},
 'primary': {'secondary': {'tertiary': {'quaternary': {}}}}}

正如最后一行所示，它打印得很漂亮，便于手工檢查。但是如果您想要直觀地檢查您的數據，請執行__missing__要將其類的新實例設置為鍵并返回，這是一個更好的解決方案。

與之相反的其他備選辦法：

`dict.setdefault`

雖然提問者認為這是不干凈的，但我發現這比Vividict我自己。

d = {} # or dict()for (state, county, occupation), number in data.items():
    d.setdefault(state, {}).setdefault(county, {})[occupation] = number

現在：

>>> pprint.pprint(d, width=40){'new jersey': {'mercer county': {'plumbers': 3,
                                  'programmers': 81},
                'middlesex county': {'programmers': 81,
                                     'salesmen': 62}},
 'new york': {'queens county': {'plumbers': 9,
                                'salesmen': 36}}}

拼寫錯誤會引起噪音，而且不會使我們的數據充斥著糟糕的信息：

>>> d['new york']['queens counyt']Traceback (most recent call last):
  File "<stdin>", line 1, in <module>KeyError: 'queens counyt'

此外，我認為setDefault在循環中使用時效果很好，而且您也不知道要為鍵獲取什么，但是重復使用會帶來很大的負擔，而且我認為沒有人會想要保持以下內容：

d = dict()d.setdefault('foo', {}).setdefault('bar', {})d.setdefault('foo', {}).setdefault('baz', {})d.setdefault('fizz', {}).setdefault
('buzz', {})d.setdefault('primary', {}).setdefault('secondary', {}).setdefault('tertiary', {}).setdefault('quaternary', {})

另一個批評是setdefault需要一個新實例，不管是否使用它。但是，Python(或至少CPython)在處理未使用和未引用的新實例方面相當聰明，例如，它重用內存中的位置：

>>> id({}), id({}), id({})(523575344, 523575344, 523575344)

一個自動生動的默認設置

這是一個整潔的實現，在沒有檢查數據的腳本中使用與實現相同的功能__missing__:

from collections import defaultdictdef vivdict():
    return defaultdict(vivdict)

但是，如果您需要檢查您的數據，使用相同方式填充數據的自動生動的defaultdict的結果如下所示：

>>> d = vivdict(); d['foo']['bar']; d['foo']['baz']; d['fizz']['buzz']; d['primary']['secondary']['tertiary']['quaternary']; import pprint;
 >>> pprint.pprint(d)defaultdict(<function vivdict at 0x17B01870>, {'foo': defaultdict(<function vivdict 
at 0x17B01870>, {'baz': defaultdict(<function vivdict at 0x17B01870>, {}), 'bar': defaultdict(<function vivdict at 0x17B01870>, {})}), 'pr
mary': defaultdict(<function 
vivdict at 0x17B01870>, {'secondary': defaultdict(<function vivdict at 0x17B01870>, {'tertiary': defaultdict(<function vivdict at 0x17B01870
>, {'quaternary': defaultdict(<function vivdict at 0x17B01870>, {})})})}), 'fizz': defaultdict(<function vivdict at 
0x17B01870>, {'buzz': defaultdict(<function vivdict at 0x17B01870>, {})})})

這個輸出是相當不雅致的，結果是非常不可讀的。通常給出的解決方案是遞歸地將其轉換為DECT，以便進行手動檢查。這個非平凡的解決方案是留給讀者的練習。

性能

最后，讓我們看看性能。我正在減去實例化的成本。

>>> import timeit>>> min(timeit.repeat(lambda: {}.setdefault('foo', {}))) - min(timeit.repeat(lambda: {}))0.13612580299377441>>>
 min(timeit.repeat(lambda: vivdict()['foo'])) - min(timeit.repeat(lambda: vivdict()))0.2936999797821045>>> min(timeit.repeat(lambda:
  Vividict()['foo'])) - min(timeit.repeat(lambda: Vividict()))0.5354437828063965>>> min(timeit.repeat(lambda: AutoVivification()['foo']))
   - min(timeit.repeat(lambda: AutoVivification()))2.138362169265747

根據業績，dict.setdefault效果最好。在您關心執行速度的情況下，我強烈推薦它用于生產代碼。

如果您需要用于交互使用(可能在IPython筆記本中)，那么性能并不重要-在這種情況下，我將使用Vividict來獲取輸出的可讀性。與自動識別對象(該對象使用__getitem__而不是__missing__，這是為了這個目的而做的)它要好得多。

結語

實施__missing__子類dict設置和返回一個新實例比其他方法稍微困難一些，但是它的好處是

易實例化
易數據總體
容易查看數據

因為它比修改更不復雜和更有效。__getitem__，它應該比那種方法更好。

然而，它也有缺點：

糟糕的查找將悄悄地失敗。
糟糕的查找將留在字典中。

所以我個人更喜歡setdefault其他的解決方案，在我需要這種行為的每一種情況下都有。

反對回復 2019-06-14

拉丁的傳說

TA貢獻1789條經驗獲得超8個贊

class AutoVivification(dict):
    """Implementation of perl's autovivification feature."""
    def __getitem__(self, item):
        try:
            return dict.__getitem__(self, item)
        except KeyError:
            value = self[item] = type(self)()
            return value

測試：

a = AutoVivification()a[1][2][3] = 4a[1][3][3] = 5a[1][2]['test'] = 6print a

產出：

{1: {2: {'test': 6, 3: 4}, 3: {3: 5}}}

反對回復 2019-06-14

慕絲7291255

TA貢獻1859條經驗獲得超6個贊

就因為我還沒見過這么小的，這里有一個你喜歡嵌套的小塊，沒有汗水：

# yo dawg, i heard you liked dicts                                                                      def yodict():
    return defaultdict(yodict)

反對回復 2019-06-14

3 回答
0 關注
1499 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

實現嵌套字典的最佳方法是什么？

實現嵌套字典的最佳方法是什么？

3 回答

在Python中實現嵌套字典的最佳方法是什么？

批評

說明：

示范使用

與之相反的其他備選辦法：

dict.setdefault

一個自動生動的默認設置

性能

結語

添加回答

實現嵌套字典的最佳方法是什么？

在Python中實現嵌套字典的最佳方法是什么？

`dict.setdefault`