Python的平分線如何工作？

我讀過Python的列表是使用指針實現的。然後我看到這個模塊http://docs.python.org/2/library/bisect.html高效地插入一個排序列表。它如何有效地做到這一點？如果列表是使用指針而不是通過連續數組實現的，那麼如何有效地搜索插入點？如果列表是通過一個連續的數組來支持的，那麼當插入一個元素時就不得不進行元素移位。那麼這個bisect如何有效地工作呢？Python的平分線如何工作？

來源

2013-11-27 rafalio

我假設您已閱讀鏈接到您鏈接到頁面頂部的源代碼？ – vanza

['list'實際上是一個數組]（http://stackoverflow.com/questions/3917574/how-is-pythons-list-implemented）。 –

啊我看到了，所以它被存儲爲一個數組。我錯過了「bisect」文檔中說插入實際上是O（n）的部分，所以現在對我來說一切都很清楚，謝謝。 – rafalio

我相信列表中的元素是指向的，但「列表」實際上是一個連續的數組（在C中）。他們被稱爲列表，但他們不是鏈接列表。

實際上，在排序列表中查找元素非常好 - 它是O（logn）。但插入不是很好 - 它是O（n）。

如果你需要一個logn數據結構，最好使用一個樹木或紅黑樹。

來源

2013-11-28 00:02:46 dstromberg

這是有效的搜索，而不是實際的插入。快速搜索使得整個操作「增加一個值並保持所有值的順序」比較快，例如，再次附加然後再排序：O(n)而不是O(n log n)。

來源

2013-11-28 00:00:24

儘管在Python中，再次附加，然後再排序也是'O（n）'感謝TimSort。 –

Python的平分線如何工作？

回答

相關問題