是否有可能將元素添加到列表中並保留訂單

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

​​