Повторное добавление в большой список (Python 2.6.6)

Question

У меня есть проект, в котором я считываю значения ASCII с микроконтроллера через последовательный порт (выглядит так: AA FF BA 11 43 CF и т. Д.) Вход поступает быстро (38 двухсимвольных набора в секунду).Я беру эти данные и добавляю их в рабочий список всех измерений.

Примерно через 5 часов мой список вырос до ~ 855000 записей.

Мне дано понять, чточем больше список, тем медленнее становятся операции со списком.Мое намерение состоит в том, чтобы запустить этот тест в течение 24 часов, что должно дать около 3 млн. Результатов.

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

Спасибо всем.

Answer 1

Мне дано понять, что чем больше становится список, тем медленнее становятся операции со списком.

В общем, это не так.Списки в Python - это, несмотря на название, не связанные списки, а массивы.Есть операции, которые являются O (n) для массивов (например, копирование и поиск), но вы, кажется, не используете ни один из них.Практическое правило: если он широко используется и идиоматичен, некоторые умные люди пошли и выбрали умный способ сделать это.list.append - широко используемая встроенная функция (а лежащая в основе функция C также используется в других местах, например, в списках).Если бы существовал более быстрый способ, он бы уже использовался.

Как вы увидите, когда вы будете проверять исходный код , списки перераспределяются, то есть, когда их размер изменяется, они выделяют большечем необходимо для одного элемента, так что следующие n элементов могут быть добавлены без необходимости другого изменения размера (то есть O (n)).Рост не является постоянным, он пропорционален размеру списка, поэтому изменение размера становится все реже по мере увеличения списка.Вот фрагмент из listobject.c:list_resize, который определяет перераспределение:

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

Как отмечает Марк Рэнсом, более старые версии Python (<2.7, 3.0) имеют ошибку, которая заставляет GC саботировать это.Если у вас есть такая версия Python, вы можете отключить gc.Если вы не можете этого сделать, потому что генерируете слишком много мусора (что приводит к перерасчету), вам не повезло. </p>

Answer 2

Одна вещь, которую вы можете рассмотреть, - это запись ваших данных в файл по мере его сбора.Я не знаю (или действительно беспокоюсь), повлияет ли это на производительность, но это поможет гарантировать, что вы не потеряете все свои данные, если произойдет сбой питания.После того, как вы получили все данные, вы можете извлечь их из файла и вставить в список, массив, матрицу или еще что-нибудь для обработки.

Answer 3

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

http://wiki.python.org/moin/TimeComplexity

Было бы полезно понять, почему вы действительно добавляете вещи в список. Что вы планируете делать с предметами. Если вам не нужны все из них, вы можете создать кольцевой буфер, если вам не нужны вычисления, вы можете записать список в файл и т. Д.

Answer 4

Может быть быстрее использовать numpy, если вы знаете, как долго будет работать массив, и можете преобразовать свои шестнадцатеричные коды в целые:

import numpy
a = numpy.zeros(3000000, numpy.int32)
for i in range(3000000):
   a[i] = int(scanHexFromSerial(),16)

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

Answer 5

Прежде всего, 38 двухсимвольных наборов в секунду, 1 стоповый бит, 8 битов данных и без проверки четности, это всего 760 бод, совсем не быстро.

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

Хотя вы можете полностью пропустить списки и просто воспользоваться предложением nmichaels, записать данные в файл по мере их получения и использоватьнебольшой круговой буфер для хранения полученных данных, которые еще не были записаны.