Structure de données plus rapide pour rechercher une chaîne

Question

J'ai ce code qui détermine si un mot (cas ignorant) est inclus dans un fichier texte wordList. Cependant, le fichier texte wordList peut avoir 65000 ++ lignes, et juste chercher un mot en utilisant ma mise en œuvre ci-dessous prend près d'une minute. Pouvez-vous penser à une meilleure mise en œuvre?

Merci!

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

Utilisez un HashSet dans lequel vous mettez une version en minuscule de chaque mot. Vérifier si une chaîne spécifiée contient HashSet est, en moyenne, une opération à temps constant (lire: extrêmement rapide).

Answer 2

Puisque vous êtes à la recherche, vous pouvez vouloir trier la liste avant de chercher; alors vous pouvez faire une recherche binaire qui est beaucoup plus rapide que la recherche linéaire. Cela peut vous aider si vous effectuez plusieurs recherches sur la même liste, sinon la pénalité que vous payez pour trier la liste ne vaut pas la peine de la rechercher une seule fois. De plus, effectuer une recherche linéaire sur une liste chaînée à l'aide de «lxx.get (i)» demande des problèmes. LinkedList.get() est O (n). Vous pouvez soit utiliser un Iterator (moyen simple: pour (String s: lxx)), soit passer à un type de liste ayant un temps d'accès O (1), tel que ArrayList.

Answer 3

Chaque recherche par l dans une opération O (n), donc cela sera très coûteux lorsque vous avez des milliers de mots. Au lieu de cela, utilisez un HashSet:

Set<String> lxx; 

... 

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

puis utilisez lxx.contains(theWord.toLowerCase()) pour vérifier si le mot est dans le fichier. Chaque recherche dans le HashSet est une opération O (1), donc le temps qu'il faut est (presque) indépendant de la taille de votre fichier.

Answer 4

Tout d'abord, ne pas déclarer votre variable être un LinkedList, déclarer être une liste (parties du code ne concernent pas la liste supprimé:

public class WordSearch 
{ 
    List<String> lxx; 

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

Ensuite ne pas appeler à obtenir la liste, en utilisant un get LinkedList sera très lent utiliser plutôt une iterator ... mieux utiliser encore la nouvelle sType boucle qui utilise un itérateur pour vous.

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

     return false; 
    } 

Suivant changer la nouvelle LinkedList à une nouvelle ArrayList :

lxx = new ArrayList();

Ce code devrait être plus rapide, mais vous pouvez toujours faire mieux. Puisque vous ne vous souciez pas des mots en double, utilisez Set au lieu d'une liste et utilisez un HashSet au lieu d'un ArrayList.

Ceci accélèrera considérablement le programme.

Votre code original, en utilisant LinkedList avec get, doit recommencer au début de la liste chaque fois que vous recherchez le mot suivant dans la liste. L'utilisation de l'Iterator (via le nouveau style pour chaque boucle) empêche que cela se produise. L'utilisation d'une LinkedList signifie que chaque fois que vous devez passer au mot suivant dans la liste, une recherche est nécessaire, ArrayList n'a pas cette surcharge.

L'utilisation d'un HashSet se termine (probablement) en utilisant une structure arborescente qui a des recherches très rapides.

Answer 5

Voici ma mise en œuvre de recherche de moins de 50 ms.

Vous devez d'abord charger le fichier et le garder en mémoire.

Vous pouvez le charger comme vous voulez, mais si vous l'avez chargé en gros morceaux, ce sera plus facile.

Mon entrée a été le byte into python book (téléchargé la seule version du fichier HTML) et le Java language specification (téléchargé le code html et créer un fichier unique de toutes les pages html)

Pour créer la liste dans un grand fichier je ce même programme (voir le code commenté).

Une fois que j'ai un gros fichier avec environ 300k mots, je courais le programme avec cette sortie:

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 

toujours moins de 50 ms.

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

     } 
    } 

La partie la plus difficile était d'obtenir une entrée de l'échantillon: P

Answer 6

Devinez quoi, en utilisant un rendement de HashMap en un rien de temps:

est ici la version modifiée et ça finit toujours en 0 ms.

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

     } 
    } 

Maintenant je sais sûr :)

Answer 7

deux suggestions: Les deux structures de données vous donnent une meilleure performance.

1. graphe orienté acyclique mot (DAWG)
2. structure de données dictionnaire. n-tree