Накопление коллекций Счетчик в Python замедляется по мере увеличения размера накопленного счетчика - PullRequest
Новая
       18

Накопление коллекций Счетчик в Python замедляется по мере увеличения размера накопленного счетчика

0 голосов
/ 26 декабря 2018

У меня есть объект collection.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')

Ожидаемые результаты: время печати постоянно-ish во всем цикле

Фактические результаты: печатные времена увеличиваются по мере продвижения циклов

Фактические результаты (выполнение кода): 

[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

Вот графикчто демонстрирует тенденцию:

Time cost per iteration

1 Ответ

0 голосов
/ 26 декабря 2018

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

На самом деле вам даже не нужно создавать второй счетчик для добавления.Вы можете просто передать итерируемую часть элементов непосредственно в update, и это добавит количество элементов к существующим значениям счетчика: 

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