0

我正在编写一些 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());
}
4

3 回答 3

2

作为第一个优化，您可以删除对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()线性搜索您的数组列表。特别是在每次循环迭代时都会执行第二次出现，因此对于大型列表来说这将是一个杀手

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

像这样的一个简单场景：

输入文字："Some words are larger while some other words are smaller"

paraWordsList：包含上述文本的字符串拆分，例如 {"Some", "words", ...}

paraWordsIndexes : 包含 blah blah 的索引，例如 {0, 3}

lowFreqIndexes：包含废话，例如 {0, 1}

预期输出：它应该返回 {value} 而不是 {other_value}

于 2013-07-25T08:40:54.513 回答
1

在这种情况下，您的代码似乎很复杂（for - if - for），优化它的最佳方法是使用分析器检查在执行过程中花费更多时间的代码在哪里。

由于您没有指定您的 IDE，因此您将尝试推荐一些有趣的工具：

https://profiler.netbeans.org/ http://www.eclipse.org/tptp/

此致

于 2013-07-25T05:27:02.697 回答
0

好吧，如果您没有嵌套循环，这将有所帮助，并且，如果您可以最小化每个循环中的 if 语句的数量（尤其是如果您有嵌套循环），这也会有所帮助。

你能解释一下你想要做什么吗？您的代码并不完全明显，也许有一种与您的方法完全不同的方法。

于 2013-07-25T05:27:17.097 回答