搜索unorder列表而不將其轉換爲數組

有沒有辦法先排序然後搜索對象鏈表中的對象。我以爲只是給你一種排序方式和二分搜索你怎麼看？感謝搜索unorder列表而不將其轉換爲數組

來源

2010-02-02 gbox

二進制搜索不能很好地處理鏈表。你需要隨機訪問。 – Thilo 2010-02-02 05:13:28

根據API文檔，用於大型鏈表的'binarySearch'將執行與O（n）鏈接遍歷的O（log n）比較。一個樸素的算法會做O（n log n）鏈接遍歷。 – 2010-02-02 05:32:04

您是否正在爲此構建計算機性能基準測試例程，並且您需要投入儘可能多的高效率障礙來測試cpus的高效性能？ – 2010-02-02 06:13:19

java.util.Collections中的＃排序（）
java.util.Collections中的＃的binarySearch（）

的Collections類有很多其他驚人的方法，使程序員的生活更輕鬆。

注意，排序方法的實現將列表確實轉化爲陣，但你不必調用該方法:)

來源

2010-02-02 05:14:09

請注意，這些方法將首先將整個列表轉儲到數組中，然後重新構建列表。所以這不是特定於鏈表的算法。 – Thilo 2010-02-02 05:16:27

@Thilo - 這是正確的。它「有效」，但是如果你在鏈表上單純地做這個事情，性能將會比僅僅調用java.util.List＃contains（）'更糟！ – 2010-02-02 07:34:44

您可能需要之前明確地轉換到數組列表中的問題，如果想要搜索排序的清單是您的用例的最佳選擇，因爲這樣做效果不佳。列表排序是O（NlogN），二進制搜索是O（logN）。如果你只是想看看一個元素是否存在，你可以考慮通過contains方法找到你的列表元素，然後通過O（1）進行搜索。如果你能更詳細地解釋你的用例，那麼給你一些你可能考慮的集合的建議會容易得多。

編輯：考慮performance issues of List sorting如果您打算爲大型列表執行此操作。

來源

2010-02-02 05:27:10 harschware

請注意，java的sort（）方法使用合併排序 – 2010-02-02 05:30:49

@Suraj的修改版本 - 可能並不重要。更重要的問題是理解您的用例並選擇最合適的方法。最合適和最不合適的方法之間的差異*可能與'O（N ** 2）'差不多......這是一個很大的差異！ – 2010-02-02 07:41:27

這不是一個好方法，IMO。如果您使用Collections.sort(list)，其中list爲LinkedList，則會將list複製到臨時陣列，對其進行分類，然後將其複製回列表中，即O(NlogN)以加2 * O(N)副本。但是當你嘗試進行二分搜索時（例如使用Collections.binarySearch(list)，每個搜索都會執行O(N)列表遍歷操作，所以你也可以不用煩瑣列表的排序！

另一種方法是將列表轉換爲array或ArrayList，然後對數組/ ArrayList進行排序和搜索，這會給出一個副本加上一種排序來設置，並且O(logN)對於每個搜索都是

但是這兩種方法都不是最好的方法，這取決於多少次您需要執行搜索操作。

如果你只是想在列表中進行一次搜索，那麼調用list.contains(...)就是O(N) ......這比任何涉及排序和二進制搜索的更好。
如果你想在一個永不改變的列表上進行多次搜索，你最好把列表項放到一個HashSet中。構建一個HashSet是O(N)，搜索是O(1)。（假定你不需要你自己的比較器。）
如果你想在一個列表上進行多次搜索，這個列表會不斷改變順序不重要的地方，用HashSet替換列表。更新HashSet的增量成本將爲每個添加/刪除的O(1)，以及每個搜索的O(1)。
如果你想這樣做，不斷變化且訂單顯著名單上多次搜索，用插入順序LinkedHashMap更換名單。對於每次添加/刪除，這將是O(1)，並且對於每個搜索...... O(1)但是具有比HashSet大的比例常量。

來源

2010-02-02 06:04:21

+1，寫得很好。 – harschware 2010-02-02 17:16:21

搜索unorder列表而不將其轉換爲數組

回答

相關問題