Ajout de façon répétée à une grande liste (Python 2.6.6)

J'ai un projet où je suis, la lecture de valeurs ASCII à partir d'un microcontrôleur par l'intermédiaire d'un port série (qui ressemble à ceci : AA FF BA 11 43 CF, etc)
L'entrée est à venir rapidement (38 deux jeux de caractères /seconde).
Je vais prendre cette entrée et en les ajoutant à une liste de toutes les mesures.

Après environ 5 heures, ma liste s'est allongée à ~ 855000 entrées.

Je me suis donné à comprendre que plus d'une liste devient, le ralentissement de la liste des opérations de devenir. Mon intention est d'avoir présent à l'essai de 24 heures, ce qui devrait générer environ 3M résultats.

Est-il plus efficace, plus rapide pour ajouter à une liste de liste de.append()?

Merci À Tous.

source d'informationauteur Michael

  1. 24

    Je me suis donné à comprendre que plus d'une liste devient, le ralentissement de la liste des activités.

    Ce n'est pas vrai en général. Les listes en Python sont, malgré le nom, pas de listes liées mais les tableaux. Il y a des opérations qui sont en O(n) sur les tableaux (de la copie et de la recherche, par exemple), mais vous ne semblez pas à l'utilisation de ces. Comme une règle de base: Si il est largement utilisé et idiomatiques, des gens brillants est allé et a choisi une façon intelligente de le faire. list.append est un moyen largement utilisé builtin (et de la fonction C est également utilisé dans d'autres endroits, comme par exemple interprétations de la liste). Si il y avait un moyen plus rapide, il serait déjà en cours d'utilisation.

    Comme vous le verrez lorsque vous inspectez le code sourceles listes sont overallocating, c'est à dire quand ils sont redimensionnés, ils allouent plus que nécessaire pour un élément, de sorte que le prochain n éléments peuvent être ajoutés sans avoir besoin de redimensionner une autre (qui est en O(n)). La croissance n'est pas constante, elle est proportionnelle à la taille de la liste, de sorte que le redimensionnement devient plus rare que la liste grandit. Voici l'extrait de listobject.c:list_resize qui détermine la surutilisation:

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

    Comme Marque de Rançon points, les anciennes versions de Python (<2.7, 3.0) ont un bug qui font de la GC de sabotage. Si vous en avez une version de Python, vous souhaiterez peut-être désactiver la gc. Si vous ne pouvez pas parce que vous générer trop de déchets (qui se glisse compteurs refcount), vous êtes hors de la chance si.

  2. 11

    Une chose que vous pourriez envisager est l'écriture de vos données vers un fichier, car il est recueilli. Je ne sais pas (ou vraiment) si il aura une incidence sur les performances, mais cela permettra de s'assurer que vous ne perdez toutes vos données si l'alimentation soubresauts. Une fois que vous avez toutes les données, vous pouvez sucer du fichier et de la confiture dans une liste ou d'un tableau ou d'un numpy matrice ou que ce soit pour le traitement.

  3. 2

    Ajoutant à une liste python a un coût constant. Il n'est pas affecté par le nombre d'éléments dans la liste (en théorie). Dans la pratique, l'ajout à une liste obtiendrez plus lente une fois que vous exécuter de mémoire et le démarrage du système d'échange.

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

    Il serait utile de comprendre pourquoi vous avez fait ajouter des choses dans une liste. Qu'allez-vous faire avec les éléments. Si vous n'avez pas besoin de tous d'entre eux vous pourriez construire un anneau de la mémoire tampon, si vous n'avez pas besoin de faire le calcul, vous pourriez écrire la liste dans un fichier, etc.

  4. 0

    Tout d'abord, 38 de deux jeux de caractères par seconde, 1 bit d'arrêt, 8 bits de données, et pas de parité, est seulement 760 bauds, pas rapide du tout.

    Mais de toute façon, ma suggestion, si vous êtes inquiet d'avoir trop grandes listes/ne souhaitez pas utiliser une liste énorme, c'est juste pour stocker stocker une liste sur le disque une fois qu'il atteint une certaine taille, et de commencer une nouvelle liste, la répétition jusqu'à ce que vous avez obtenu toutes les données, puis de les combiner toutes les listes en un seul une fois que vous avez terminé la réception de données.

    Si vous pouvez ignorer les sous-listes complètement et juste aller avec nmichaels suggestion, d'écrire les données dans un fichier que vous l'obtenez, et à l'aide d'un petit tampon circulaire pour contenir les données reçues qui n'a pas encore été écrite.

  5. 0

    Il peut être plus rapide d'utiliser numpy si vous savez combien de temps le tableau va être et vous pouvez convertir vos codes hex à ints:

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

    Ce qui vous laisse avec un tableau d'entiers (que vous pouvez convertir en arrière pour hex hex()), mais en fonction de votre application peut être que cela fonctionnera tout aussi bien pour vous.