顯着較慢的處理，因爲設置大小超過了500.000

我不習慣使用真正大的數據集，我在這裏難倒了。顯着較慢的處理，因爲設置大小超過了500.000

我有以下代碼：

private static Set<String> extractWords(BufferedReader br) throws IOException { 
    String strLine; 
    String tempWord; 
    Set<String> words = new HashSet<String>(); 
    Utils utils = new Utils(); 
    int articleCounter = 0; 
    while(((strLine = br.readLine()) != null)){ 
     if(utils.lineIsNotCommentOrLineChange(strLine)){ 
      articleCounter++; 
      System.out.println("Working article : " + utils.getArticleName(strLine) + " *** Article #" + articleCounter + " of 3.769.926"); 
      strLine = utils.removeURLs(strLine); 
      strLine = utils.convertUnicode(strLine); 
      String[] temp = strLine.split("\\W+"); 
      for(int i = 0; i < temp.length; i++){ 
       tempWord = temp[i].trim().toLowerCase(); 
       if(utils.validateWord(tempWord)){ 
        words.add(tempWord); 
        System.out.println("Added word " + tempWord + " to list"); 
       } 
      } 
     } 
    } 
    return words; 
}

這基本上得到從BufferedReader中，其中的每一行文本是從文章文本巨大的文本文件。我想在這個文本文件中列出唯一的單詞，但是其中有3.769.926條文章，因此單詞數量非常龐大。

從我對Sets或HashSet的理解來看，這應該是這個職業的人可以這麼說。一開始一切運轉都很順利，但是在500.000篇文章開始放緩之後。當它達到700.000時，它開始變得足夠慢，基本上在一秒鐘之後停止，然後再繼續。這裏有一個瓶頸，我看不到它是什麼..

任何想法？

來源

2013-12-20 Geir K.H.

哈希集由hashmaps支持，一旦你發展到一個很大的價值，它必須開始做它的數據的深層副本，以確保碰撞不會變得荒謬。高度的碰撞計數最終會使您的執行採集的時間線性化。如果您正確調整表格的大小，它將在內存和性能平穩的情況下更有效地運作 –

@GregGiacovelli只是爲了確保我理解您的建議;他應該使用HashSet（int initialCapacity）構造函數，其中initialCapacity相當高？可能甚至使用Integer.MAX_VALUE？ – DoubleDouble

你必須弄清楚你的需求和最佳效果。不知道這些對象有多大，但它可能也值得更改負載因子也不要太積極 –

我相信你可能面臨的問題是一個哈希表（集合或映射）必須由固定數量的條目支持。所以你的第一個聲明可能有一個表可以容納16個條目。拋開負載因素之類的東西，一旦你試圖將17個條目放入表中，就必須增加以適應更多的條目以防止發生衝突，所以Java會爲你擴展它。

此擴展包括使用2 * previousSize條目創建一個新表，然後複製舊條目。因此，如果您不斷擴大規模，您最終可能會遇到一個區域，例如 524,288，它將不得不擴大，但它會創建一個能夠處理1,048,576個條目的新表格，但它必須複製整個先前的表格。

如果您不介意額外的查找時間，您可以考慮使用TreeSet而不是HashSet。您的查找現在是對數時間，但Tree沒有預分配表，並且可以輕鬆地進行動態增長。要麼使用它，要麼聲明你的尺寸爲HashSet，這樣它就不會動態增長。

來源

2013-12-20 20:20:31 Nicholas

也可能會經常發生gc並導致緩慢。將堆大小增加到幾GB，並確保運行64位版本的Java。 –

正確。我從純粹的編程角度思考，但也可以通過JVM優化來加速。 – Nicholas

老實說，對於這種規模你最好轉到數據庫。如果您不想使用單獨的Derby，則可以將Derby嵌入您的應用程序中。

他們的索引系統針對這種規模進行了優化，而HashSet等可以應對，如果你按摩他們的權利，你最好使用正確的工具。

來源

2013-12-20 20:20:58

...並通過將每個單詞寫入數據庫來殺死速度？ –

@AmitSharma您可以將數據庫寫入緩衝到批處理中，這實際上會非常快。它還將允許您在填充下一個緩衝區時在單獨的線程中進行寫入。 –

如果您正在向Derby數據庫寫入全部內部相同的Java進程，那麼這麼快。 –

正如TheSageMage指出的那樣，隨着數據的增長，HashSet實現將不斷調整底層HashMap的大小。有幾種方法可以解決這個問題：初始容量和負載因數。您可以使用2-arg構造函數來設置：HashSet(int, float)。如果您知道需要的單詞的大概數量，則可以將初始容量設置爲大於該數字。這將使較小的地圖工作速度稍慢一些，但可以防止較大的地圖出現明顯的減速。負載因子是在增加底層大小重新散列之前，地圖必須滿足的程度。由於這對於大型地圖來說是一個相對耗時的操作，因此您可能希望將其設置爲0.9的很大一部分。如果您的初始容量設置爲可以超過此容量，但永遠不會超過此容量的兩倍，那麼大容量係數將確保您只會儘可能晚地重複使用。

來源

2013-12-20 20:36:29

顯着較慢的處理，因爲設置大小超過了500.000

回答

相關問題