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