Java方法优化

Question

我正在编写一些java代码我写了一个方法，对于测试输入，执行时间超过 5 秒我真的真的很想把它控制在5秒以内谁能建议我如何优化我的方法

private static String getShortestSub(ArrayList<String> paraWordsList,
        ArrayList<Integer> paraWordsIndexes,
        ArrayList<Integer> lowFreqIndexes) {

    long d = System.currentTimeMillis();
    // Finding the substring
    int startTxtIndex = 0, endTxtIndex = 0;
    int tempLength = paraWordsList.size();
    for (int i = 0; i < lowFreqIndexes.size(); i++) 
    {
        int point = lowFreqIndexes.get(i), startIndex = 0;
        HashSet<String> frame = new HashSet<String>();


        // index is the indexes of paraWordsIndexes
        startIndex =paraWordsIndexes.indexOf(point);
        for (int index = paraWordsIndexes.indexOf(point); index >= 0; index--) 
        {
            if (frame.add(paraWordsList.get(paraWordsIndexes.get(index))))
            {
                startIndex = index;
                if (frame.size() == K
                        || (paraWordsIndexes.get(startIndex) - point) >= tempLength) 
                    index = -1;                 
            }
        }
        frame.clear();

        for (int start = startIndex, index = startIndex; start <= paraWordsIndexes
                .indexOf(point) && index < paraWordsIndexes.size(); index++) 
        {
            int tempStart = paraWordsIndexes.get(start), tempEnd = paraWordsIndexes.get(start);
            int currIndex = paraWordsIndexes.get(index);
            String word = paraWordsList.get(currIndex);
            if ((tempStart - point) >= tempLength)          break;
            if ((tempStart - currIndex) >= tempLength)      break;
                    frame.add(word);
            if (frame.size() == K) 
            {
                tempEnd = currIndex;
                int newLength;
                if ((newLength = tempEnd - tempStart) > 0)
                    if (tempLength > newLength) 
                    {
                        tempLength = newLength;
                        startTxtIndex = tempStart;
                        endTxtIndex = tempEnd;
                        if (K == (tempLength+1)) {
                            i = lowFreqIndexes.size();
                            break;
                        }
                    }
                frame.clear();
                tempStart = paraWordsList.size();
                start++;
                index = start - 1;
            }
        }
        frame.clear();
        System.out.println(System.currentTimeMillis() - d);
    }

    String[] result = paraText.split(" ");
    ArrayList<String> actualParaWordsList = new ArrayList<String>(
            Arrays.asList(result));

    return textCleanup(actualParaWordsList.subList(startTxtIndex,
            endTxtIndex + 1).toString());
}

Answer 1

作为第一个优化，您可以删除对 indexOf() 的冗余调用

在外循环期间，point 变量不会更改，因此第一次调用 indexOf() 是唯一实际需要的调用。

// index is the indexes of paraWordsIndexes
startIndex =paraWordsIndexes.indexOf(point);

引入一个新变量来存储 indexOf() 的结果，并且不会在循环内更改

int pointLFIndex = paraWordsIndexes.indexOf(point); // new variable. should not change
startIndex = pointLFIndex;

然后将所有出现的 indexOf(point) 更改为上述变量。

// you don't need this. change to for (int index = pointLFIndex; ...);
for (int index = paraWordsIndexes.indexOf(point); index >= 0; index--)  

// use for (int start = ...; start <= pointLFIndex ...; index++) {
for (int start = ...; start <= paraWordsIndexes.indexOf(point) ...; index++) {

indexOf() 线性搜索数组列表。特别是第二次出现是在每次循环迭代时执行的，因此对于大型列表来说它将是一个 killer

如果上述方法没有帮助，我不明白为什么你不编辑你的问题来添加一个简单的测试用例，因为很多人也问过你(包括我自己)。

像这样的简单场景:

Input text: "Some words are larger while some other words are
smaller"

paraWordsList: contains the string split of the above text e.g. {"Some", "words", ...}

paraWordsIndexes: contains the indexes of blah blah e.g. {0, 3}

lowFreqIndexes: contains blah blah e.g. {0, 1}

Expected output: it should return {value} but not {other_value}