作者:手机用户2502929821 | 来源:互联网 | 2022-11-20 16:53
字典和集合都在Python中实现为哈希表,插入时间和查找时间均为O(1)。我正在编写一个程序来计算字符串是否由所有唯一字符组成,并且我正在使用一个程序来跟踪到目前为止看到的所有字符。我观察到的是,如果我使用字典而不是集合,则程序的总体运行时间会更快一些。谁能解释这个原因?
使用字典的代码:
def TestUniqueCharacters(characters):
chars = {}
for character in characters:
if character not in chars:
chars[character] = 1
else:
return False
return True
for i in range(30000000):
TestUniqueCharacters("qwertyuiopasdfghjklzxcvbnm1234567890-=[];',.!@#$%^&*()")
使用一组代码
def TestUniqueCharacters(characters):
chars = set()
for character in characters:
if character not in chars:
chars.add(character)
else:
return False
return True
for i in range(30000000):
TestUniqueCharacters("qwertyuiopasdfghjklzxcvbnm1234567890-=[];',.!@#$%^&*()")
用字典执行时间
设定执行时间
1> Tim Peters..:
我不愿意在此上花费很多时间,因为dict和set的实现在Python版本中有所不同。追逐依赖于版本的小谜团并没有什么乐趣;-)
所以我只建议更改:
chars = set()
for character in characters:
if character not in chars:
chars.add(character)
至:
chars = set()
charsadd = chars.add # new line here
for character in characters:
if character not in chars:
charsadd(character) # this line is different - no method lookup now
看看您使用的是哪个版本的Python都会发生什么。
在原始语言中chars.add(...)
,每次循环时"add"
都必须在chars
对象上查找具有字符串名称的方法,并创建一个绑定的方法对象,然后使用arguments调用该方法character
。虽然这不是一笔大笔费用,但这不是免费的。在建议的重写中,该add
方法在循环外仅查找一次。
嗨,非常感谢您的建议。它确实大大减少了执行时间。集合的平均执行时间现在从我早些时候的大约2分钟20秒下降到1分钟45秒。