PTT數位生活區 / Python

[問題] 關於Dictionary

看板Python作者 (Ben)時間14年前 (2011/03/12 17:57), 編輯推噓4(4推 0噓 16→)
留言20則, 4人參與, 最新討論串1/1
大家好, 想請教各位一個問題, 由於Dictionary是Hash table, 那 keys()這個member function的time complexity不就非常大(因為他是hash table, 所以資料很散), 最近需要處理大量資料所以有這個疑惑. 感謝大家解答！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.5.201
→
03/12 19:48, , 1F
是的，所以一般直接用 for k in dct:
03/12 19:48, 1F
→
03/12 22:05, , 2F
keys()不就回傳所有的key而已嗎 應該O(1)吧
03/12 22:05, 2F
→
03/12 22:15, , 3F
資料很散跟複雜度大哪有關係...
03/12 22:15, 3F
→
03/12 22:19, , 4F
我的意思是不太清楚他是如何得知Hash table內哪些位址存
03/12 22:19, 4F
→
03/12 22:19, , 5F
了資料? 因為他分配位址的時候是利用hash function指定的
03/12 22:19, 5F
→
03/12 22:20, , 6F
這樣的話他要找哪些位址有存資料的話, 照理講應該掃遍所
03/12 22:20, 6F
→
03/12 22:21, , 7F
有空間才能確定? 就算是用tree搜尋也要log(n)
03/12 22:21, 7F
推
03/12 22:26, , 8F
對喔 那應該是 我原本想每次add用list記下 但忘了有del
03/12 22:26, 8F
→
03/12 22:29, , 9F
orz 我搞錯了 就算只有add 也不行 冏
03/12 22:29, 9F
推
03/12 22:41, , 10F
03/12 22:41, 10F
→
03/12 22:42, , 11F
果然O(n) 不過我上面講錯 沒del是可以O(1) 不過不重要..
03/12 22:42, 11F
→
03/12 22:45, , 12F
感謝A大熱心提供資料!! 不過有點不清楚keys()有沒有優化
03/12 22:45, 12F
→
03/12 22:46, , 13F
過, 不知道去哪裡查他的implement方式？
03/12 22:46, 13F
推
03/12 22:49, , 14F
等等 它的O(n)有特別注明在Note 不是指hash後table大小
03/12 22:49, 14F
→
03/12 22:50, , 15F
implement我也不知道 大概看source code吧
03/12 22:50, 15F
推
03/13 01:01, , 16F
剛看了一下source code 有個 dictobject.c
03/13 01:01, 16F
→
03/13 01:02, , 17F
裡面寫了很多註解 可以參考看看 我大概看到兩個有趣的
03/13 01:02, 17F
→
03/13 01:02, , 18F
1. 連續的整數或字串 hash 也是非常連續的
03/13 01:02, 18F
→
03/13 01:04, , 19F
2. 它的表大小會動態增減 所以若add的不多 表就較小
03/13 01:04, 19F
→
03/13 23:41, , 20F
謝謝A大, 裡面寫得蠻清楚的！
03/13 23:41, 20F
‣ 更多 bin90909 的文章
文章代碼(AID): #1DUqEAjW (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 bin90909 的文章
文章代碼(AID): #1DUqEAjW (Python)