Python fast包含方法
Python fast包含方法
提问于 2013-11-14 00:05:27
如果我有一个Python字典，搜索一个不存在的键的时间复杂度是多少？
d = {}
if key not in d:
print "Key not found!"in是否在键数组中进行线性搜索？
是否存在搜索特定字符串的数据结构的O(1)实现？有效地适用于contains()方法。
回答 3
Stack Overflow用户
回答已采纳
发布于 2013-11-14 00:08:19
它必须为字典摊销O(1)，因为最终in操作符只是执行成员身份查找，而not在这方面没有额外的开销。看看这个answer，了解关于in操作符在字典情况下的时间复杂性的更多细节。
Stack Overflow用户
发布于 2013-11-14 00:08:56
它的O(1)字典实现为哈希表和在哈希表查找
Stack Overflow用户
发布于 2013-11-14 00:19:04
字典通常是用于查找的O(1)。
有一个类返回一个常量作为它的散列是完全可以接受的，但是这会将字典查找降低为线性。
例如：
class dumbint(int):
def __hash__(self):
return 0
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(100)}' 'dumbint(-1) in d'
100000 loops, best of 3: 3.64 usec per loop
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(1000)}' 'dumbint(-1) in d'
10000 loops, best of 3: 31.7 usec per loop
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(10000)}' 'dumbint(-1) in d'
1000 loops, best of 3: 803 usec per loop字符串有一个很好的散列函数，所以您将得到O(1)查找精确匹配的结果。在键中搜索子字符串是一个更困难的问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19967004
复制相关文章
相似问题
腾讯云开发者
