正在创建纵横填字游戏的解算器。 读取图案并提供给词典文件，并返回与该图案匹配的所有单词的列表。 我有功能，但这项工作必须更快。 我制作了HashMap。 其中单词的长度是键，以单词的ArrayList为值。 你能更快地读取ArrayList吗？ 还是有更好的数据结构？
import java.util.*；
公共类CW解决方案{
//createthedatastructurethatwillstorethedictionary
私密hashmap db；
公共世界(列表世界)。
{
//constructthebackgroundstructure
//创建混图
db=new HashMap (；
//go through each word
for (字符串项目3360 all words ) {
//ifthedbdoesnotcontainalistingforthiswordlength，create one
if (！ db.containskey(item.length () ) ) ) ) ) ) ) )。
ArrayList temp=new ArrayList (；
TEMP.add(item；
db.put(item.length )、temp )；
}
//ifitdoescontainalistingforthiswordlength，add this word to it
else{
ArrayList temp=db.get (item.length )；
TEMP.add(item；
db.put(item.length )、temp )；
}
}
}
publiclistsolutions (字符串模式，int maxRequired ) ) )。
{
//actually look for each pattern
//create the structures we need
列表answer=new ArrayList (；
//get the relevant array列表
ArrayList temp=db.get (pattern.length ()；
//gothroughthearraylistwordbyword
for(stringitem3360temp )
//seeifthepatternmatchestheword，if it does add it to the list，otherwise skip it
if (匹配图案(图案，item ) ) }
Answer.add(item；
}
//ifwereachtherequiredsizereturnit，otherwise密钥登录
if (answer.size (==max要求) {
返回响应器；
}
}
返回响应器；
}
专用booleanmatchpattern (字符串参数，字符串word )。
//todo实施this function
//checkthewordagainstthepattern
charstar='*'.charat(0；
for(intI=0； I
if(Pattern.Charat(I )！=star ) {
if(Pattern.Charat(I )！=word.Charat(I ) }{
返回假；
}
}
}
返回真；
}
}
编辑：
为了更加明确，添加信息。
有几条评论在讨论这个问题，我想澄清一下。 因为我是数据结构课程的学生，所以知道很多，但是我们快到期末了，所以对基本的数据结构很了解。
另外，我对优化求解(solve )方法而不是优化CWSolution (方法)感兴趣。 速度经过了以下测试，但真正感兴趣的是Time2。 这是找到匹配单词所需的时间，不是构建结构所需的时间。
import java.util.Date；
I
mport java.util.List;public class CWSpeedTest {
public static void main(String[] args){
try{
FileParser fp = new FileParser("TWL06.txt");
List solutions = null;
//Change this to change the pattern
String pattern = "*S**";
//Change this to change the max solutions
int maxSolns = 2000;
List 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>> indexLetterDb = new HashMap<>();
public void storeWord(String word) {
int l = word.length();
for (int i = 0; i < l; i++) {
HashMap> letterDb = indexLetterDb.get(i);
if (letterDb == null) {
letterDb = new HashMap<>();
indexLetterDb.put(i, letterDb);
}
Set list = letterDb.get(word.charAt(i));
if (list == null) {
list = new HashSet<>();
letterDb.put(word.charAt(i), list);
}
list.add(word);
}
}
public Set getList(int i, char c) {
HashMap> letterDb = indexLetterDb.get(i);
if (letterDb == null) {
return null;
}
return letterDb.get(c);
}
}
//create the data structure that will store the dictionary
private HashMap db = new HashMap<>();
private List allWords;
public CWSolution(List 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 solutions(String pattern, int maxRequired)
{
FixLengthDB fixLengthDB = db.get(pattern.length());
if (fixLengthDB == null) {
return new ArrayList<>();
}
Set shortList = null;
int shortListIndex = 0;
int l = pattern.length();
for (int i = 0; i < l; i++) {
if (pattern.charAt(i) == '*') {
continue;
}
Set 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 result = new HashSet<>(shortList);
for (int i = 0; i < l; i++) {
if (i == shortListIndex || pattern.charAt(i) == '*') {
continue;
}
Set set = fixLengthDB.getList(i, pattern.charAt(i));
result.retainAll(set);
}
// TODO truncate result list according to 'maxRequired' parameter
return new ArrayList<>(result);
}
}
说明：该算法分两步进行
>构建索引(在构造函数中)
>使用索引查找匹配的单词(解决方案(…))
构建索引：索引维护每个字长/字符索引/字符的字符串集.
这里我们如何向索引添加单词
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,performance,arraylist
来源： https://codeday.me/bug/20190831/1774323.html