高效的方式來尋找最相似的名單<String>

我有一個list1<String>和其他1000 list<String>。我需要選擇具有最精確匹配值的列表。高效的方式來尋找最相似的名單<String>

今天我瀏覽每個list<String>並與list1比較，將封面保存在一些排序列表中，最後選擇最相似的列表。

public static <T> List<T> intersection(List<T> list1, List<T> list2) { 
     List<T> list = new ArrayList<T>(); 

     for (T t : list1) { 
      if(list2.contains(t)) { 
       list.add(t); 
      } 
     } 

     return list; 
    }

此操作遍歷所有1000個唯一列表需要花費時間，假設我有很多列表來比較它。

能否請你給我一個有效的方法/算法來做到這一點？

來源

2016-01-20 userit1985

你的'list2.contains（t）'會給你O（n * m）的複雜度。也許你可以選擇更快的遏制檢查，因爲列表的大小也是高度。 – lschuetze

您的列表沒有排序，所以任何操作需要搜索整個列表（或直到找到平均N/2）。
所以首先排序（Collections.sort()）所有列表，然後使用Collections.binarySearch()來查找是否包含該字符串。這隻需要（log N）而不是像以前那樣N/2。

來源

2016-01-20 20:37:26 AlexWien

哇！謝謝！ – userit1985

接受的anwser是好的，但仍然可以改進。你可以簡單地使用一個LinkedHashSet，這將使O（n）將數據轉儲到該集合中，並且每個O（1）包含操作。如果您的列表很大，這將有所幫助，但對於小型用戶，請使用排序。

如果您的列表中有重複的條目，您可能會得到一些意外的結果，因爲您的原始代碼將在結果中創建多個條目。在這種情況下，請使用Google Guava的LinkedHashMultiset之類的東西。如果你的班級路徑中沒有番石榴，如果你想要O（1）的搜索時間，你可能必須自己寫一個。

正如旁註，Collections.sort()將改變原來的列表。如果您以後需要原始訂單或者該列表以某種方式無法修改，則應該創建它的副本，在這種情況下，我認爲您應該嘗試設置，因爲它們需要花費相同的時間進行構建，並且使用更少的時間執行contains

來源

2016-01-21 02:25:48 glee8e

高效的方式來尋找最相似的名單<String>

回答

相關問題