Существует ли способ обойти Python list.append () становящийся прогрессивно медленнее в цикле, когда список растет?

Низкая производительность, которую вы наблюдаете, вызвана ошибкой в ​​сборщике мусора Python в используемой вами версии. Выполните обновление до Python 2.7 или 3.1 или выше, чтобы восстановить амортизированное поведение 0 (1), ожидаемое при добавлении списка в Python.

Если вы не можете выполнить обновление, отключите сборку мусора при построении списка и включите его после завершения.

(Вы также можете настроить триггеры сборщика мусора или выборочно вызывать сборщик по мере продвижения, но я не рассматриваю эти варианты в этом ответе, потому что они более сложные, и я подозреваю, что ваш вариант использования поддается описанному выше решению.)

​​Справочная информация:

См .: https: //bugs.python.org / issue4074 , а также https://docs.python.org/release/2.5.2/lib/module-gc.html

Репортер отмечает, что добавление сложных объектов (объектов, которые не числа или строки) в список линейно замедляется по мере увеличения длины списка.

Причина такого поведения в том, что сборщик мусора проверяет и перепроверяет каждый объект в списке, чтобы узнать, подходят ли они для сборки мусора. Такое поведение приводит к линейному увеличению времени добавления объектов в список. Ожидается, что исправление появится в py3k, поэтому оно не должно применяться к используемому вами интерпретатору.

Тест:

Я провел тест, чтобы продемонстрировать это. Для 1k итераций я добавляю 10k объектов в список и записываю время выполнения для каждой итерации. Общая разница во времени работы очевидна. Когда сборка мусора отключена во время внутреннего цикла теста, время выполнения в моей системе составляет 18,6 с. При включенной сборке мусора для всего теста время выполнения составляет 899,4 с.

Это тест:

import time
import gc

class A:
    def __init__(self):
        self.x = 1
        self.y = 2
        self.why = 'no reason'

def time_to_append(size, append_list, item_gen):
    t0 = time.time()
    for i in xrange(0, size):
        append_list.append(item_gen())
    return time.time() - t0

def test():
    x = []
    count = 10000
    for i in xrange(0,1000):
        print len(x), time_to_append(count, x, lambda: A())

def test_nogc():
    x = []
    count = 10000
    for i in xrange(0,1000):
        gc.disable()
        print len(x), time_to_append(count, x, lambda: A())
        gc.enable()

Полный источник: https://hypervolu.me/~erik/programming/python_lists/listtest.py.txt

Графический результат: красный цвет с включенным gc, синий с выключенным gc. По оси ординат отложены секунды в логарифмическом масштабе.

_{(источник: hypervolu.me )}

Поскольку два графика различаются на несколько порядков по компоненту y, здесь они представлены независимо, ось Y масштабируется линейно.

_{(источник: hypervolu.me )}

_{(источник: hypervolu.me )}

Интересно, что при отключенной сборке мусора мы видим лишь небольшие всплески времени выполнения на 10 КБ дополнений, что говорит о том, что затраты на перераспределение списков Python относительно низки. В любом случае они на много порядков ниже затрат на сборку мусора.

Плотность вышеупомянутых графиков затрудняет понимание того, что при включенном сборщике мусора большинство интервалов действительно имеют хорошую производительность; только тогда, когда сборщик мусора циклически повторяет цикл, мы сталкиваемся с патологическим поведением. Вы можете наблюдать это на этой гистограмме времени добавления 10k. Большинство точек данных падают примерно на 0,02 с на 10 тыс. Добавлений.

_{(источник: hypervolu.me )}

Необработанные данные, использованные для создания этих графиков, можно найти на http://hypervolu.me/~erik/programming/python_lists/