Неоднократно добавляется к большому списку (Python 2.6.6)

Question

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

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

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

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

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

Answer 1

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

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

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

/* 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. Если вы не можете, потому что вы генерируете слишком много мусора (что ускоряет пересчет), вам не повезло.

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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