在大列表中重复添加元素（Python 2.6.6）
我有一个项目，需要通过串口从微控制器读取ASCII值（看起来像这样：AA FF BA 11 43 CF等等）。
这些输入数据来的很快（每秒大约有38组两个字符的值）。
我把这些输入数据添加到一个正在运行的测量列表中。
经过大约5个小时，我的列表已经增长到大约855000条记录。
我了解到，列表变得越大，进行列表操作的速度就会变得越慢。我打算让这个测试运行24小时，这样大约会得到300万条结果。
有没有比list.append()更高效、更快的方法来添加数据到列表中呢？
谢谢大家。
5 个回答
往Python的列表里添加东西是一个固定的成本。这意味着，添加的速度和列表里有多少个东西没有关系（理论上是这样）。不过在实际操作中，当你用完内存，系统开始进行交换时，添加的速度会变慢。
http://wiki.python.org/moin/TimeComplexity
理解你为什么要往列表里添加东西是很有帮助的。你打算对这些东西做什么？如果你不需要所有的东西，可以考虑建立一个环形缓冲区；如果你不需要进行计算，可以把列表写入文件等等。
你可能想要考虑的一个方法是，在收集数据的时候就把它写入一个文件里。我不太清楚（也不太在意）这样做会不会影响性能，但这样可以确保如果电源突然中断，你不会丢失所有的数据。一旦你收集完所有数据，就可以从文件中读取出来，然后放进一个列表、数组或者numpy矩阵等地方进行处理。
我了解到，列表越大，列表操作就会越慢。
其实这并不完全正确。在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);
正如Mark Ransom所指出的，旧版本的Python（<2.7, 3.0）有一个bug，会导致垃圾回收（GC）干扰这个过程。如果你使用的是这样的Python版本，可能需要禁用垃圾回收。不过，如果你生成了太多垃圾（导致引用计数失效），那就没办法了。