是否可以向列表中添加元素并保留顺序

bisect.insort 比追加然后排序快一点(除非在需要再次排序列表之前您有一些元素需要添加)--在我的笔记本电脑上像往常一样测量(速度更快的机器当然会更快,但比率应该保持大致不变):

$ python -mtimeit -s'import random, bisect; x=range(20)' 'y=list(x); bisect.insort(y, 22*random.random())'
1000000 loops, best of 3: 1.99 usec per loop

VS

$ python -mtimeit -s'import random, bisect; x=range(20)' 'y=list(x); y.append(22*random.random()); y.sort()'
100000 loops, best of 3: 2.78 usec per loop

当然,您对这种差异的关注程度取决于此操作对应用程序的瓶颈有多关键——当然,在某些情况下,即使是一微秒的这一部分也会产生所有的差异,尽管它们是例外,而不是规则。

这个 bisect 模块没有那么灵活和可配置——您可以很容易地传递自己的自定义比较器进行排序(尽管如果您可以将它以key=argument的形式放置,那么 强烈地 建议这样做;在python 3中,只有key=remains,cmp=is gone,因为性能不好),而bisct则严格使用内置比较(因此必须将对象包装到包装器实现中) __cmp__ 或 __le__ 符合您的喜好,这也会对性能产生重要影响)。

在您的例子中,我将从附加然后排序的方法开始,并切换到不太方便的对分方法,前提是分析显示性能影响很大。记得 Knuth's (和霍尔的)名言,以及 Kent Beck's 几乎和著名的一样!-)

是的,这就是 bisect.insort 是的,但是它不带比较函数。如果对象是自定义对象,则可以重写 rich comparison methods 以确定所需的排序顺序。或者,您可以存储一个以排序键作为第一项的2元组,然后对其进行排序。

L.insert(index, object) -- insert object before index