Kann ich eine schnellere Leistung für diese Schleife haben?

Question

Ich lese ein Buch und lösche eine Reihe von Wörtern daraus. Mein Problem ist, dass der Prozess lange Zeit in Anspruch nimmt, und ich will seine Leistung besser (weniger Zeit), Beispiel machen:

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. 
} 

Dieser Code dauert etwa 3 Minuten durchzuführen. Wenn ich die Schleife von replaceAll (...) überspringe kann ich mehr als 2 Minuten speichern. Gibt es also eine Möglichkeit, die gleiche Schleife mit einer schnelleren Leistung zu machen?

Answer 1

Zunächst einmal können Sie die contains(..) Überprüfung loswerden. Es fügt unnötigen Overhead hinzu. Und manchmal wird es wahr, wenn das nicht der Fall ist. Zum Beispiel gibt es true für "nicht" zurück, auch wenn es nur "Knoten" auf der Seite gibt.

Eine andere Sache - ersetzen Vector durch ArrayList.

Und wie Konrad in seinem Kommentar angedeutet hat - ändern Sie nicht die Vektoren. String ist unveränderlich, also ändern Sie die Objekte nicht. Sie müssten set(..) verwenden (und einen Iterationsindex beibehalten).

Answer 2

Ja, Sie können die Seite auf andere Weise bearbeiten. Die Grundidee ist folgende

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

Hier forbiddenWords ein Satz ist.
for (String word : page) ist auch eine Abkürzung für das Parsen der Seite in eine Liste von Wörtern. Vergessen Sie nicht, auch Leerzeichen hinzuzufügen (ich überspringe das zur besseren Übersicht).

Die Komplexität der Verarbeitung einer Seite in der ursprünglichen Version war ~ 50000 * 1000, während es jetzt nur ~ 1000 ist. (Prüfen, ob Wort in HashSet ist benötigt konstante Zeit)

bearbeiten
Da wollte ich mich zehn Minuten lang von der Arbeit abzulenken, hier ist der Code :)

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

Verwenden java.lang.StringBuilder - es ist speziell erstellt für modifizierten Text.

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; 
    } 
} 

Es ist nur die Idee - es ist nicht für Wortgrenzen überprüft

Answer 4

Das Problem ist, dass Sie für Schleife ein Doppel haben. Dies ist im Allgemeinen eine schlechte Leistung und entspricht der x * y-Leistung. Da Strings auch nicht jedes Mal geändert werden können, wenn Sie toLowerCase und dann replaceAll aufrufen, erstellen Sie eine neue Zeichenfolge. Sie erstellen also eine x * y-Anzahl von Strings, die für jedes Wort in Ihrer Liste eine ganze Seite enthalten. Dies kann mit den Optionen MULTI_LINE und CASE_INSENSITIVE in einer Regex vermieden werden.

Sie können es auf eine Schleife reduzieren und Regex verwenden, um alle Wörter auf einmal zu ersetzen.

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

die Seiten sind unabhängig, Unter der Annahme, und wenn Sie um mehrere Kerne haben, und Sie haben eine Menge Seiten bekam zu verarbeiten, könnte diese Schleife auch parallelisiert werden:

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()