Schneller Datenstruktur für das suchen nach einem string

Verwenden HashSet in dem du eine Kleinbuchstaben-version von jedem Wort. Überprüfen, ob ein HashSet enthält eine angegebene Zeichenfolge ist, im Durchschnitt eine Konstante Zeit (gelesen: extrem schnell) - operation.

Jeder Suche durch l in O(n) - operation, also das wird ziemlich teuer, wenn Sie haben Tausende von Worten. Verwenden Sie stattdessen eine HashSet:

Set<String> lxx;

...

lxx = new HashSet<String>();
while ( (word = bxx.readLine()) != null) {
        lxx.add(word.toLowerCase());
}
bxx.close();

und verwenden Sie dann lxx.contains(theWord.toLowerCase()) um zu überprüfen, ob das Wort in der Datei.
Jede Suche in der HashSet ist eine O(1) operation, so dass die Zeit es dauert, ist (fast) unabhängig von der Größe der Datei.

Hier ist meine Umsetzung suchen unter 50 ms.

Zuerst müssen Sie zum laden der Datei und halten Sie Sie sortiert in Erinnerung.

Können Sie laden Sie es wie Sie wollen, aber wenn Sie es geladen hat, in große Stücke leichter.

Mein input war der byte in python-Buch ( Download der HTML-single-file-version ) und die Java language specification ( Download der html-und eine einzelne Datei erstellen, aus der alle html-Seiten )

Erstellen Sie die Liste in eine große Datei, die ich verwendet dieses Programm ( siehe code auskommentiert ).

Sobald ich eine große Datei mit über 300k Worten, ich lief das Programm mit dieser Ausgabe:

C:\Users\oreyes\langs\java\search>dir singlelineInput.txt
 El volumen de la unidad C no tiene etiqueta.
 El número de serie del volumen es: 22A8-203B

 Directorio de C:\Users\oreyes\langs\java\search

04/03/2011  09:37 p.m.         3,898,345 singlelineInput.txt
               1 archivos      3,898,345 bytes

C:\Users\oreyes\langs\java\search>javac WordSearch.java

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "great"
Loaded 377381 words in 2844 ms
true
in 31 ms

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "great"
Loaded 377381 words in 2812 ms
true
in 31 ms

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "awesome"
Loaded 377381 words in 2813 ms
false
in 47 ms

C:\Users\oreyes\langs\java\search>gvim singlelineInput.txt

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "during"
Loaded 377381 words in 2813 ms
true
in 15 ms

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "specification"
Loaded 377381 words in 2875 ms
true
in 47 ms

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "<href"
Loaded 377381 words in 2844 ms
false
in 47 ms

C:\Users\oreyes\langs\java\search>java WordSearch singlelineInput.txt "<br>"
Loaded 377381 words in 2829 ms
true
in 15 ms

Immer unter 50 ms.

Hier der code:

   import java.io.*;
   import java.util.*;

   class WordSearch {
       String inputFile;
       List<String> words;
       public WordSearch(String file ) { 
           inputFile = file;
       }
       public void initialize() throws IOException { 
           long start = System.currentTimeMillis();
           File file = new File( inputFile );
           ByteArrayOutputStream baos = new ByteArrayOutputStream(( int ) file.length());
           FileInputStream in = new FileInputStream( file );
           copyLarge( in, baos, (int)file.length() );

           Scanner scanner = new Scanner( new ByteArrayInputStream(  baos.toByteArray() ));
           words = new LinkedList<String>();
           while( scanner.hasNextLine() ) { 
              String l = scanner.nextLine().trim();
              //for( String s : l.split("\\s+")){
                //System.out.println( s );
                words.add( l.toLowerCase() );
              //}
           }

           Collections.sort( words );
           for( String s : words ) { 
               //System.out.println( s );
           }
           System.out.println("Loaded " + words.size() + " words in "+  ( System.currentTimeMillis() - start ) + " ms"  );
       }

       public boolean contains( String aWord ) { 
           return words.contains( aWord.toLowerCase() );
       }
        //taken from:  http://stackoverflow.com/questions/326390/how-to-create-a-java-string-from-the-contents-of-a-file/326413#326413 
        public static long copyLarge(InputStream input, OutputStream output, int size )
               throws IOException {
           byte[] buffer = new byte[size];//something biggie 
           long count = 0;
           int n = 0;
           while (-1 != (n = input.read(buffer))) {
               output.write(buffer, 0, n);
               count += n;
           }
           return count;
       }
       public static void main( String ... args ) throws IOException  { 
           WordSearch ws = new WordSearch( args[0] );
           ws.initialize();
           long start = System.currentTimeMillis();
           System.out.println( ws.contains( args[1] ) );
           System.out.println("in "+  ( System.currentTimeMillis() - start ) +" ms ");

       }
    }

Der schwierige Teil war, um ein Beispiel für die Eingabe 😛

zwei Vorschläge:
Beide Datenstrukturen geben Sie eine bessere Leistung.

1. Directed acyclic word graph (DAWG)
2. Dictionary-Datenstruktur. n-tree