作者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