54

説明 | テキスト ファイルを読み取り、一意の各単語をアルファベット順に出力する Java プログラム。

Map<String, Integer>プログラムは、単語と対応する出現頻度を格納する型の変数を宣言する必要があります。しかし、具体的なタイプはどれですか？TreeMap<String, Number>またはHashMap<String, Number>？

入力は小文字に変換する必要があります。

単語に次の文字が含まれていません。\t\t\n]f.,!?:;\"()'

出力例 | 

 Word            Frequency
  a                 1
  and               5
  appearances       1
  as                1
         .
         .
         .

備考 | Perl では、およそ 2 行のコードでこれを解決するエレガントなソリューションを見てきました。ただし、Javaで見たいです。

編集: そうそう、これらの構造の 1 つを (Java で) 使用して実装を示すと役に立ちます。

4

14 に答える 14

62

TreeMap私には簡単に思えます-単に「アルファベット順」の要件のためです。HashMapそれを反復するとき、順序はありません。TreeMap自然キーの順序で反復します。

編集：コンラッドのコメントは、「を使用HashMapしてからソートする」ことを示唆していた可能性があると思います。これは良いことです。最初は N 回の反復がありますが、重複のために最後には K <= N キーになるからです。キーの数が少なくなる最後まで、高価なビット (ソート) を節約することもできます。

そうは言っても、私は今のところ私の答えにこだわっています。それが目標を達成する最も簡単な方法だからです。OPがパフォーマンスを特に心配していることはよくわかりませんが、質問は彼が優雅さと簡潔さを心配していることを意味します. a を使用するTreeMapと、これが信じられないほど簡潔になります。これは私にとって魅力的です。パフォーマンスが本当に問題である場合、それを攻撃するより良い方法があるかもしれないと思いますTreeMapまたはHashMap:)

于 2008-11-19T15:56:52.010 に答える
18

TreeMap はすでにソートされているため、TreeMap は HashMap より優れています。

ただし、より適切なデータ構造であるバッグの使用を検討することをお勧めします。Commons コレクションとTreeBagクラスを参照 してください。

これには、最適化された優れた内部構造と API があります。

bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")

編集: HashMap と TreeMap のパフォーマンスの問題は、Jon によって回答されました。バッグも同じです。HashBag と TreeBag があります。実装 (変更可能な整数を使用) に基づいて、バッグは同等の整数の単純なマップよりも優れている必要があります。確実に知る唯一の方法は、パフォーマンスに関する質問と同様に、テストすることです。

于 2008-11-19T16:06:11.290 に答える
11

「TreeMap のルックアップには時間がかかる」と言っている人がかなりいますO(n log n)。どうして？

どのように実装されているかはわかりませんが、私の頭ではO(log n).

これは、ツリー内のルックアップが で実行できるためですO(log n)。アイテムを挿入するたびにツリー全体をソートするわけではありません。それがツリーを使用する全体のアイデアです。

したがって、元の質問に戻ると、比較対象の数値は次のようになります。

HashMap アプローチ: O(n + k log k)平均的なケース、最悪のケースははるかに大きくなる可能性があります

TreeMap アプローチ: O(k + n log k)最悪のケース

ここで、n = テキスト内の単語数、k = テキスト内の個別の単語数です。

于 2011-04-14T14:21:51.800 に答える
3

ハッシュマップははるかに高速であるはずです。最終的にアイテムをどのように配置するかに基づいてコンテナを選択しないでください。最後に（単語、頻度）ペアのリストを並べ替えるだけです。通常、ファイル内の単語よりもソートされるそのようなペアが少ないため、ハッシュマップを使用した漸近的（および実際の）パフォーマンスが向上します。

