Iterate attraverso solo parte di un grande elenco in java

Question

Sto provando a creare un gioco Boggle in Java, e per il mio programma una volta che ho randomizzato la scheda ho un metodo che scorre le possibili combinazioni e confronta ognuna con un elenco di dizionari per verificare se si tratta di una parola valida e, in caso affermativo, inserirla nella chiave. Funziona bene, tuttavia il programma impiega tre o quattro minuti per generare la chiave, che è principalmente dovuta alla dimensione del dizionario. Quello che sto usando ha circa 19k parole e il confronto di ogni combinazione richiede un sacco di tempo. Ecco la parte del codice che sto cercando di rendere più veloce:

if (str.length()>3&&!key.contains(str)&&prefixes.contains(str.substring(0,3))&&dictionary.contains(str)){ 
     key.add(str); 
    } 

dove str viene generata la combinazione. prefixes è una lista che ho generato in base dictionary che va come questo:

public void buildPrefixes(){ 
    for (String word:dictionary){ 
     if(!prefixes.contains(word.substring(0,3))){ 
      prefixes.add(word.substring(0,3)); 
     } 
    }  
} 

che aggiunge solo tutti e tre i prefissi lettera nel dizionario come "abb" e "mar" in modo che quando str è jibberish come "xskfjh "Non verrà controllato contro l'intero dizionario, solo prefixes, che è qualcosa come 1k parole.

Quello che sto cercando di fare è ridurre il tempo scorrendo solo le parole del dizionario che hanno lo stesso prima lettera come str, quindi se str è "Abbey" allora controllerà solo str contro parole che iniziare con "a" anziché l'intera lista, che ridurrebbe in modo significativo il tempo. O ancora meglio, controlla solo str contro parole che hanno lo stesso prefisso. Sono abbastanza nuovo in Java, quindi sarei davvero grato se sei molto descrittivo nelle tue risposte, grazie!

Answer 1

Quali commenti stanno cercando di dire è - non reinventare ruota. Java non è Assembler o C ed è abbastanza potente da gestire questi casi banali. Ecco semplice codice che mostra come semplice insieme in grado di gestire il vostro vocabolario facile:

import java.util.Set; 
import java.util.TreeSet; 

public class Work { 

    public static void main(String[] args) { 
     long startTime=System.currentTimeMillis(); 
     Set<String> allWords=new TreeSet<String>(); 
     for (int i=0; i<20000;i++){ 
      allWords.add(getRandomWord()); 
     } 
     System.out.println("Total words "+allWords.size()+" in "+(System.currentTimeMillis()-startTime)+" milliseconds"); 

    } 

    static String getRandomWord() { 
     int length=3+(int)(Math.random()*10); 
     String r = ""; 
     for(int i = 0; i < length; i++) { 
      r += (char)(Math.random() * 26 + 97); 
     } 
     return r; 
    } 
} 

Sul mio computer che mostra

Total words 19875 in 47 milliseconds 

Come si può vedere 125 parole di 20.000 sono stati duplicati. E non è stato solo il tempo di generare 20.000 parole in modo molto inefficiente, ma memorizzarle e controllare i duplicati.