Agregar repetidamente a una lista grande (Python 2.6.6)

Tengo un proyecto en el que estoy leyendo valores ASCII desde un microcontrolador a través de un puerto serie (se parece a esto: AA FF BA 11 43 CF, etc.) La entrada está llegando rápidamente (38 conjuntos de dos caracteres / segundo). Tomaré esta entrada y la añadiré a una lista de todas las mediciones.

Después de aproximadamente 5 horas, mi lista ha crecido a ~ 855000 entradas.

Me dan a entender que cuanto más grande se vuelve una lista, más lentas se vuelven las operaciones de lista. Mi intención es hacer que esta prueba se ejecute durante 24 horas, lo que debería generar alrededor de 3M de resultados.

¿Hay una forma más eficiente y rápida de agregar a una lista que list.append ()?

Gracias a todos.

Me dan a entender que cuanto más grande se vuelve una lista, más lentas se vuelven las operaciones de lista.

Eso no es cierto en general. Las listas en Python son, a pesar del nombre, no listas enlazadas sino matrices. Hay operaciones que son O (n) en arreglos (copia y búsqueda, por ejemplo), pero parece que no utilizas ninguno de estos. Como regla general: si es ampliamente utilizado e idiomático, algunas personas inteligentes eligieron una forma inteligente de hacerlo. list.append es una función incorporada ampliamente utilizada (y la función C subyacente también se usa en otros lugares, por ejemplo, en la lista de comprensión). Si hubiera una forma más rápida, ya estaría en uso.

Como verá cuando inspeccione el código fuente , las listas están generalizando, es decir, cuando se redimensionan, asignan más de lo necesario para un elemento, por lo que los siguientes n elementos pueden agregarse sin necesidad a otro tamaño (que es O (n)) . El crecimiento no es constante, es proporcional al tamaño de la lista, por lo que el cambio de tamaño se vuelve más raro a medida que la lista crece. Aquí está el fragmento de listobject.c:list_resize que determina la ubicación general:

 /* 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); 

Como señala Mark Ransom, las versiones más antiguas de Python (<2.7, 3.0) tienen un error que hace que el GC sabotee esto. Si tiene una versión de Python de este tipo, puede desactivar el gc. Si no puedes porque generas demasiada basura (eso resbala refcounting), sin embargo, no tienes suerte.

Una cosa que quizás desee considerar es escribir sus datos en un archivo a medida que se recostackn. No sé (o realmente me importa) si afectará el rendimiento, pero ayudará a garantizar que no pierda todos sus datos si se produce un fallo. Una vez que tenga todos los datos, puede extraerlos del archivo y atascarlos en una lista o una matriz o una matriz numpy o lo que sea para procesarlos.

Anexar a una lista de python tiene un costo constante. No se ve afectado por el número de elementos en la lista (en teoría). En la práctica, agregar a una lista se volverá más lento una vez que se quede sin memoria y el sistema comience a intercambiarse.

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

Sería útil comprender por qué en realidad agregas cosas a una lista. ¿Qué estás planeando hacer con los artículos? Si no los necesita todos, puede crear un búfer de anillo, si no necesita realizar cálculos, puede escribir la lista en un archivo, etc.

En primer lugar, 38 conjuntos de dos caracteres por segundo, 1 bit de parada, 8 bits de datos y sin paridad, son solo 760 baudios, en absoluto rápidos.

Pero de todos modos, mi sugerencia, si le preocupa tener listas demasiado grandes o no desea usar una lista enorme, es simplemente almacenar una lista en el disco una vez que scope un cierto tamaño y comenzar una nueva lista, repitiendo hasta ha obtenido todos los datos y, a continuación, combina todas las listas en una, una vez que haya terminado de recibir los datos.

Aunque puede omitir las listas completamente y seguir la sugerencia de nmichaels, escriba los datos en un archivo a medida que los obtenga y use un pequeño búfer circular para guardar los datos recibidos que aún no se han escrito.

Podría ser más rápido usar numpy si sabe cuánto tiempo va a durar la matriz y puede convertir sus códigos hexadecimales a ints:

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

Esto te dejará con una serie de enteros (que puedes convertir de nuevo a hex con hex ()), pero dependiendo de tu aplicación, quizás eso funcione igual de bien para ti.