Более быстрая структура данных для поиска строки

Question

У меня есть этот код, который определяет, включено ли слово (без учета регистра) в текстовый файл wordList.Тем не менее, текстовый файл wordList может иметь 65000 ++ строк, и просто поиск слова с использованием моей реализации ниже занимает около минуты.Не могли бы вы придумать лучшую реализацию?

Спасибо!

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). Вы можете использовать итератор (простой способ: for (String s: lxx)) или переключиться на тип списка с временем доступа O (1), например ArrayList.

Answer 3

два предложения: обе структуры данных обеспечивают лучшую производительность.

1. Направленный ациклический граф слов (DAWG)
2. Структура словарных данных.н-дерево

Answer 4

Угадайте, что, используя 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 5

Вот моя реализация поиска менее 50 мс.

Сначала вы должны загрузить файл и сохранить его отсортированным в памяти.

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

Мой ввод был байт в книгу Python (скачал версию HTML с одним файлом) и Спецификация языка Java (скачал html и создал один файл из всех html-страниц)

Чтобы создать список в большом файле, я использовал эту же программу (см. Закомментированный код).

Получив большой файл с 300 тыс. Слов, я запустил программу с таким выводом:

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

Всегда менее 50 мс.

Вот код:

   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:  /285483/kak-mne-sozdat-stroku-java-iz-soderzhimogo-faila#285486 
        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

Прежде всего, не объявляйте вашу переменную списком LinkedList, объявляйте его списком (части кода, не относящиеся к списку, удалены:

public class WordSearch 
{
    List<String> lxx;

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

Далее не вызывайте get в списке, использование LinkedList будет ОЧЕНЬ медленным. Вместо этого используйте итератор ... еще лучше используйте новый стиль для цикла, который использует итератор для вас:

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

        return false;
    }

Затем измените новый LinkedList на новый ArrayList:

lxx = new ArrayList ();

Этот код должен быть быстрее, но вы все равно можете сделать лучше.

Поскольку вас не волнуют повторяющиеся слова, используйте Set вместо List и используйте HashSet вместо ArrayList.

Это значительно ускорит программу.

Ваш оригинальный код, использующий LinkedList с get, должен начинаться с начала списка каждый раз при поиске следующего слова в списке. Использование Итератора (с помощью нового стиля для каждого цикла) останавливает это.

Использование LinkedList означает, что каждый раз, когда вам нужно перейти к следующему слову в списке, происходит поиск, ArrayList не имеет таких издержек.

Использование HashSet завершается (вероятно) использованием древовидной структуры, которая имеет очень быстрый поиск.

Answer 7

Каждый поиск по l в операции O (n), так что это будет довольно дорого, если у вас есть тысячи слов. Вместо этого используйте 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), поэтому время, которое он занимает, (почти) не зависит от размера вашего файла.