是否有可能将元素添加到列表中并保留订单

Question

我想向保存列表顺序的列表添加元素。

假设对象的列表是[A，B，C，d]我有一个函数CMP，其比较该列表的两个元素。如果我添加更大的f对象，我希望它处于最后位置。

也许是更好的排序完整列表...

Answer 1

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模块是不够灵活和可配置的 - 你可以很容易地通过自己的自定义比较排序（但如果你都不可能把它放在一个键=参数的形式，你强烈建议做那么;在Python 3中，只有key =保留，cmp =不见了，因为性能不可能变好），而对分严格地使用内置比较（所以你必须将你的对象包装到实现__cmp__的包装中或__le__，这也有重要的性能影响）。

在你的鞋子里，我将从append-then-sort方法入手，并且只有在剖析表明性能受到重大影响时才切换到不太方便的对分方法。请记住Knuth's（以及霍尔斯）的名言，Kent Beck's也几乎与此同名！ - ）

Answer 2

是的，这就是bisect.insort是，但是它并不需要一个比较函数。如果对象是自定义对象，则可以覆盖一个或多个rich comparison methods以建立所需的排序顺序。或者，您可以使用排序键作为第一项存储一个2元组，然后对其进行排序。

Answer 3

​​