-1

さまざまな文字列を含む大きなファイルがあります。ファイルを解析して、ファイルに存在するさまざまな単語の単語数を見つける必要があります。その後、カウントの昇順で単語を並べる必要があります。

私のアプローチは、ファイルを解析し、単語がキーでカウントが値であるハッシュマップに単語を格納することでした。ファイルの解析を進めると、カウントが更新されます。解析が完了したら、カウントに基づいてコレクションを並べ替えます。

上記のアプローチは非常に単純で、ファイルが大きいことを考慮していません。

大きなファイルを処理するために、どのような変更をアプローチに取り入れるべきですか？

4

4 に答える 4

1

それで、コメントの私の声明にもう少し明確にするために：

あなたが大きなファイルを持っていると仮定しましょう。すべてを単語ごとに読み取るには、N回の操作が必要です。I / Oは一般的に遅いため、これがボトルネックになります。

カウントスキームには、を使用しMap<String, Integer>ます。表示されるすべての単語がマップに配置され、特定の単語に複数回遭遇した場合は、1を追加します。一般に、特定のキーと値のペアの追加は一定時間（HashMap）であり、可能かどうかを判断します。Integerマップに新しいものを入れるかどうかも一定です。

したがって、ファイル内の単語をカウントするための全体的なランタイムパフォーマンスは、O（N）+ Cになります。ここで、Nは主にI/Oによるものです。

ここで、10個のスレッドを使用するとします。大きなファイルを10個のチャンクに分割し、各スレッドに値をに挿入させますConcurrentHashMap。全体的な実行時の複雑さは、（潜在的に）10分の1に減少したことを除いて、変更されていません。

追加のスレッドを使用したランタイムはO（t（1/10）N）+ Cになりますが、それでもO（N）+Cになります。

これをより効率的にする唯一の方法は、使用する線形スキャン方法を線形時間よりも効率的に変更できるかどうかです。

于 2013-03-13T16:11:25.737 に答える
1

まず、aを使用しMapて単語数を決定します。

    String[] words = {"one", "two", "three", "two", "three", "three"};
    Map<String, Integer> map = new HashMap<String, java.lang.Integer>();
    for (String word : words) {
        int count = 0;
        if (map.containsKey(word)) {
            count = map.get(word);
        }
        map.put(word, ++count);
    }
    System.out.println(map);
    --> output: {two=2, one=1, three=3}

次に、TreeMapまたは新しい「カスタム」キー/値クラスを使用して、カウントで並べ替えます。

使用TreeMap：

private static void sortUsingTreeMap(Map<String, Integer> map) {
    TreeMap<String, Integer> sorted = new TreeMap<String, Integer>(new MyComparator(map));
    sorted.putAll(map);
    System.out.println(sorted);
}

static class MyComparator implements Comparator<String> {
    private Map<String, Integer> map;

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

    @Override
    public int compare(String o1, String o2) {
        return map.get(o1).compareTo(map.get(o2));
    }
}
--> output: {one=1, two=2, three=3}

新しいキー/値クラスの使用：

private static void sortUsingKeyValueClass(Map<String, Integer> map) {
    class KeyValue implements Comparable<KeyValue> {
        private final Integer count;
        private final String word;

        public KeyValue(Integer count, String word) {
            this.count = count;
            this.word = word;
        }

        @Override
        public int compareTo(KeyValue o) {
            return count.compareTo(o.count);
        }

        @Override
        public String toString() {
            return word + "=" + count;
        }
    }

    List<KeyValue> keyValues = new ArrayList<KeyValue>();
    for (String word : map.keySet()) {
        keyValues.add(new KeyValue(map.get(word), word));
    }
    Collections.sort(keyValues);
    System.out.println(keyValues);
}
--> output: [one=1, two=2, three=3]

また、パフォーマンスの面で必要であることがわかるまで、ミックスへのスレッドの追加を延期することも付け加えておきます。ここで他の人が述べているように、結果を同時に処理しても、不十分な実装は保存されません。

于 2013-03-13T16:11:49.640 に答える
1

複数のスレッドを使用するHashMap場合は、を使用せず、ConcurrentHashMap代わりに（javadoc）を使用してください。

Integer値がすでに存在する場合は、値の更新時に何らかのチェックを実行する必要があります。そのプロセスの詳細については、この投稿を参照してください。

データを入力した後のマップの並べ替えについては、この投稿を参照してください。

于 2013-03-13T15:44:18.617 に答える
0

コメントで述べたように、スレッドは、自分のソリューションを他の人のソリューションよりも少しだけ速くしたいというタイブレーカーの状況に役立ちます。スレッド内で実行されているものが本当に遅い場合、スレッドは役に立ちません。

ハッシュマップは、質問の最初の部分の時間計算量に最適です。

質問の2番目の部分では、セット、2次元配列、および最初の部分で使用したデータ構造を使用します。ファイルをもう一度解析し、新しい各単語をセットに追加し、作成済みのハッシュマップでその単語数を確認すると、各単語をその単語数のインデックス位置に格納できます。その後、配列を逆方向にトラバースするだけで、カウント順に単語が表示されます。

于 2013-03-13T15:38:59.690 に答える