1

そこで、JavaでArraylistを検索し、文字列の長さと大きなテキストファイルに存在する頻度で構成されるヒストグラムを作成しようとしています。私はブルートフォースアルゴリズムを考え出しましたが、それは遅すぎて大きなデータファイルで使用できません。Arraylistを介して処理するより効率的な方法はありますか？私が思いついた強引な方法を含めました。

for (int i = 0; i < (maxLen + 1); i++)
{
    int hit = 0;
    for (int j = 0; j < list.size(); j++)
    {
        if (i == list.get(j).length())
            ++hit;

        histogram[i] = hit;
    }

}
4

2 に答える 2

2

これはひどく非効率的です。

可能な各長さの値をループしてから、使用可能な各単語をループする代わりに、ドキュメント内の使用可能な単語をループして、それらの長さを数えるのはどうですか？

例えば：

Map<Integer, Integer> frequencies = new HashMap<Integer, Integer>();

for(int i=0; i<list.size(); i++) {
    String thisWord = list.get(i);
    Integer theLength = (Integer)(thisWord.length());
    if(frequencies.containsKey(theLength) {
        frequencies.put(theLength, new Integer(frequencies.get(theLength).intValue()+1));
    }
    else {
        frequencies.put(theLength, new Integer(1));
    }
}

次に、キーがに存在しない場合、HashMapその長さの単語がドキュメントに存在しないことがわかります。キーが存在する場合は、発生した回数を正確に調べることができます。

注：このコード例のいくつかの側面は、ボクシングとアンボクシングに関する追加の混乱を防ぐために作成されました。少しすっきりと書くことは可能ですが、実稼働環境では確かにそうします。また、単語の最小または最大の長さについての知識がないことを前提としています（したがって、わずかに柔軟性があり、スケーラブルで、キャッチオールです）。それ以外の場合は、プリミティブ配列を宣言するための他の手法も同様に機能します（Jon Skeetの回答を参照）。

自動ボクシングを利用するよりクリーンなバージョンの場合：

Map<Integer, Integer> frequencies = new HashMap<Integer, Integer>();

for(int i=0; i<list.size(); i++) {
    String thisWord = list.get(i);
    if(frequencies.containsKey(thisWord.length()) {
        frequencies.put(thisWord.length(), frequencies.get(thisWord.length())+1);
    }
    else {
        frequencies.put(thisWord.length(), 1);
    }
}
于 2012-10-23T17:28:32.450 に答える
1

リストを一度だけループしてみませんか？

int[] histogram = new int[maxLen + 1]; // All entries will be 0 to start with
for (String text : list) {
    if (text.length() <= maxLen) {
        histogram[text.length()]++;
    }
}

これは現在、O（N）です。

于 2012-10-23T17:29:19.127 に答える