1

サイズが 500 万を超えるベクトルがあり、そのたびにベクトルから最小のキーを持つ 1 つの要素を選択し、この要素に対して何らかの処理を行います。ただし、この特定の要素を処理すると、ベクトル内の残りのすべての要素も影響を受け、キーが更新されます。次回、ベクトルから最小のキーを持つ要素を取得したい場合は、ベクトルをもう一度並べ替える必要があります。問題は、ベクトルから最小の要素を取得する回数が 50 万回に達するため、プログラムの実行が非常に遅くなることです。より明確に理解できるように、次のコードを記述して説明します。

void function(vector<MyObj*>& A)
{ //A.size() is near 5 million, maybe even more such as 50 million.
    make_heap(A.begin(), A.end(), compare); // compare function is self-defined.
    for (int i=0; i<500000; i++)
    {
        MyObj* smallest_elem = A.front();
        pop_heap(A.begin(), A.end());
        A.pop_back();
        Process_MyObj(smallest_elem); // here all of the elements 
                                      // in A will be affect, causing 
                                      // their keys changed.

        make_heap(A.begin(), A.end()); // Since all elements' keys in A changed,
                                       // so heap sorting A once again is 
                                       // necessary in my viewpoint.
    }
}

コードをできるだけ効率的に実行する方法はありますか? 並列化など、アルゴリズムの限定的な改善ではなく、どんなアイデアでも大歓迎です。どうもありがとう！

4

3 に答える 3

0

にどれくらいの時間がProcess_MyObj費やされ、ヒープ操作にどれくらいの時間が費やされているか - 50/50%、80/20% ?
2 つのバランスを取りたいので、これは重要です。次の一般的な設定を検討してください。

Make a Todo list
Loop:
    work on items ...
    update the Todo list

リストの更新に時間がかかりすぎるということは、実際の作業に十分な時間がないことを意味します。したがって、最初にプロセス/ヒープ時間の比率を測定します。
これを行う安価な方法は、2 回目の実行を行い、2 回実行すること ですProcess_MyObj。compare

 P + H = 1.0 sec
2P + H = 1.7 sec
=> P = .7, H = .3: P / H = 70 % / 30 %.


make_heap線形時間で実行されます -- how-can-stdmake-heap-be-implemented-while-make-at-max-3n-comparisons を参照してください-- そのため、高速化は難しいでしょう。値が定数の場合、64 ビット <32 値、32 インデックス> のヒープは、ポインターよりもキャッシュ効率が高くなります。

cstheory.stack の whats -new-in-purely-functional-data-structures-since- okasaki には、ほとんどが理論的な数十の論文がリストされていますが、1 つまたは 2 つが問題に関連している可能性があります。

実際の高速化は、ほとんどの場合、一般的なものではなく、問題固有のものです。本当の問題についてもっと教えていただけますか？

追加: ほとんどの pop が小さく、push が大きい場合は、大きなソート済みリストの前に小さなキャッシュヒープを配置してみてください。擬似コード:

push:
    push( cacheheap )
pop:
    return min( cacheheap, bigsortedlist )

これは、実際の CPU キャッシュに残っている場合に効果的です。 cacheheapymmv。(ごまかして、毎回ソートする代わりに不正確な
ままにしておくことができるかもしれません。)bigsortedlist

于 2014-03-26T10:25:05.833 に答える