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()配列リストを直線的に検索します。特に 2 番目の発生はすべてのループ反復で実行されるため、大きなリストのキラーになります。

上記が役に立たない場合は、質問を編集して簡単なテストケースを追加しない理由がわかりません。非常に多くの人が（私を含めて）あなたにも尋ねてきたからです。

このような単純なシナリオ:

入力テキスト:"Some words are larger while some other words are smaller"

paraWordsList : {"Some", "words", ...} など、上記のテキストの文字列分割が含まれます。

paraWordsIndexes : {0, 3} などの何とかのインデックスが含まれています

lowFreqIndexes : {0, 1} など、何とか何とか含まれています

予想される出力: {value} は返されますが、{other_value} は返されません。

于 2013-07-25T08:40:54.513 に答える
1

コードが複雑に見える ( for - if - for ) この場合、コードを最適化する最善の方法は、プロファイラーを使用して、実行プロセスでより多くの時間を費やしているコードがどこにあるかを確認することです。

IDE を指定しないので、y はいくつかの興味深いツールを提案しようとします。

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

よろしくお願いします

于 2013-07-25T05:27:02.697 に答える
0

入れ子になったループがない場合に役立ちます。また、各ループ内の if ステートメントの数を最小限に抑えることもできます (特に入れ子になったループがある場合)。

何をしようとしているのか説明できますか？あなたのコードは完全に明白ではなく、あなたのアプローチとはまったく異なる方法があるかもしれません。

于 2013-07-25T05:27:17.097 に答える