文字列を検索するためのより速いデータ構造

Question

word（大文字と小文字を区別しない）がwordListテキストファイルに含まれているかどうかを判断するこのコードがあります。しかし、wordListのテキストファイルには65000 ++の行があり、以下の実装を使って単語を検索するだけで約1分かかります。より良い実装について考えてみてください。

ありがとうございます！

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

public class WordSearch 
{ 
    LinkedList<String> lxx; 
    FileReader fxx; 
    BufferedReader bxx; 

    public WordSearch(String wordlist) 
     throws IOException 
    { 
     fxx = new FileReader(wordlist); 
     bxx = new BufferedReader(fxx); 
     lxx = new LinkedList<String>(); 
     String word; 

     while ((word = bxx.readLine()) != null) 
      { 
      lxx.add(word); 
     } 

     bxx.close(); 
    } 

    public boolean inTheList (String theWord) 
    { 
     for(int i =0 ; i < lxx.size(); i++) 
      { 
      if (theWord.compareToIgnoreCase(lxx.get(i)) == 0) 
        { 
       return true; 
      } 
     } 

     return false; 
    } 
} 

Answer 1

HashSetを使用して、各単語の小文字を入れてください。 HashSetに指定された文字列が含まれているかどうかをチェックするのは、平均して一定時間（読み込み：超高速）です。

Answer 2

検索しているので、検索する前にリストを並べ替えることを検討してください。線形検索よりもはるかに高速なバイナリ検索を行うことができます。これは、同じリストで複数の検索を実行する場合に役立ちます。そうしないと、リストをソートするために支払うペナルティは、一度だけ検索する価値がありません。

また、 "lxx.get（i）"を使用してリンクリストで線形検索を実行すると、問題が発生することがあります。 LinkedList.get（）はO（n）です。 Iterator（簡単な方法：for（String s：lxx））を使用するか、ArrayListなどのO（1）アクセス時間を持つリストタイプに切り替えることができます。

Answer 3

O（n）操作ではそれぞれlで検索しますので、数千語の単語がある場合は非常にコストがかかるでしょう。代わりに、HashSetを使用します。その後、

Set<String> lxx; 

... 

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

と単語がファイルであるかどうかを確認するためにlxx.contains(theWord.toLowerCase())を使用しています。 HashSetの各ルックアップはO（1）操作なので、ファイルサイズの（ほぼ）独立しています。

Answer 4

まず第一に、リストすることを宣言し、LinkedListのようにあなたの変数を宣言しません（削除されたリストと心配していないコードの一部：

public class WordSearch 
{ 
    List<String> lxx; 

    public WordSearch(String wordlist) 
     throws IOException 
    { 
     lxx = new LinkedList<String>(); 
    } 
} 

次はアップに乗る呼び出すことはありませんリストには、LinkedListのを使用すると、非常に遅くなります代わりにイテレータを使用して...いっそあなたのためのイテレータを使用してループのための新たなstypeの使用：。

public boolean inTheList (String theWord) 
    { 
     for(String word : lxx) 
     { 
      if (theWord.compareToIgnoreCase(word) == 0) 
      { 
       return true; 
      } 
     } 

     return false; 
    } 

を次に新しいArrayListに新しいLinkedListのを変更します：

lxx = new ArrayList（）;

このコードは高速である必要がありますが、それでも改善は可能です。

重複する単語を気にしないので、リストの代わりにセットを使用し、ArrayListの代わりにHashSetを使用します。

これを行うと、プログラムが大幅に高速化されます。

getでLinkedListを使用しているオリジナルのコードは、リストの次の単語を検索するたびにリストの先頭からやり直さなければなりません。 Iteratorを（新しいスタイルfor-eachループを介して）使用すると、それが起こらなくなります。

LinkedListを使用すると、リスト内の次の単語に移動するたびに検索が行われるため、ArrayListにはそのオーバーヘッドがありません。

HashSetを使用すると、非常に高速なルックアップを持つツリー構造を使用して（おそらく）表示されます。

Answer 5

私の実装は50ミリ秒未満で検索しています。

まず、ファイルを読み込んでメモリに保存しておく必要があります。

あなたはそれを読み込むことができますが、大きなチャンクで読み込んだ方が簡単です。

私の入力は、私が使用し、大きなファイルにリストを作成するには

（HTMLをダウンロードして、すべてのHTMLページのうち1つのファイルを作成します）byte into python book（HTML、単一のファイルのバージョンをダウンロードした）とJava language specificationましたこの同じプログラム（コメントされたコードを参照）。私はおよそ300K言葉で大きなファイルを持っていたら

は、私はこの出力を使用してプログラムを実行した：50ミリ秒の下で常に

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 

。

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 "); 

     } 
    } 

難しい部分は、サンプル入力を取得することでした：

は、ここでは、コードですP

Answer 6

時間がないのHashMapのリターンを使用して、何を推測：

は修正版ですし、常に0ミリ秒で終了します。

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

    class WordSearch { 
     String inputFile; 
     //List<String> words; 
     Set<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 HashSet<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()); 
     } 

     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 "); 

     } 
    } 

今、私は確かに知って:)

Answer 7

2つの提案： 両方のデータ構造は、あなたのパフォーマンスが向上します。

1. 有向非循環単語グラフ（DAWG）
2. 辞書データ構造。 n-tree