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

Question

У меня есть большой файл, из которого я читаю, и преобразовываю каждые несколько строк в экземпляр объекта.

Поскольку я зацикливаюсь на файле, я сохраняю экземпляр в списке с помощью list.append (instance), а затем продолжаю зацикливаться.

Это файл размером ~ 100 МБ, поэтому он не слишком велик, но по мере увеличения списка цикл постепенно замедляется. (Я печатаю время для каждого круга в цикле).

Это не свойственно циклу ~, когда я печатаю каждый новый экземпляр, когда я зацикливаюсь в файле, программа прогрессирует с постоянной скоростью ~, только когда я добавляю их в список, становится медленно.

Мой друг предложил отключить сборку мусора перед циклом while, а затем включить его и выполнить вызов сборки мусора.

Кто-нибудь еще наблюдал подобную проблему с замедлением работы list.append? Есть ли другой способ обойти это?

---

Я попробую следующие две вещи, предложенные ниже.

(1) «предварительное распределение» памяти ~ каков наилучший способ сделать это? (2) Попробуйте использовать deque

Несколько постов (см. Комментарий Алекса Мартелли) предполагали фрагментацию памяти (у него большой объем доступной памяти, как у меня) ~, но для этого не было очевидных исправлений производительности.

Чтобы воспроизвести явление, запустите тестовый код, приведенный ниже в ответах, и предположите, что в списках есть полезные данные.

---

gc.disable () и gc.enable () помогают с синхронизацией. Я также сделаю тщательный анализ того, где все время проводится.

Answer 1

Низкая производительность, которую вы наблюдаете, вызвана ошибкой в ​​сборщике мусора 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. Ось Y - это логарифмическое масштабирование секунд.

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

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

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

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

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

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

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

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

Answer 2

Нечего обойти: добавление в список O (1) амортизируется.

Список (в CPython) - это массив, по крайней мере, такой же длины, как список, и вдвое длиннее. Если массив не заполнен, добавление в список так же просто, как назначение одного из членов массива (O (1)). Каждый раз, когда массив заполнен, он автоматически удваивается в размере. Это означает, что в некоторых случаях требуется операция O (n), но требуется только для каждых n операций , и она все реже требуется по мере увеличения списка. O (n) / n ==> O (1). (В других реализациях имена и детали могут потенциально измениться, но свойства того же времени должны сохраняться.)

Добавление к списку уже масштабируется.

Возможно ли, что когда размер файла станет большим, вы не сможете удержать все в памяти, и у вас возникнут проблемы с подкачкой ОС на диск? Возможно, это другая часть вашего алгоритма, которая плохо масштабируется?

Answer 3

Многие из этих ответов - просто дикие догадки. Мне нравится, что Майк Грэм лучший, потому что он прав насчет реализации списков. Но я написал некоторый код, чтобы воспроизвести ваше заявление и изучить его дальше. Вот некоторые выводы.

Вот с чего я начал.

import time
x = []
for i in range(100):
    start = time.clock()
    for j in range(100000):
        x.append([])
    end = time.clock()
    print end - start

Я просто добавляю пустые списки в список x. Я распечатываю продолжительность для каждых 100 000 добавлений, 100 раз. Это замедляется, как вы утверждали. (0,03 секунды для первой итерации и 0,84 секунды для последней ... большая разница.)

Очевидно, что если вы создаете экземпляр списка, но не добавляете его к x, он работает намного быстрее и не масштабируется с течением времени.

Но если вы измените x.append([]) на x.append('hello world'), скорость вообще не увеличится. Один и тот же объект добавляется в список 100 * 100 000 раз.

Что я делаю из этого:

• Уменьшение скорости никак не связано с размером списка. Это связано с количеством живых объектов Python.
• Если вы вообще не добавляете элементы в список, они просто сразу же собирают мусор и больше не управляются Python.
• Если вы добавляете один и тот же элемент снова и снова, количество живых объектов Python не увеличивается. Но список должен изменить размер себя время от времени. Но это не источник проблем с производительностью.
• Поскольку вы создаете и добавляете множество вновь созданных объектов в список, они остаются живыми и не удаляются сборщиком мусора. Замедление, вероятно, как-то связано с этим.

Насколько внутренности Python это могли объяснить, я не уверен. Но я почти уверен, что структура данных списка не виновна.

Answer 4

Вместо этого используйте набор, а затем в конце преобразуйте его в список

my_set=set()
with open(in_file) as f:
    # do your thing
    my_set.add(instance)


my_list=list(my_set)
my_list.sort() # if you want it sorted

У меня была такая же проблема, и это решило проблему времени на несколько порядков.

Answer 5

Я столкнулся с этой проблемой при использовании массивов Numpy, созданных следующим образом:

import numpy
theArray = array([],dtype='int32')

Присоединение к этому массиву в цикле занимало все больше времени по мере роста массива, что было препятствием, поскольку у меня было 14M добавлений.

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

Что работало, так это создание массива с предопределенным размером следующим образом:

theArray = array(arange(limit),dtype='int32')

Просто убедитесь, что limit больше нужного вам массива.

Затем вы можете установить каждый элемент в массиве напрямую:

theArray[i] = val_i

И в конце при необходимости вы можете удалить неиспользованную часть массива

theArray = theArray[:i]

Это имело ОГРОМНОЕ различие в моем случае.

Answer 6

Можете ли вы попробовать http://docs.python.org/release/2.5.2/lib/deque-objects.html выделить ожидаемое количество обязательных элементов в вашем списке? ? Держу пари, что этот список является непрерывным хранилищем, которое необходимо перераспределять и копировать каждые несколько итераций. (аналогично некоторым популярным реализациям std :: vector в c ++)

РЕДАКТИРОВАТЬ: поддерживается http://www.python.org/doc/faq/general/#how-are-lists-implemented