使用字典似乎很理想。在Python中检查重复项的最快方法是什么?
例如为:
history = {}
for i in collection:
if i not in history:
history[i] = None
# fancy computation here
将使用该组()类型是一样快; set()不需要我向散列键添加无用的None值。
使用字典似乎很理想。在Python中检查重复项的最快方法是什么?
例如为:
history = {}
for i in collection:
if i not in history:
history[i] = None
# fancy computation here
将使用该组()类型是一样快; set()不需要我向散列键添加无用的None值。
是的,你应该使用一套。
将使用该组()类型是一样快;
不,它不会一样快。这将是更快。
更新
有人已经发布的基准显示,集比字典慢。我认为这有点令人惊讶,因为它们基本上具有相同的底层实现,只是设置更简单。我想我已经找到了缓慢的原因:
def set_way():
my_set = set()
my_set_add = my_set.add # remember the method
for ele in x:
if ele not in my_set:
my_set_add(ele) # call the method directly
结果:现在
dict time : 1.896939858077399
set time : 1.8587076107880456
设置稍快,符合市场预期。
日文N3 N4 N5的速度更快,但只能勉强:
import timeit
setup = """
x = range(10000)
s = set(range(5000))
d = dict.fromkeys(range(5000))
"""
print '# set', timeit.timeit('for i in x: z = i in s', setup, number=1000)
print '# dic', timeit.timeit('for i in x: z = i in d', setup, number=1000)
# set 1.18897795677
# dic 1.1489379406
然而,除非性能绝对是至关重要的,你应该使用集可读性的原因。
当然,正如你的问题所暗示的,我们正在谈论可排序类型。不可容忍的类型,如容器,将需要其他技术。
为了完整起见,这里有不同的修饰方法基准:
import timeit
setup = """
x = range(10000)
s = set(range(5000))
d = dict.fromkeys(range(5000))
add_method = s.add
"""
print '# set-add ', timeit.timeit('for i in x: s.add(i)', setup, number=1000)
print '# set-closure ', timeit.timeit('for i in x: add_method(i)', setup, number=1000)
print '# dict [] ', timeit.timeit('for i in x: d[i]=None', setup, number=1000)
print '# d.setdefault', timeit.timeit('for i in x: d.setdefault(i)', setup, number=1000)
# set-add 1.96829080582
# set-closure 1.2261030674
# dict [] 0.982795000076
# d.setdefault 2.27355480194
dict[i]
是最快的,但这次一点也不奇怪,因为没有函数调用参与。
字典似乎更快。
import timeit
import random as rn
x = [rn.choice(xrange(10000)) for i in xrange(1000)]
def set_way():
my_set = set()
for ele in x:
if ele in my_set:
return True
else:
my_set.add(ele)
else:
return False
def dict_way():
dicto = {}
for ele in x:
if ele in dicto:
return True
else:
dicto[ele] = None
else:
return False
num = 10000
set_time = timeit.timeit(set_way, number = num)
print 'set time :', set_time
dict_time = timeit.timeit(dict_way, number = num)
print 'dict time :', dict_time
结果:
set time : 0.619757678699
dict time : 0.466664548148
设置较慢?令人惊讶...你有任何解释吗? –
我也很惊讶。也许增加设置比添加字典要慢?我很想知道自己的解释是什么。 – Akavall
+1用于发布令人惊讶的性能测量结果。请参阅我的更新答案以获得解释。 –
为什么快?检查字典中的密钥是否需要一定的时间,它与集合的确切算法相同吗? – TheOne
@Ramin:是的,套装也使用哈希。集合中的项目必须是可散列的。 –
有趣的.... – TheOne