Могу ли я получить более высокую производительность для этого цикла?

Question

Я читаю книгу и удаляю несколько слов из нее. Моя проблема заключается в том, что этот процесс занимает много времени, и я хочу, чтобы его производительность лучше (меньше времени), например:

Vector<String> pages = new Vector<String>(); // Contains about 1500 page, each page has about 1000 words. 
Vector<String> wordsToDelete = new Vector<String>(); // Contains about 50000 words. 

for(String page: pages) { 
    String pageInLowCase = page.toLowerCase(); 

    for(String wordToDelete: wordsToDelete) { 
     if(pageInLowCase.contains(wordToDelete)) 
      page = page.replaceAll("(?i)\\b" + wordToDelete + "\\b" , ""); 
    } 

    // Do some staff with the final page that does not take much time. 
} 

Этот код занимает около 3 минут, чтобы выполнить. Если я пропустил цикл replaceAll (...) Я могу сэкономить более 2 минут. Итак, есть ли способ сделать тот же цикл с более высокой производительностью?

Answer 1

Для начала, вы можете избавиться от проверки contains(..). Он добавляет ненужные накладные расходы. И это вернет истину иногда, когда это не так. Например, он вернет true для «не», даже если на странице есть только «узел».

Другое дело - заменить Vector на ArrayList.

И как указал Конрад в своем комментарии - вы не меняете векторы. String неизменен, поэтому вы не меняете объекты. Вам нужно будет использовать set(..) (и поддерживать индекс итерации).

Answer 2

Да, вы можете обрабатывать страницу по-другому. Основная идея следующая

for (String word : page) { 
    if (!forbiddenWords.contains(word)) { 
     pageResult.append(word); 
    } 
} 

Здесь forbiddenWords представляет собой набор.
Кроме того, for (String word : page) является сокращением для разбора страницы в список слов. Не забудьте добавить лишние пробелы (я пропустил это для ясности).

Сложность обработки одной страницы в оригинальной версии была ~ 50000 * 1000, а теперь это всего ~ 1000. (Проверка, если слово в HashSet занимает постоянное время)

редактировать
Так как я хотел, чтобы отвлечь себя от работы в течение десяти минут, вот код :)

String text = "This is a bad word, and this is very bad, terrible word."; 
    Set<String> forbiddenWords = new HashSet<String>(Arrays.asList("bad", "terrible")); 

    text += "|"; // mark end of text 
    boolean readingWord = false; 
    StringBuilder currentWord = new StringBuilder(); 
    StringBuilder result = new StringBuilder(); 

    for (int pos = 0; pos < text.length(); ++pos) { 
     char c = text.charAt(pos); 
     if (readingWord) { 
      if (Character.isLetter(c)) { 
       currentWord.append(c); 
      } else { 
       // finished reading a word 
       readingWord = false; 
       if (!forbiddenWords.contains(currentWord.toString().toLowerCase())) { 
        result.append(currentWord); 
       } 

       result.append(c); 
      } 
     } else { 
      if (Character.isLetter(c)) { 
       // start reading a new word 
       readingWord = true; 
       currentWord.setLength(0); 
       currentWord.append(c); 
      } else { 
       // append punctuation marks and spaces to result immediately 
       result.append(c); 
      } 
     } 
    } 

    result.setLength(result.length() - 1); // remove end of text mark 
    System.out.println(result); 

Answer 3

Использование java.lang.StringBuilder - он создан специально для измененного текста.

StringBuilder builder = new StringBuilder(page); 
for (String word: wordsToDelete) { 
    int position = 0; 
    int newpos = 0; 
    while ((newpos = builder.indexOf(word, position))>=0) { 
     builder.delete(position, position+word.length()); 
     position = newpos; 
    } 
} 

Это просто идея - это не проверяет границы слов

Answer 4

Проблема в том, у вас есть двойной цикл. Это, как правило, низкая производительность и приравнивается к производительности x * y. Кроме того, поскольку строки не могут быть изменены каждый раз, когда вы вызываете toLowerCase, а затем replaceAll, вы создаете новую строку. Таким образом, вы создаете x * y число строк, содержащих целую страницу для каждого слова в вашем списке. Этого можно избежать, используя опции MULTI_LINE и CASE_INSENSITIVE в регулярном выражении.

Вы можете уменьшить его до одного цикла и использовать регулярное выражение для замены всех слов одновременно.

StringBuffer buffer = new StringBuffer(); 
    for (String word : wordsToDelete) { 
     if (buffer.length() != 0) { 
      buffer.append("|"); 
     } 
     buffer.append("(\\b"); 
     buffer.append(word); 
     buffer.append("\\b)"); 
    } 

    Pattern pattern = Pattern.compile(buffer.toString(), Pattern.CASE_INSENSITIVE | Pattern.MULTILINE); 

    List<String> newPageList = new ArrayList<String>(); 

    for (String page : pages) { 
     Matcher matcher = pattern.matcher(page); 
     String newPage = matcher.replaceAll(""); 
     newPageList.add(newPage); 
    } 

Answer 5

Предполагая, что страницы являются независимыми, и если у вас есть несколько ядер вокруг, и у вас есть много страниц для обработки, этот цикл может быть распараллеливание, а также:

final ArrayList<String> pages = ...; 
final Set<String> wordsToDelete = ...; 
final ExecutorService pageFrobber = Executors.newFixedThreadPool(8); //pick suitable size 
final List<Callable<String>> toFrobPages = new ArrayList<Callable<String>>(pages.size()); 

for(final String page: pages) { 
    toFrobPages.add(new Callable<String>() { 
     String call() { 
     return page.toLowerCase().replaceAll("(?i)\\b" + wordToDelete + "\\b" , ""); 
     } 
    }); 
} 

final List<Future<String>> frobbedPages = pageFrobber.executeAll(toFrobPages); 
// the above will block until all pages are processed 
// frobbedPages will contain a set of Future<String> which can be converted to strings 
// by calling get()