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

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

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

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

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

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

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


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

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

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

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


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

4b9b3361

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

http://hypervolu.me/~erik/programming/python_lists/gc.png

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

http://hypervolu.me/~erik/programming/python_lists/gc_on.png

http://hypervolu.me/~erik/programming/python_lists/gc_off.png

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

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

http://hypervolu.me/~erik/programming/python_lists/gc_on.hist.png

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

88
ответ дан 19 марта '10 в 22:20
источник

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

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

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

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

13
ответ дан 19 марта '10 в 2:37
источник

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

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

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

6
ответ дан 19 марта '10 в 2:50
источник

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

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

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

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

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

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

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

Вы можете сразу установить каждый элемент в массиве:

theArray[i] = val_i

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

theArray = theArray[:i]

Это привело к большой разнице в моем случае.

1
ответ дан 29 нояб. '11 в 12:50
источник

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

EDIT: резервное копирование http://www.python.org/doc/faq/general/#how-are-lists-implemented

1
ответ дан 19 марта '10 в 1:39
источник

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

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

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

0
ответ дан 30 июля '16 в 4:20
источник