于 2008-11-19T17:35:40.330 に答える
3 
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream.GetField;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class TreeMapExample {

    public static void main (String args[]){
        Map<String,Integer> tm = new TreeMap<String,Integer>();
        try {

            FileInputStream fis = new FileInputStream("Test.txt");
            DataInputStream in = new DataInputStream(fis);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String line;
            int countValue = 1;
            while((line = br.readLine())!= null ){
                line = line.replaceAll("[-+.^:;,()\"\\[\\]]","");
                StringTokenizer st = new StringTokenizer(line, " ");    
                while(st.hasMoreTokens()){
                    String nextElement = (String) st.nextElement();

                    if(tm.size()>0 && tm.containsKey(nextElement)){
                        int val = 0;
                        if(tm.get(nextElement)!= null){
                        val = (Integer) tm.get(nextElement);
                        val = val+1;
                        }
                        tm.put(nextElement, val);
                    }else{
                    tm.put(nextElement, 1);
                    }

                }
            }
            for(Map.Entry<String,Integer> entry : tm.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
            }

        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

}
于 2012-05-03T13:02:31.723 に答える
2

TreeMap<String,Number>タイプが の変数にa を代入することはできませんMap<String,Integer>。Double、Longなどを に「入れる」ことができますTreeMap<String,Number>。から値を「取得」するときMap<String,Integer>、それは でなければなりませんInteger。

i18n の問題、メモリの制約、およびエラー処理を完全に無視すると、次のようになります。

class Counter {

  public static void main(String... argv)
    throws Exception
  {
    FileChannel fc = new FileInputStream(argv[0]).getChannel();
    ByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
    CharBuffer cb = Charset.defaultCharset().decode(bb);
    Pattern p = Pattern.compile("[^ \t\r\n\f.,!?:;\"()']+");
    Map<String, Integer> counts = new TreeMap<String, Integer>();
    Matcher m = p.matcher(cb);
    while (m.find()) {
      String word = m.group();
      Integer count = counts.get(word);
      count = (count == null) ? 1 : count + 1;
      counts.put(word, count);
    }
    fc.close();
    for (Map.Entry<String, Integer> e : counts.entrySet()) {
      System.out.printf("%s: %d%n", e.getKey(), e.getValue());
    }
  }

}
于 2008-11-19T16:17:34.667 に答える
2

「キーがすでに存在する場合、HashMap と同じパフォーマンスを発揮します。」- それは明らかに間違っています。HashMap には O(1) の挿入があり、TreeMap には O(n log n) があります。テーブルにあるかどうかを確認するには、少なくとも n 回のログ n 回のチェックが必要です。

于 2010-08-14T03:46:49.463 に答える
2

このように、私の意見では、Apache Commons CollectionsのHashBagまたはGuavaのHashMultisetまたはEclipse Collections (正式にはGS Collections ) の HashBag または次のクラスを使用することをお勧めします。

    Order    |  Guava           |   Apache  | Eclipse(GS) | JDK analog
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Not define   | HashMultiset     |   HashBag | HashBag     | HashMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Sorted       | TreeMultiset     |   TreeBag | TreeBag     | TreeMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Linked       |LinkedHashMultiset|     -     |     -       | LinkedHashMap<String, Integere>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent & | ConcurrentHash-  |Synchroniz-|Synchroniz-  | Collections.synchronizedMap(
not define   | Multiset         |   edBag   | edBag       |       HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent   |         -        |Synchroniz-|Synchroniz-  | Collections.synchronizedSorted-
and sorted   |                  |edSortedBag| edSortedBag |       Map(TreeMap<>))
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableMultiset|Unmodifiab-|Unmodifiab-  | Collections.unmodifiableMap(
not define   |                  |   leBag   | leBag       | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableSorted- |Unmodifiab-|Unmodifiab-  | Collections.unmodifiableSorted-
sorted       | Multiset         |leSortedBag| leSortedBag | Map(TreeMap<String, Integer>))
────────────────────────────────────────────────────────────────────────

例:

1. Apache から SynchronizedSortedBag を使用する:

    // Parse text to separate words
    String INPUT_TEXT = "Hello World! Hello All! Hi World!";
    // Create Multiset
    Bag bag = SynchronizedSortedBag.synchronizedBag(new TreeBag(Arrays.asList(INPUT_TEXT.split(" "))));

    // Print count words
    System.out.println(bag); // print [1:All!,2:Hello,1:Hi,2:World!]- in natural (alphabet) order
    // Print all unique words
    System.out.println(bag.uniqueSet());    // print [All!, Hello, Hi, World!]- in natural (alphabet) order


    // Print count occurrences of words
    System.out.println("Hello = " + bag.getCount("Hello"));    // print 2
    System.out.println("World = " + bag.getCount("World!"));    // print 2
    System.out.println("All = " + bag.getCount("All!"));    // print 1
    System.out.println("Hi = " + bag.getCount("Hi"));    // print 1
    System.out.println("Empty = " + bag.getCount("Empty"));    // print 0

    // Print count all words
    System.out.println(bag.size());    //print 6

    // Print count unique words
    System.out.println(bag.uniqueSet().size());    //print 4

2. Eclipse(GC) から TreeBag を使用する:

    // Parse text to separate words
    String INPUT_TEXT = "Hello World! Hello All! Hi World!";
    // Create Multiset
    MutableSortedBag<String> bag =  TreeBag.newBag(Arrays.asList(INPUT_TEXT.split(" ")));

    // Print count words
    System.out.println(bag); // print [All!, Hello, Hello, Hi, World!, World!]- in natural order
    // Print all unique words
    System.out.println(bag.toSortedSet());    // print [All!, Hello, Hi, World!]- in natural order

    // Print count occurrences of words
    System.out.println("Hello = " + bag.occurrencesOf("Hello"));    // print 2
    System.out.println("World = " + bag.occurrencesOf("World!"));    // print 2
    System.out.println("All = " + bag.occurrencesOf("All!"));    // print 1
    System.out.println("Hi = " + bag.occurrencesOf("Hi"));    // print 1
    System.out.println("Empty = " + bag.occurrencesOf("Empty"));    // print 0

    // Print count all words
    System.out.println(bag.size());    //print 6

    // Print count unique words
    System.out.println(bag.toSet().size());    //print 4

3. Guava から LinkedHashMultiset を使用する:

    // Parse text to separate words
    String INPUT_TEXT = "Hello World! Hello All! Hi World!";
    // Create Multiset
    Multiset<String> multiset = LinkedHashMultiset.create(Arrays.asList(INPUT_TEXT.split(" ")));

    // Print count words
    System.out.println(multiset); // print [Hello x 2, World! x 2, All!, Hi]- in predictable iteration order
    // Print all unique words
    System.out.println(multiset.elementSet());    // print [Hello, World!, All!, Hi] - in predictable iteration order

    // Print count occurrences of words
    System.out.println("Hello = " + multiset.count("Hello"));    // print 2
    System.out.println("World = " + multiset.count("World!"));    // print 2
    System.out.println("All = " + multiset.count("All!"));    // print 1
    System.out.println("Hi = " + multiset.count("Hi"));    // print 1
    System.out.println("Empty = " + multiset.count("Empty"));    // print 0

    // Print count all words
    System.out.println(multiset.size());    //print 6

    // Print count unique words
    System.out.println(multiset.elementSet().size());    //print 4

私のgithubプロジェクトで見つけることができるその他の例

于 2016-03-04T17:39:50.460 に答える
1

私は間違いなく TreeMap を選択します。

  • TreeMap は挿入時に新しいキーを自動的にソートします。後でソートする必要はありません。
  • キーが既に存在する場合、HashMap と同じパフォーマンスを発揮します。

TreeSet は内部で TreeMap を使用するため、TreeMap を直接使用しないでください。

于 2008-11-19T18:44:41.407 に答える
0

データ構造への追加または削除の頻度を考慮してください。TreeMapが高い場合、理想的ではありません。既存のエントリnLnの検索とは別に、頻繁にリバランスが行われます。

一方、ハッシュ構造はメモリ上で少し派手です（割り当て超過）。その弾丸を噛むことができる場合は、ハッシュ構造を選択し、必要に応じて並べ替えます。

于 2010-08-19T11:40:32.227 に答える
0

テキスト ファイルを読み取り、キーに基づいてソートし、次に値に基づいてソートする Java の例を次に示します。ファイル内の単語の出現数に応じて。

public class SortFileWords {

    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        ValueCompare vc = new ValueCompare(map);
        TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(map);
        List<String> list = new ArrayList<>();
        Scanner sc;
        try {
            sc = new Scanner(new File("c:\\ReadMe1.txt"));
            while (sc.hasNext()) {
                list.add(sc.next());
            }
            sc.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        for (String s : list) {
            if (map.containsKey(s)) {
                map.put(s, map.get(s) + 1);
            } else
                map.put(s, 1);
        }

        System.out.println("Unsorted map: " + map);
        sorted_map.putAll(map);
        System.out.println("Sorted map on keys: " + sorted_map);

        TreeMap<String, Integer> sorted_value_map = new TreeMap<>(vc);
        sorted_value_map.putAll(map);
        System.out.println("Sorted map on values: " + sorted_value_map);
    }
}

class ValueCompare implements Comparator<String> {

    Map<String, Integer> map;

    public ValueCompare(Map<String, Integer> map) {
        this.map = map;
    }

    @Override
    public int compare(String s1, String s2) {
        if (map.get(s1) >= map.get(s2))
            return -1;
        else
            return 1;
    }
}
于 2015-06-28T12:54:10.993 に答える
0

速度要件に応じて、Trieを使用することもできます。しかし、TreeMap が十分に高速な場合、それらのいずれかを実装しても意味がありません。

于 2008-11-19T16:06:20.667 に答える
-2

TreeSetを使用しないのはなぜですか?

Set であることを除いて、TreeMap と同じ順序付けの概念です。これは、定義上、「重複する要素を含まないコレクション」です。

問題の説明から、セットが必要なように聞こえますが、どのキーと値を一緒にマッピングしているのかわかりません。

このクラスは、TreeMap インスタンスによってサポートされる Set インターフェースを実装します。このクラスは、使用されるコンストラクターに応じて、ソートされたセットが要素の昇順、要素の自然な順序 (Comparable を参照)、またはセット作成時に提供されるコンパレーターに従ってソートされることを保証します。

于 2008-11-19T16:14:11.337 に答える
-3

基本的には要件に依存します。ハッシュマップが良い場合もあれば、ツリーマップが良い場合もあります。しかし、ハッシュマップは、それをソートするためのオーバーヘッドのための制約のみを使用する方が良いです.

于 2011-04-05T13:02:27.210 に答える