什麼是比較大量字符串的最有效的算法？

讓我們2周字符串的ArrayList什麼是比較大量字符串的最有效的算法？

List<String> namesListA = new ArrayList<>(/*50 000 strings*/); 
List<String> namesListB = new ArrayList<>(/*400 000 strings*/);

RemoveAll方法似乎不工作。後：

namesListA.removeAll(namesListB);

namesListA.size（）仍然是50000編輯：輸入數據是不正確的，它的實際工作，但是需要很長的石灰。

我寫了下面的蠻力代碼：

boolean match; 
    for (String stringA: namesListA) 
    { 
     match = false; 
     for (String stringB: namesListB) 
     { 
      if (stringA.equals(stringB)) 
      { 
       match = true; 
       break; 
      } 
     } 
     if (!match) 
     { 
      finallist.add(stringA); 
     } 
    }

但它需要8小時才能完成。它有什麼已知的有效算法來搜索字符串？喜歡按字母順序對字符串進行排序，然後逐字或類似地搜索。

來源

2017-01-20 Paco de la Vega

你可以對這些列表進行排序，但這也會花費太多時間。這將有助於減少閱讀次數。然後你可以使用一些dychotomial搜索來再次減少它。但爲此，您需要對這些列表進行排序。有[Collections.sort]（https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#sort（java.util.List）） – AxelH

如果'removeAll' isn' t刪除任何，那麼這些列表沒有共同的字符串。 – khelwood

你確定removeAll不工作？ –

變量下面是爲O（n * LOGN）的解決方案。 應該比發佈的方法更快。編輯：如果你不需要確切的元素，我的另一種方法更快。

1）排序兩個列表

使用Collections.sort（...）進行有效排序在O（N * LOGN）。

2）用兩個迭代器

比較取兩個迭代器在兩個列表。然後：

while(leftIterator.hasNext() && rightIterator.hasNext(){ 
    int comparisonResult = leftElement.compare(rightElement); 
    if (comparisonResult == -1){ 
     leftElement = leftIterator.next(); 
    } 
    else if (comparisonResult == 1){ 
     rightElement = rightIterator.next(); 
    } 
    else{ 
     // found it! 
     return true; 
    } 
}

（很抱歉，如果我輸錯，不必在我手裏的IDE）

=>排序是O（我LOGI + J logj））

= >比較是O（I + J）

結果性能是有效地在類爲O（n * logn）時間。這應該很好。

來源

2017-01-20 09:30:36 LastFreeNickname

您也可以只對較小的結構'O（n * log（n））'進行排序，然後迭代未排序的結構以在排序後的結果中找到匹配'O（n *的log（n））'。 –

使用'Set'可以得到線性時間複雜度，這比n好* logn – radoh

它看起來像是假設元素實現了'Comparable'，這是合理的，但調用的正確方法是compare（）。此外，應該測試compare（）的結果小於或大於零，不等於1或-1。 –

一種可能性是平行移除。列表namesListA和namesListB可以按起始字符分組;那麼刪除可以並行進行並且可以將結果列表再次連接。

假設一些標準的拉丁字母，這將導致大約26個組可以並行處理。如果4個線程可以並行運行，我會期待顯着的加速。

來源

2017-01-20 08:45:01 Codor

他剛纔提到的字符串，String可以是任何字面的起始字符 - How我們可以假設它只是字母表？。雖然它說名稱列表，它可以是任何'事物'的名稱。 –

在這個特殊的例子中，字符串是名字，只能包含字母。 –

使用第一個「char」值，這仍然是一個數字，更多的組，但這個想法仍然有效。使用Map存儲創建的不同組，並且您可以在每個組上啓動Thread。 – AxelH

您可以將列表namesListB的元素放入新的Set（最好是HashSet）。然後，它是更有效的調用namesListA.removeAll(setFromListB);，由於ArrayList.removeAll的實現調用Collection.contains()這在Set（HashSet）比在ArrayList有效得多（HashSet.contains()具有恆定的時間性能，同時具有ArrayList.contains()線性性能）。

無論如何，namesListA.removeAll(namesListB);應該工作，如果namesListA不改變，那麼2列表沒有共同的元素。的時間複雜度

估計（N = namesListA.length，M = namesListB.length）：
創建HashSet從namesListB：O（M）
調用namesListA.removeAll(setListB)：O（N * 1）= O（N）
在總：O（M + N）（這可以寫成O（M），因爲M> N，但我不知道）

來源

2017-01-20 08:51:37 radoh

理想情況下，這應該很好.. namesListA.removeAll（namesListB）;不是嗎？ –

@SrikanthA你讀過我的*全*答案嗎？我在最後一段提到了這一點。 – radoh

我的意思是直接列表removeAll作爲最好的算法。考慮到，您正在將400k列表轉換爲集合（其內部包含集合，同時添加到集合），並且您正在執行removeall操作。 –

我會建議使用HashSet而不是一個的存儲String S中的最大集合，以便知道集合中是否包含或不特定String與O(1)代替O(n)一個時間複雜度，然後用removeAll(Collection<?> c)只保留String S中的不是第二集合中下一步：

List<String> namesListA = new ArrayList<>(/*50 000 strings*/); 
Set<String> namesSetB = new HashSet<>(/*400 000 strings*/); 
namesListA.removeAll(namesSetB);

來源

2017-01-20 08:51:52

爲namesListB中的40萬個名稱創建一組。然後使用此設置刪除不需要的元素namesListA。

List<String> namesListA = new ArrayList<>(/*50 000 strings*/); 
List<String> namesListB = new ArrayList<>(/*400 000 strings*/); 

Set<String> undesiredNames = new HashSet<>(namesListB); 

for (String name : namesListA) { 
    if (undesiredNames.contains(name)) { 
     namesListA.remove(name); 
    } 
}

來源

2017-01-20 08:54:10

做的removeAll的名單可能是一個更好的解決方案，考慮到你同時擁有與50K和400K大小的列表

namesListA.removeAll(namesListB);

來源

2017-01-20 09:18:13

如果不重要的是哪個元素是重複的，但只有如果有任何你可以讓集合爲你做的伎倆。

int sizeA = listA.size(); 
int sizeB = listB.size(); 

Set merger = new HashSet((sizeA+sizeB)*someLoadFactor); 
merger.addAll(listA); 
merger.addAll(listB); 
// Sets do not contain duplicates! 

if (merger.size() < sizeA + sizeB){ 
    return true; 
} 
return false;

這個運行在O（I + J），從而有效地爲O（n）！

來源

2017-01-20 09:44:43 LastFreeNickname

什麼是比較大量字符串的最有效的算法？

回答

相關問題