反复附加到大型列表(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函数也用于其他地方,例如列表推导).如果有更快的方法,它就已经在使用中了.

正如您在检查源代码时所看到的那样,列表是过度分配的,即当它们被调整大小时,它们为一个项目分配的内容超过了需要,因此可以追加下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)有一个错误,使GC破坏了这一点.如果您有这样的Python版本,则可能需要禁用gc.如果你不能,因为你产生了太多的垃圾(这会导致反映),那你就不走运了.

Answer 2

您可能需要考虑的一件事是将数据写入收集的文件中.我不知道(或非常关心)它是否会影响性能,但它有助于确保在电源闪烁时不会丢失所有数据.一旦获得了所有数据,就可以将其从文件中取出并将其插入列表或数组或numpy矩阵或其他任何处理中.