23

I have a project where I am reading in ASCII values from a microcontroller through a serial port (looks like this : AA FF BA 11 43 CF etc) The input is coming in quickly (38 two character sets / second). I'm taking this input and appending it to a running list of all measurements.

After about 5 hours, my list has grown to ~ 855000 entries.

I'm given to understand that the larger a list becomes, the slower list operations become. My intent is to have this test run for 24 hours, which should yield around 3M results.

Is there a more efficient, faster way to append to a list then list.append()?

Thanks Everyone.

Michael
  • 233
  • 1
  • 2
  • 4
  • 10
    _"I'm given to understand that the larger a list becomes, the slower list operations become."_ `[citation needed]` – Matt Ball Apr 29 '11 at 15:18
  • 2
    Have you tried to run it for 24 hours and seen an issue? Whats the issue? – tMC Apr 29 '11 at 15:22
  • 3
    @Matt, see http://stackoverflow.com/questions/2473783/is-there-a-way-to-circumvent-python-list-append-becoming-progressively-slower-i – Mark Ransom Apr 29 '11 at 15:24
  • 2
    @Mark: Interesting. It was a *bug* though, and is fixed by now. –  Apr 29 '11 at 15:34
  • 1
    @Mark: the answer to that question was that there's a bug in the Python GC, so the solution to the problem is to _disable the GC_, not to use a different algorithm. – Matt Ball Apr 29 '11 at 15:35
  • The bug is fixed in 2.7+, but not in 2.6.6. – Jochen Ritzel Apr 29 '11 at 15:39
  • @delnan, Matt asked for a citation and I gave one. If the bug is fixed, I'd be curious to see a citation for that as well. Without evidence I'd assume that the "bug" is inherent to the design of the garbage collector and not easy to fix. – Mark Ransom Apr 29 '11 at 15:40
  • @Matt, disabling the GC is one possible answer, but not the only answer. Maybe not even the best one. – Mark Ransom Apr 29 '11 at 15:41
  • @Mark: The [issue](http://bugs.python.org/issue4074) linked to in the top answer of that question is marked as fixed. Assume what you want, but the Python devs seem to think the problem is solved. And the two benchmarks shown in that answer yield very close results for me under Python 3.1. –  Apr 29 '11 at 15:43
  • @delnan, that was exactly the info I was asking for - thanks. Sorry I didn't find it for myself. – Mark Ransom Apr 29 '11 at 15:49

5 Answers5

44

I'm given to understand that the larger a list becomes, the slower list operations become.

That's not true in general. Lists in Python are, despite the name, not linked lists but arrays. There are operations that are O(n) on arrays (copying and searching, for instance), but you don't seem to use any of these. As a rule of thumb: If it's widely used and idiomatic, some smart people went and chose a smart way to do it. list.append is a widely-used builtin (and the underlying C function is also used in other places, e.g. list comprehensions). If there was a faster way, it would already be in use.

As you will see when you inspect the source code, lists are overallocating, i.e. when they are resized, they allocate more than needed for one item so the next n items can be appended without need to another resize (which is O(n)). The growth isn't constant, it is proportional with the list size, so resizing becomes rarer as the list grows larger. Here's the snippet from listobject.c:list_resize that determines the 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);

As Mark Ransom points out, older Python versions (<2.7, 3.0) have a bug that make the GC sabotage this. If you have such a Python version, you may want to disable the gc. If you can't because you generate too much garbage (that slips refcounting), you're out of luck though.

  • 4
    True answer in theory, but the reality is more complicated. Unless you've measured it yourself and know it to be fixed in recent Python versions - See http://stackoverflow.com/questions/2473783/is-there-a-way-to-circumvent-python-list-append-becoming-progressively-slower-i – Mark Ransom Apr 29 '11 at 15:37
16

One thing you might want to consider is writing your data to a file as it's collected. I don't know (or really care) if it will affect performance, but it will help ensure that you don't lose all your data if power blips. Once you've got all the data, you can suck it out of the file and jam it in a list or an array or a numpy matrix or whatever for processing.

nmichaels
  • 49,466
  • 12
  • 107
  • 135
2

Appending to a python list has a constant cost. It is not affected by the number of items in the list (in theory). In practice appending to a list will get slower once you run out of memory and the system starts swapping.

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

It would be helpful to understand why you actually append things into a list. What are you planning to do with the items. If you don't need all of them you could build a ring buffer, if you don't need to do computation you could write the list to a file, etc.

cellcortex
  • 3,166
  • 1
  • 24
  • 34
  • The reason for the growing list is I do need to do some math on the elements later on (after the capture) and pass it along as a csv file (for later manipulation in Matlab). – Michael Apr 29 '11 at 15:36
0

First of all, 38 two-character sets per second, 1 stop bit, 8 data bits, and no parity, is only 760 baud, not fast at all.

But anyway, my suggestion, if you're worried about having overly large lists/don't want to use one huge list, is just to store store a list on disk once it reaches a certain size and start a new list, repeating until you've gotten all the data, then combining all the lists into one once you're done receiving the data.

Though you may skip the sublists completely and just go with nmichaels' suggestion, writing the data to a file as you get it and using a small circular buffer to hold the received data that has not yet been written.

JAB
  • 20,783
  • 6
  • 71
  • 80
0

It might be faster to use numpy if you know how long the array is going to be and you can convert your hex codes to ints:

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

This will leave you with an array of integers (which you could convert back to hex with hex()), but depending on your application maybe that will work just as well for you.

flionetti
  • 11
  • 1