我正在编写一个用于解决填字游戏的求解器，它读取词典文件并根据模式返回符合该模式的所有单词列表。我已经实现了功能，但我需要让它更快地工作。我创建了一个HashMap，其中单词长度是键，单词列表是值。是否有一些方法可以更快地遍历ArrayList，或者有更好的数据结构可以使用？
import java.util.*;
public class CWSolution {
//create the data structure that will store the dictionary
private HashMap<Integer,ArrayList<String>> db;
public CWSolution(List<String> allWords)
{
//construct the background structure
//Create hashmap
db = new HashMap<Integer,ArrayList<String>>();
//go through each word
for(String item : allWords ){
//if the db does not contain a listing for this word length, create one
if(!db.containsKey(item.length())){
ArrayList<String> temp = new ArrayList<String>();
temp.add(item);
db.put(item.length(), temp);
}
//if it does contain a listing for this word length, add this word to it
else{
ArrayList<String> temp = db.get(item.length());
temp.add(item);
db.put(item.length(), temp);
}
}
}
public List<String> solutions(String pattern, int maxRequired)
{
//actually look for each pattern
//create the structures we need
List<String> answer = new ArrayList<String>();
//get the relevant array list
ArrayList<String> temp = db.get(pattern.length());
//go through the array list word by word
for(String item : temp ){
//see if the pattern matches the word, if it does add it to the list, otherwise skip it
if(matchPattern(pattern, item)){
answer.add(item);
}
//if we reach the required size return it, otherwise keep going
if(answer.size() == maxRequired){
return answer;
}
}
return answer;
}
private boolean matchPattern(String pattern, String word){
//TODO implement this function
//check the word against the pattern
char star = "*".charAt(0);
for(int i=0;i<pattern.length();i++){
if(pattern.charAt(i) != star){
if(pattern.charAt(i) != word.charAt(i)){
return false;
}
}
}
return true;
}
}
一些评论在辩论这个问题，所以我想澄清一下：我是一位数据结构课程的学生，我只知道一些基本的数据结构，但我们即将结束本学期，所以我有一个基本的思路。
此外，我不太关心优化CWSolution()方法，而是关心优化solutions()方法。速度测试如下，我真正关心的是Time2。找到匹配单词所需的时间而不是创建结构所需的时间。
import java.util.Date;
import java.util.List;
public class CWSpeedTest {
public static void main(String[] args){
try{
FileParser fp = new FileParser("TWL06.txt");
List<String> solutions = null;
//Change this to change the pattern
String pattern = "*S**";
//Change this to change the max solutions
int maxSolns = 2000;
List<String> dict = fp.getAllWords();
Date d1 = new Date();
CWSolution c = new CWSolution(dict);
Date d2 = new Date();
for (int i = 0; i < 1000; i++)
solutions = c.solutions(pattern,maxSolns);
Date d3 = new Date();
System.out.println("Time 1: " + (d2.getTime() - d1.getTime()));
System.out.println("Time 2: " + (d3.getTime() - d2.getTime()));
System.out.println("For the pattern: " + pattern);
System.out.println("With max solutions: " + maxSolns);
System.out.println(solutions);
}catch (Exception e){
e.printStackTrace();
}
}
}
Map<Integer, Map<Character, Set<String>>>的东西。其中的Set是所有包含给定Character在Integer指定位置的单词。然后您可以遍历模式中的字符，从该映射中获取所有指定字符的Set并逐个对这些集合进行交集运算。 - millimooseMap<Integer, Map<Integer, Map<Character, Set<String>>>>之后使用一个薄包装器，因为这么多的尖括号让人感到痛苦。你真正需要的是一个多维矩阵。或者，你可以为映射键创建一个单独的类DictionaryKey，其中包含字段length、position和character。让你的 IDE 使用这些字段生成一个hashCode()，然后使用Map<DictionaryKey, Set<String>>使代码更易读。这样，你可以通过使DictionaryKey不可变并记忆哈希码来微调优化一下。 - millimooselength -> position -> character -> words的映射被称为db。你会将单词 "puppy" 存储在长度为5的位置，并且使用position, character键0, 'p'、1, 'u'、2, 'p'等存储。 （每个单词都将由单词中的每个字符进行索引，而不仅仅是起始单词。这正是键为position, character的原因。）然后，如果你正在寻找与**ppy匹配的单词，你将得到集合db[2]['p']、db[3]['p']和db[4]['y']。我可以编写代码，但我现在很忙，如果这是作业，那么这将是一个很好的练习。;) - millimoosetotal_words/10个单词。(假设大多数单词的长度在3到13之间。实际上确切的长度分布并不重要，因为我的算法也通过单词长度进行过滤。)然后对这些单词中的每一个执行word_length个字符比较。如果字典很大，这可能是一个很大的数字。 - millimooseN是字典中单词的数量，m是当前单词的长度，则OP的方法为O((N * m) / 10)。我的方法为O(N / 260)，并且有一些变化。考虑到m可能很小，它们属于相同的复杂度类，但我的方法至少快一个数量级。 - millimoose