Accumulating collections Counter in Python becomes slower as accumulated counter increases in size

user_7928119 0
Viewed 267

I have a collections.Counter() object that keeps getting added Counter objects (accumulated) in a loop. As the loops pass and the accumulated Counter increases (more entries), the accumulate (+=) operation becomes slower.

A workaround is to use the Counter in batches and accumulate partial counters to add (reduce) them all in the end. But I would like to know why this is happening (maybe the underlying implementation uses hashmaps and the bucket size is not dynamic therefore collisions happen more and more often?)

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')

Expected results: The printed times are constant-ish in the entire loop

Actual results: The printed times increase as the loops goes forward

Actual results (code execution):

[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

Here is a plot that demonstrates the tendency:

Time cost per iteration

counter collections python performance
1 Answers

Counter.__iadd__ includes a linear scan of the self Counter to remove items with nonpositive counts. From 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()

Of course the time taken to do that will grow linearly with the size of the result Counter. If you want to avoid that behavior, use update instead of +=. Like += (and unlike dict.update), Counter.update adds counts instead of replacing entries. Unlike +=, it doesn't remove nonpositive counts.

# Instead of cnt += Counter(...)
cnt.update(Counter(txt_f.read().lower().replace('\n', ' ').split(' ')))

In fact, you don't even need to build a second Counter to add. You can just pass an iterable of elements to update directly, and it will add the element counts to the existing counts in the Counter:

cnt.update(txt_f.read().lower().replace('\n', ' ').split(' '))
user_67793070
Related