在Java中遍历一个大列表的部分

Question

我正在用Java制作“波格尔”游戏。在我的程序中，一旦我随机生成了游戏板，我有一个方法来遍历所有可能的字母组合，并将每个组合与单词词典列表进行比较，以检查是否是有效的单词，如果是，就将其放入关键字里面。这个方法运行良好，但程序需要花费三到四分钟的时间来生成关键字，这主要是由于单词词典的大小所致。我使用的词典约有19,000个单词，每次比较每个组合都需要很长时间。以下是我试图加速的代码部分：

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

其中str是生成的组合。 prefixes是我基于dictionary生成的列表，如下所示：

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

这个代码会在字典中添加所有的三个字母前缀，例如"abb"和"mar"，这样当str是类似于"xskfjh"这样的无意义字符串时，它就不会被与整个字典进行比较，而只会与prefixes进行比较，后者大约有1k个单词。

我的目的是通过仅迭代与str具有相同首字母的单词来缩短时间，因此如果str是"abbey"，则它只会检查以"a"开头的单词，而不是整个列表，这将显著缩短时间。或者更好的是，它只会检查具有相同前缀的单词。我对Java还很新，所以如果您的答案非常详细，我会非常感激，谢谢！

- Ham Lingo

---

看起来你可能想使用Map<Letter, List<Word>>或类似的东西。这将把你的搜索分成26个块，并加快搜索速度。但你可能正在寻找一种有效地构建和搜索图形的方法。 - David Brossard

在谷歌搜索时发现了这个... http://www.wutka.com/dawg.html 有趣的东西。 - David Brossard

你正在尝试重新发明 Trie。 - AdamSkywalker

为什么不直接使用一个简单的 Set 呢？我有漏掉什么吗？ - Sergei Tachenov

Answer 1

评论的意思是 - 不要重复造轮子。Java 不是汇编语言或 C 语言，它已经足够强大，可以处理这种琐碎的情况。以下是一个简单的代码示例，展示了简单的 Set 可以轻松处理您的词汇：

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;
    }
}

在我的电脑上显示为：

Total words 19875 in 47 milliseconds

如您所见，这20000个单词中有125个是重复的。不仅生成这些20000个单词的过程低效，而且存储和检查重复也耗费了时间。

- Alex