Значительная медленная обработка в виде заданного размера превышает 500 000

Question

Я не привык к работе с действительно большими наборами данных, и я здесь как бы неспокойный.

У меня есть следующий код:

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 статей, поэтому количество слов довольно велико.

Из того, что я понимаю о наборах или, в частности, HashSets, это должен быть человек для работы, так сказать. Сначала все работает довольно гладко, но после 500 000 статей он немного замедляется. Когда он достигает 700 000, его начало становится настолько медленным, что оно в основном останавливается на секунду из двух, прежде чем продолжить. Там где-то есть узкое место, и я не вижу, что это такое.

Любые идеи?

Answer 1

Я считаю, что проблема, с которой вы можете столкнуться, заключается в том, что хэш-таблица (набор или карта) должна поддерживаться фиксированным количеством записей, которые она может удерживать. Таким образом, ваше первое объявление может иметь таблицу, в которой можно хранить 16 записей. Отложив в сторону вещи, такие как факторы нагрузки, как только вы попытались поместить 17 записей в таблицу, она должна расти, чтобы разместить больше записей для предотвращения конфликтов, поэтому Java расширит ее для вас.

Это расширение включает в себя создание новой таблицы с записями 2 * previousSize, а затем копирование по старым записям. Поэтому, если вы постоянно расширяетесь, вы можете попасть в область, например, 524,288, где ей придется расти, но она создаст новую таблицу, способную обрабатывать 1 048 576 записей, но ее придется скопировать по всей предыдущей таблице.

Если вы не против дополнительного времени поиска, вы можете подумать об использовании TreeSet вместо HashSet. Теперь поиск будет логарифмическим, но Tree не имеет предварительно выделенной таблицы и может динамически развиваться. Либо используйте это, либо объявите размер вашего HashSet, чтобы он не динамически развивался.

Answer 2

Честно говоря, для такого масштаба вам лучше перейти к базе данных. Вы можете вставлять Derby в ваше приложение, если вы не хотите использовать отдельный.

Их системы индексирования оптимизированы для такого масштаба, и в то время как HashSet и т. Д. Справятся, если вы массируете их правильно, вам лучше использовать подходящий инструмент для этого.

Answer 3

Как отмечено TheSageMage, реализация HashSet будет постоянно изменять размер базового HashMap по мере роста данных. Есть несколько способов обойти это: начальная емкость и коэффициент нагрузки. Вы можете установить оба варианта с помощью конструктора 2-arg: HashSet(int, float). Если вы знаете приблизительное количество слов, которые вам понадобятся, вы можете установить начальную емкость, которая будет больше, чем это число. Это приведет к тому, что меньшие карты будут работать немного медленнее, но предотвратит резкое замедление для больших карт. Коэффициент загрузки - это то, как должна заполняться карта, прежде чем увеличивать переопределение базового размера. Поскольку это относительно трудоемкая операция для больших карт, вы можете установить ее на большую долю, скажем, 0,9. Если ваша первоначальная емкость была установлена ​​так, чтобы вы могли ее превысить, но никогда не превысите вдвое больше этого размера, большой коэффициент загрузки гарантирует, что вы перефразируете только один раз и как можно позже.