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

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

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

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

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

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

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


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

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

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

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


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

вопрос задан 18.03.2010
Deniz
626 репутация

6 ответов


  • 88 рейтинг

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

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

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

    Фон:

    См .: https: // ошибки. питон. org / issue4074 , а также https: // docs. питон. орг / выпуск / 2. 5. 2 / Библиотека / модуль-дс. 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. я / ~ Erik / программирование / python_lists / listtest. ру. TXT

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

    http: // hypervolu. я / ~ Erik / программирование / python_lists / дс. png

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

    http: // hypervolu. я / ~ Erik / программирование / python_lists / gc_on. png

    http: // hypervolu. я / ~ Erik / программирование / python_lists / gc_off. png

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

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

    http: // hypervolu. я / ~ Erik / программирование / python_lists / gc_on. истор. png

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

    ответ дан Erik Garrison, с репутацией 1414, 19.03.2010
  • 13 рейтинг

    Обходить нечего: добавление в список является O (1) амортизированным.

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

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

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

    ответ дан Mike Graham, с репутацией 48069, 18.03.2010
  • 6 рейтинг

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

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

    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, которые могли бы объяснить это, я не уверен. Но я почти уверен, что структура данных списка не является виновником.

    ответ дан FogleBird, с репутацией 46939, 18.03.2010
  • 1 рейтинг

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

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

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

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

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

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

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

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

    theArray[i] = val_i
    

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

    theArray = theArray[:i]
    

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

    ответ дан Nathan Labenz, с репутацией 439, 29.11.2011
  • 1 рейтинг

    Можете ли вы попробовать http: // docs. питон. орг / выпуск / 2. 5. 2 / Библиотека / Deque-объекты. html выделите ожидаемое количество обязательных элементов в вашем списке? ? Держу пари, что этот список является непрерывным хранилищем, которое необходимо перераспределять и копировать каждые несколько итераций. (похоже на некоторые популярные реализации std :: vector в c ++)

    РЕДАКТИРОВАТЬ: Резервное копирование http: // www. питон. org / doc / faq / general / # how-are-lists-реализованный

    ответ дан Tomasz Zielinski, с репутацией 12898, 18.03.2010
  • 0 рейтинг

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

    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
    

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

    ответ дан Kahiga, с репутацией 1, 30.07.2016