1

私はある種の連続的なダイクストラである Fast Marching アルゴリズムを実装しています。多くの論文で読んだように、フィボナッチ ヒープはこの目的に最も適したヒープです。

ただし、私のコードを callgrind でプロファイリングすると、次の関数が実行時間の 58% を占めていることがわかります。

int popMinIdx () {
    const int idx = heap_.top()->getIndex();
    heap_.pop();
    return idx; 
}

具体的にpop()は、全体の実行時間の 57.67% を占めています。

heap_は次のように定義されます。

boost::heap::fibonacci_heap<const FMCell *, boost::heap::compare<compare_cells>> heap_;

「そんなに」時間がかかるのは普通ですか、それともパフォーマンスを改善するためにできることはありますか?

十分な情報が提供されていない場合は申し訳ありません。できるだけ簡潔にしようとしました。必要に応じてさらに情報を追加します。

ありがとうございました！

4

2 に答える 2

4

他の答えは大部分に言及していません: もちろん pop() はあなたの時間の大半を占めます: それは実際の仕事を実行する唯一の関数です!

読んだことがあるかもしれませんが、フィボナッチ ヒープの操作の限界は償却限界です。これは、適切なシーケンスで十分な操作を実行すると、境界が平均化されることを意味します。ただし、実際のコストは完全に隠されています。

要素を挿入するたびに、何も起こりません。ルートリストにスローされるだけです。ブーム、O(1) 時間。2 つのツリーをマージするたびに、そのルートがルート リストにリンクされるだけです。ブーム、O(1) 時間。しかし、待ってください、あなたの構造は有効なフィボナッチ ヒープではありません! そこで pop() (または extract-root) の出番です。この操作が呼び出されるたびに、ヒープ全体が正しい形状に再構築されます。ルートが削除され、その子がルート リストにカットされます。次に、ルート リストに同じ次数 (子の数) を持つ 2 つのツリーが存在しないように、ルート リスト内のツリーのマージを開始します。

したがって、Insert(e) と Merge(t) のすべての作業は、実際には Pop() が呼び出されるまで遅延され、その後すべての作業が行われます。他の操作はどうですか？

Delete(e) は美しいです。Decrease-Key(e, -inf) を実行して要素 e をルートにします。そして、Pop()! を実行します。繰り返しますが、作業は Pop() によって行われます。

Decrease-Key(e, v) はそれ自体で作業を行います: e をルート リストにカットし、カット カスケードを開始して、その子もルート リストに入れます (子リストもカットできます)。したがって、Decrease-Key は多くの要素をルート リストに入れます。どの関数がそれを修正する必要があるか推測できますか?

TL;DR: Pop() はフィボナッチ ヒープの主力です。他のすべての操作は、Pop() 操作の作業を作成するため、効率的に実行されます。Pop() は作業を収集し、一度に実行します (最大 O(n) かかる場合があります)。「グループ化された」作業は、各操作を個別に行うよりも高速に実行できるため、これは実際には非常に効率的です。

そうです、Pop() があなたの時間の大部分を占めるのは自然なことです!

于 2015-09-11T15:26:29.857 に答える
1

フィバナッチ ヒープの pop() の償却実行時間は O(log n) で、最悪の場合は O(n) です。ヒープが大きい場合、アルゴリズムで CPU 時間の大部分を簡単に消費する可能性があります。特に、使用する可能性が高い他の操作のほとんどが O(1) ランタイム (挿入、トップなど) を持っているためです。

fibonacci_heap などのテンプレート化されたデータ構造/コンテナーはインライン化された関数の使用に重きを置いているため、デバッグ情報 (-g) を使用して、好みの最適化レベル (-O3 など) で callgrind を試すことをお勧めします。測定している CPU サイクルのほとんどが、最適化された実行可能ファイルに存在しない可能性があります。

于 2014-02-17T01:59:43.267 に答える