我需要從 python 字典對象中檢索任意鍵。假設我有一本字典d。以下代碼的時間復雜度是多少？k = next(iter(d.keys()))我知道在 Python 3 中 d.key() 是 O(1) 時間，next() 是 O(1) 時間。iter() 會發生什么？這可以在不使用額外空間的情況下在 O(1) 時間內完成嗎？謝謝！
1 回答
牧羊人nacy
TA貢獻1862條經驗 獲得超7個贊
使用iter（或其他邏輯，例如生成器表達式，聲明委托給字典的生成器函數，使用islice等）都是某種形式的包裝器，它將.__next__()方法和一些位置簿記添加到對象的視圖中next()操作.
這些在很大程度上起作用是因為字典是可迭代的，但沒有.__next__()方法，所以iter等人。正在調用該方法，該方法返回一個具有該方法并且是dict 的視圖__iter__的可迭代對象。__next__
每個 case 只是一個 O(1) 調用的包裝器，因此一旦聲明，它們都將在 O(1) 時間內運行
https://wiki.python.org/moin/TimeComplexity
這是一個演示
首先創建一個相當大的字典（這在慢速系統上可能需要一段時間）
>>> from uuid import uuid4
>>> d = {str(uuid4()):str(uuid4()) for _ in range(1000000)}
顯示這可以直接從現有方法完成
>>> next(d.__iter__()
'1273a529-d406-4076-8acc-8993f2613ad4'
>>> type(d.__iter__())
<class 'dict_keyiterator'>
更多對象
>>> n1 = iter(d) # iter function
>>> n2 = (k for k in d) # generator expression
>>> def y(): # generator delegation
... yield from d
...
>>> import itertools
>>> i = itertools.islice(d, 1) # slice one entry from iterable
>>> type(n1)
<class 'dict_keyiterator'>
>>> type(n2)
<class 'generator'>
>>> type(y())
<class 'generator'>
>>> type(i)
<class 'itertools.islice'>
這些中的每一個都可以用來讀取第一個鍵
>>> next(n1)
'1273a529-d406-4076-8acc-8993f2613ad4'
>>> next(n2)
'1273a529-d406-4076-8acc-8993f2613ad4'
>>> next(y())
'1273a529-d406-4076-8acc-8993f2613ad4'
>>> next(i)
'1273a529-d406-4076-8acc-8993f2613ad4'
證明這些都提供了下一個方法
>>> dir(d)
['__class__', '__contains__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'clear', 'copy', 'fromkeys', 'get', 'items', 'keys', 'pop', 'popitem', 'setdefault', 'update', 'values']
>>> "__next__" in dir(d)
False
>>> "__next__" in dir(n1)
True
>>> "__next__" in dir(n2)
True
>>> "__next__" in dir(y())
True
>>> "__next__" in dir(i)
True
最后，如果需要前 N 個值（而不僅僅是第一個 from ），也可以在循環中有效地調用這些直到達到某個長度或被islicefromitertoolsnext()切片，但是當形成列表等時會產生一些進一步的開銷
>>> import itertools
>>> list(itertools.islice(d, 5))
['1273a529-d406-4076-8acc-8993f2613ad4', 'a920460d-a193-455c-979c-a91fd700f927', 'aeccb371-43d1-4690-8aaa-d6de0cbe3801', '9aaf2a96-9ef4-4610-8723-8401008e190a', 'e4b450aa-50a2-409a-a5b2-ab88285eb770']
>>> list(itertools.islice(y(), 5))
['1273a529-d406-4076-8acc-8993f2613ad4', 'a920460d-a193-455c-979c-a91fd700f927', 'aeccb371-43d1-4690-8aaa-d6de0cbe3801', '9aaf2a96-9ef4-4610-8723-8401008e190a', 'e4b450aa-50a2-409a-a5b2-ab88285eb770']
>>> list(itertools.islice(n1, 5))
['1273a529-d406-4076-8acc-8993f2613ad4', 'a920460d-a193-455c-979c-a91fd700f927', 'aeccb371-43d1-4690-8aaa-d6de0cbe3801', '9aaf2a96-9ef4-4610-8723-8401008e190a', 'e4b450aa-50a2-409a-a5b2-ab88285eb770']
>>> list(itertools.islice(n2, 5))
['1273a529-d406-4076-8acc-8993f2613ad4', 'a920460d-a193-455c-979c-a91fd700f927', 'aeccb371-43d1-4690-8aaa-d6de0cbe3801', '9aaf2a96-9ef4-4610-8723-8401008e190a', 'e4b450aa-50a2-409a-a5b2-ab88285eb770']
添加回答
舉報
0/150
提交
取消