python - 随着累积计数器大小的增加,Python中的累积集合计数器变得更慢
问题描述
我有一个 collections.Counter() 对象,它不断在循环中获取添加的 Counter 对象(累积)。随着循环通过并且累积计数器增加(更多条目),累积(+=)操作变得更慢。
一种解决方法是批量使用计数器并累积部分计数器以最终添加(减少)它们。但我想知道为什么会发生这种情况(也许底层实现使用哈希图并且桶大小不是动态的,因此冲突越来越频繁地发生?)
cnt = Counter()
for i in range(len(list_files_txt)):
t0 = time()
f = list_files_txt[i]
print('[{}/{}]'.format(i, len(list_files_txt)))
with open(f, 'r') as txt_f:
cnt += Counter(txt_f.read().lower().replace('\n', ' ').split(' '))
d_t = time() - t0
print('Time: ', d_t)
with open('times.txt', 'a') as times_f:
times_f.write(str(d_t)+'\n')
预期结果:打印时间在整个循环中是恒定的
实际结果:随着循环的进行,打印时间会增加
实际结果(代码执行):
[0/185187]
Time: 0.0009126663208007812
[1/185187]
Time: 0.0011148452758789062
[2/185187]
Time: 0.0006835460662841797
[3/185187]
Time: 0.0009150505065917969
[4/185187]
Time: 0.0005855560302734375
# A few thousand iterations later...
[14268/185187]
Time: 0.1499614715576172
[14269/185187]
Time: 0.14177680015563965
[14270/185187]
Time: 0.1480724811553955
[14271/185187]
Time: 0.14731359481811523
[14272/185187]
Time: 0.15594100952148438
这是一个展示这种趋势的图:
解决方案
Counter.__iadd__
包括对 的线性扫描self
Counter
以删除具有非正数的项目。从cpython/blob/master/Lib/collections/__init__.py
def _keep_positive(self):
'''Internal method to strip elements with a negative or zero count'''
nonpositive = [elem for elem, count in self.items() if not count > 0]
for elem in nonpositive:
del self[elem]
return self
def __iadd__(self, other):
'''Inplace add from another counter, keeping only positive counts.
>>> c = Counter('abbb')
>>> c += Counter('bcc')
>>> c
Counter({'b': 4, 'c': 2, 'a': 1})
'''
for elem, count in other.items():
self[elem] += count
return self._keep_positive()
当然,这样做所花费的时间会随着结果的大小线性增长Counter
。如果您想避免这种行为,请使用update
而不是+=
. 喜欢+=
(和不一样dict.update
),Counter.update
添加计数而不是替换条目。与 不同+=
,它不会删除非正数。
# Instead of cnt += Counter(...)
cnt.update(Counter(txt_f.read().lower().replace('\n', ' ').split(' ')))
事实上,您甚至不需要构建第二个 Counter 来添加。您可以直接将一个可迭代的元素传递给update
,它会将元素计数添加到 Counter 中的现有计数中:
cnt.update(txt_f.read().lower().replace('\n', ' ').split(' '))
推荐阅读
- python - Kivy Widget 不动
- excel - 有没有一种通用的方法来处理excel中的可见单元格?
- python - 如何通过mysql python将多个值(列表)插入数据库
- c - C中临时对象的有效类型
- java - 访问不同 fxml 文件中的 ui 元素
- javascript - 如何使用 NodeJs Async 更新数据库中的数组数据?
- azure - 构建管道中的变量替换
- javascript - 我需要使用 javascript 从结果 json 文件中删除不必要的 json 对象
- python - 查找两个列表python中每个单词的频率
- ios - iOS - 因横向和纵向特征而异