java - 更快地读取 ArrayList

Question

我正在为填字游戏编写一个解算器，它读取字典文件并给定一个模式，返回符合该模式的所有单词的列表。我的功能可以正常工作，但我需要它才能更快地工作。我创建了一个 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();
    }
    }
}

Answer 1

这里是对所有位置和字符使用索引的算法的完全重写。首先，该算法在模式中的指定位置找到具有指定字符的单词的最短列表。然后它计算所有其他单词列表的横截面(模式中每个非星号字符一个列表)。

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(...))

构建索引:索引为每个word-length/character-index/character维护字符串集。

这是我们如何将单词添加到索引中

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"}。