在定時查找排序列表中的索引

我有一組自定義對象，我將其添加到列表中，然後使用自定義比較器進行排序。然後，我有第二個列表的這些對象的子集，我需要在第一個列表中的索引，以便我可以找到相同的對象（由我的比較器定義）。當列表被排序時，這些對象應該僅僅是這個對象之前或之後的對象，但事先並不知道有多少將會是相同的（可能是2-3）。在定時查找排序列表中的索引

我需要這個查找是在不斷的時間，因爲我的列表排序的對象將是相當大的。我顯然可以使用list.index（），但這將是O（N），我認爲我可以做得更好。我的第一個想法是使用雙向鏈表，但看起來我需要自己實現這一點，而且我不完全確定如何對它進行排序。

python中是否存在雙鏈表實現？還是有更好的選擇這個問題？此外，我目前在python2.5上，無法更新我的版本，但如果我受限於我的版本，我仍然有興趣瞭解該解決方案。

來源

2016-12-21 Fozefy

我想恆定時間是不可能的，如果你沒有另一個允許計算的屬性（如在'範圍內）。但是如果'O（log n）'足夠，你總是可以使用['bisect']（https://docs.python.org/2/library/bisect.html）。 – MSeifert

我認爲應該有可能得到一個恆定的時間查找，如果我做了排序後的O（N）設置。至少我可以遍歷列表並將對象的索引添加到每個對象，當我將對象從第二個列表中拉出時可以引用該對象。該解決方案似乎有點破解，因爲我認爲應該有一個列表實現方式來處理這個對我來說，但我認爲它可能會工作。 – Fozefy

對於額外的O（N）存儲的價格，您可以創建一個字典來支持排序列表的列表索引：'dict（（e，i）for（i，e）in enumerate（sorted_list））''。這會給你O（1）查找你的第二個列表中的項目的位置。 – wildwilhelm

有關其他O（N）的存儲價格，你可以創建一個字典來背排序列表的列表索引：

index_map = dict((e,i) for (i,e) in enumerate(sorted_list))

這將使你O（1）查找的位置您的第二個列表中的項目。

如果sorted_list的元素是自定義對象，則@mseifert指出，此方法依賴於正確定義了__eq__的對象，並且也是可哈希的。

來源

2017-01-11 10:50:51 wildwilhelm

在定時查找排序列表中的索引

回答

相關問題