我正在为一个填字游戏编写一个求解器，它读入一个字典文件并给定一个模式，返回符合该模式的所有单词的列表。我的功能可以正常工作，但我需要它来更快地工作。我创建了一个 HashMap，以单词的长度为键，以单词的 ArrayList 作为值。有什么方法可以让我更快地阅读 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;
}
}
编辑:
添加更多信息以使其更清楚。
一些评论对此进行了辩论，所以我想我会澄清一下，我是数据结构类(class)的学生，所以我知道的只有这么多，但我们即将结束学期，所以我有一个好主意基本数据结构。
此外，我并不关心优化 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();
}
}
}
最佳答案
这是对所有位置和字符使用索引完全重写的算法。首先，该算法在模式中找到的指定位置找到具有指定字符的最短单词列表。然后它计算所有其他单词列表的横截面(模式中每个非星字符一个列表)。
import java.util.*;
public class CWSolution {
class FixLengthDB {
// Index -> Letter -> All word with the Letter at Index
HashMap<Integer, HashMap<Character, Set<String>>> indexLetterDb = new HashMap<>();
public void storeWord(String word) {
int l = word.length();
for (int i = 0; i < l; i++) {
HashMap<Character, Set<String>> letterDb = indexLetterDb.get(i);
if (letterDb == null) {
letterDb = new HashMap<>();
indexLetterDb.put(i, letterDb);
}
Set<String> list = letterDb.get(word.charAt(i));
if (list == null) {
list = new HashSet<>();
letterDb.put(word.charAt(i), list);
}
list.add(word);
}
}
public Set<String> getList(int i, char c) {
HashMap<Character, Set<String>> letterDb = indexLetterDb.get(i);
if (letterDb == null) {
return null;
}
return letterDb.get(c);
}
}
//create the data structure that will store the dictionary
private HashMap<Integer,FixLengthDB> db = new HashMap<>();
private List<String> allWords;
public CWSolution(List<String> allWords)
{
//construct the background structure
this.allWords = allWords;
//go through each word
for(String item : allWords) {
FixLengthDB fixLengthDB = db.get(item.length());
if (fixLengthDB == null) {
fixLengthDB = new FixLengthDB();
db.put(item.length(), fixLengthDB);
}
fixLengthDB.storeWord(item);
}
}
public List<String> solutions(String pattern, int maxRequired)
{
FixLengthDB fixLengthDB = db.get(pattern.length());
if (fixLengthDB == null) {
return new ArrayList<>();
}
Set<String> shortList = null;
int shortListIndex = 0;
int l = pattern.length();
for (int i = 0; i < l; i++) {
if (pattern.charAt(i) == '*') {
continue;
}
Set<String> set = fixLengthDB.getList(i, pattern.charAt(i));
if (set == null) {
return new ArrayList<>();
}
if (shortList == null || shortList.size() > set.size()) {
shortList = set;
shortListIndex = i;
}
}
if (shortList == null) {
return allWords;
}
HashSet<String> result = new HashSet<>(shortList);
for (int i = 0; i < l; i++) {
if (i == shortListIndex || pattern.charAt(i) == '*') {
continue;
}
Set<String> set = fixLengthDB.getList(i, pattern.charAt(i));
result.retainAll(set);
}
// TODO truncate result list according to 'maxRequired' parameter
return new ArrayList<>(result);
}
}
说明:该算法分两步工作
solutions(...)) 建立索引:索引维护每个字长/字符-索引/字符的字符串集。
这里我们如何向索引添加单词
Add word: fun
|||
||\--- (length: 3, position 3, character 'n') -> set{"fun"})
|\---- (length: 3, position 2, character 'u') -> set{"fun"})
\----- (length: 3, position 1, character 'f') -> set{"fun"})
Add word: run
|||
||\--- (length: 3, position 3, character 'n') -> set{"fun, run"})
|\---- (length: 3, position 2, character 'u') -> set{"fun, run"})
\----- (length: 3, position 1, character 'r') -> set{"run"})
Add word: raw
|||
||\--- (length: 3, position 3, character 'w') -> set{"raw"})
|\---- (length: 3, position 2, character 'a') -> set{"raw"})
\----- (length: 3, position 1, character 'r') -> set{"run, raw"})
Add word: rar
|||
||\--- (length: 3, position 3, character 'r') -> set{"rar"})
|\---- (length: 3, position 2, character 'a') -> set{"raw, rar"})
\----- (length: 3, position 1, character 'r') -> set{"run, raw, rar"})
添加四个字(fun、run、raw、rar)后的数据库是
(length: 3, position 1, character 'f') -> set{"fun"})
(length: 3, position 1, character 'r') -> set{"run, raw, rar"})
(length: 3, position 2, character 'u') -> set{"fun, run"})
(length: 3, position 2, character 'a') -> set{"raw, rar"})
(length: 3, position 3, character 'w') -> set{"raw"})
(length: 3, position 3, character 'r') -> set{"rar"})
(length: 3, position 3, character 'n') -> set{"fun, run"})
使用索引:如何匹配模式
ru*首先让我们在索引中找到匹配的最小集合。我们只有 2 个非明星角色，所以我们只检查了两组
1: (length: 3, position 1, character 'r') -> set{"run, raw, rar"})
2: (length: 3, position 2, character 'u') -> set{"fun, run"})
最小的集合是 #2
{"fun, run"} 。现在我们遍历所有其他匹配集(在我们的例子中是集 #1)并计算交集:{"fun, run"} cross {"run, raw, rar"} => {"run"}
结果是
{"run"} 。关于java - 更快地读取 ArrayList，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20505596/