0

単語の出現を 10,000 個のテキスト ファイルなどの複数のファイルに格納するハッシュマップを作成しました。次に、ハッシュマップからそれらを並べ替えて、上位 10 の単語を出力したいと考えました。ハッシュマップは次のように定義されます。

      Hashtable <String, Integer> problem1Counter = new Hashtable<String, Integer> ();

ファイルを約 1000 に保持すると、次のような単純な並べ替えを使用して上位 10 語を取得できました。

String[] keysProblem1 = (String[]) problem1Counter.keySet().toArray(new String[0]);
  Integer [] valuesProblem1 =  (Integer[])problem1Counter.values().toArray(new Integer[problem1Counter.size()]);

int kk = 0; 文字列 ii = null;

    for (int jj = 0; jj < valuesProblem1.length ; jj++){
        for (int bb = 0; bb < valuesProblem1.length; bb++){
            if(valuesProblem1[jj] < valuesProblem1[bb]){
            kk = valuesProblem1[jj];
            ii = keysProblem1[jj];
            valuesProblem1[jj] = valuesProblem1[bb];
            keysProblem1[jj] = keysProblem1[bb];
            valuesProblem1 [bb] = kk;
            keysProblem1 [bb] = ii;}}}

したがって、ハッシュテーブルに 553685 を超える値がある場合、上記の方法は機能しません。それで、誰でもそれらをソートするためのより良い方法を提案して示すことができますか? 私はJavaの初心者ですが、アクションスクリプトで働いていたので、少し快適でした. ありがとう。

4

3 に答える 3

4

問題は、分割して、各インデックスにあるものを自分で接続したままにしようとしkeysたときに始まります。values代わりに、それらを結合したままにして、Map.EntryJava が提供するオブジェクトをソートします。

これがコンパイルされるかどうかはわかりませんが、開始する必要があります。

// HashMap and Hashtable are very similar, but I generally use HashMap.
HashMap<String, Integer> answers = ...

// Get the Key/Value pairs into a list so we can sort them.
List<Map.Entry<String, Integer>> listOfAnswers =
    new ArrayList<Map.Entry<String, Integer>>(answers.entrySet());

// Our comparator defines how to sort our Key/Value pairs.  We sort by the
// highest value, and don't worry about the key.
java.util.Collections.sort(listOfAnswers,
    new Comparator<Map.Entry<String, Integer>>() {
        public int compare(
                Map.Entry<String, Integer> o1,
                Map.Entry<String, Integer> o2) {
            return o2.getValue() - o1.getValue();
        }
    });

// The list is now sorted.
System.out.println( String.format("Top 3:\n%s: %d\n%s: %d\n%s: %d", + 
        listOfAnswers.get(0).getKey(), listOfAnswers.get(0).getValue(), 
        listOfAnswers.get(1).getKey(), listOfAnswers.get(1).getValue(), 
        listOfAnswers.get(2).getKey(), listOfAnswers.get(2).getValue()));
于 2012-10-05T05:50:31.617 に答える
3

並べ替えを行うより良い方法として、次のようにします。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
    HashMap<String, Integer> counter = new HashMap<String, Integer>();

    // [... Code to populate hashtable goes here ...]
    // 

    // Extract the map as a list
    List<Map.Entry<String, Integer>> entries = new ArrayList<Map.Entry<String, Integer>>(counter.entrySet());

    // Sort the list of entries.
    Collections.sort(entries, new Comparator<Map.Entry<String, Integer>>() {
        @Override
        public int compare(Entry<String, Integer> first, Entry<String, Integer> second) {
        // This will give a *positive* value if first freq < second freq, zero if they're equal, negative if first > second.
        // The result is a highest frequency first sort.
        return second.getValue() - first.getValue();
        }
    });

    // And display the results
    for (Map.Entry<String, Integer> entry : entries.subList(0, 10))
        System.out.println(String.format("%s: %d", entry.getKey(), entry.getValue()));
    }

}

これが機能する理由を説明する編集

元のアルゴリズムは、 O(n^2) アルゴリズムであるSelection Sortのバリアントのように見えます。あなたのバリアントも多くの余分なスワッピングを行うため、非常に遅いです。

O(n^2) であるため、問題のサイズを 10 倍すると、通常、実行に 100 倍の時間がかかります。50 万の要素を並べ替えるには、2,500 億回の比較を行う必要があり、その多くは交換につながります。

Collections#sort の組み込みソート アルゴリズムは、O(n.log(n)) 時間で実行されるMerge Sortの超高速バリアントです。つまり、問題のサイズを 10 倍するたびに、約 30 倍の時間がかかるだけです。50 万個の要素を並べ替えるには、約 1,000 万回の比較を行うだけで済みます。

これが、経験豊富な開発者が可能な限りライブラリ関数を使用するようにアドバイスする理由です。独自のソート アルゴリズムを作成することは学習には最適ですが、ライブラリにあるものと同じくらい高速かつ柔軟に実装するには多くの作業が必要です。

于 2012-10-05T05:57:48.127 に答える
1
  • Comparable を実装する内部クラス Word を作成する
  • public int compareTo(Word w) をオーバーライドして、オカレンスを使用するようにします
  • HashMap のサイズの単語の配列を作成します
  • HashMap を反復して配列を埋める
  • 配列で Arrays.sort を呼び出します

または、トップ 10 のみが必要なため、Word を反復処理して、作業を進めながらトップ 10 リストを維持することもできます。

于 2012-10-05T05:46:13.677 に答える