5

私は2つの方法を試しました。

  1. HashMap を使用してすべてのアイテムの数をカウントし、マップをナビゲートします

    HashMap<Integer, Integer> doc_counts = new HashMap<Integer, Integer>();
for (int i = 0; i < p; ++i) {
    int doc = alld[i];
    Integer count = doc_counts.get(doc);
    if (null == count)
        count = 0;
    doc_counts.put(doc, count + 1);
}
// to now it cost 200ms already
for (Entry<Integer, Integer> item : doc_counts.entrySet()) {
    heapCheck(h, hsize, item.getKey(), item.getValue());    // heap sort top hsize items
}

  2. 最初に配列をソートし、ヒープソートを使用して上位 N を取得します。

    Arrays.sort(alld, 0, p); // the sort costs about 160ms
int curr = alld[0];
int count = 0;
for(int i = 0; i < p; i++) {
    int doc = alld[i];
    if(doc == curr) {
        ++count;
    } else {
        ++nHits;
        //curr += base;
        heapCheck(h, hsize, curr, count);
        curr = doc;
        count = 1;
    }
}
//
// Handle the last document that was collected.
heapCheck(h, hsize, curr, count);

1,600,000 個のアイテムを含む配列でテストすると、2 番目のメソッドのコストは約 170 ミリ秒で、ほとんどの時間は並べ替え (約 160 ミリ秒) に費やされ、最初のメソッドはすべてのアイテムを HashMap に追加するだけでも 200 ミリ秒かかることがわかります。パフォーマンスを向上させたり、より高速なマップまたはソート関数を見つけたり、並列関数に変更してマルチスレッドを使用したりするにはどうすればよいですか?

4

4 に答える 4

0

このタスクは並列化に適しています。FokJoinPool フレームワークを使用して、分割統治アルゴリズムを実装できます。たとえば、並列並べ替えアルゴリズムを使用して配列を並べ替え、160 ミリ秒を短縮できます。

または、Java 8 を試してみたい場合は、組み込みArrays.parallelSort()メソッドがあります。

于 2013-06-20T11:02:41.983 に答える
0

ソートしないでください - それは O(n log n) です。O(n) + O(N log N) のソリューションがあります。

  • Map<Integer, Integer>各数値 O(n) のカウントを保持するa を作成します。
  • カウントO(n)を作成/更新する配列を1回通過させます
  • おそらくNavigableマップO（N log N）を使用して、上位Nを最大に保ちながらマップを1回通過します

N << n の場合、O(n) です。N≒nならO(N log N)

于 2017-12-13T05:24:07.017 に答える