1

D-ary HeapC# でパフォーマンスの高いクラスを作成できないようです。BinaryHeap子の数 ( 、など)をハードコーディングするTernaryHeapと、パフォーマンスが大幅に向上するようです。

BinaryHeapmyと my D-ary Heapwithの間のコードの唯一の違いは、前者d=2でdは aconstであり、後者では readonly メンバー変数であることです ( readonly はパフォーマンスに影響しません)。

constバージョンはビットシフト操作にコンパイルされる可能性があるのに対し、メンバー変数バージョンはメモリフェッチ+デビジョンにコンパイルされる可能性があると思います。

クラスを次のように宣言する方法はありますか:

 public class DaryHeap<T, const uint(d)> : IEnumerable<T> where T : IComparable<T>

ここで、コンパイラに「はコンパイル時の値です」const uint(d)と伝えます。したがって、 my withは my と同じように機能します。duintD-ary Heapd=2BinaryHeap

4

2 に答える 2

1

D-ary ヒープ ( 1 , 2 )を試したところ、似たようなもの (これらのスレッドでは言及されていません) が見つかり、あきらめました。関連する D の値はそれほど多くありません。4と8はほぼすべてです。16、めったにありません。2、そうではありません：私のテストでは、4-aryは常に高速でした（「そうではない」場合でも）。また、2 の非べき乗もテストしましたが、これも言及されていません。

そこで、ハードコーディングされたバージョンをいくつか作成することにしました。これはいくつかのコーディング原則に違反していますが、最初に D-ary ヒープを使用した主な理由はパフォーマンスでした。

基本的に、重要な D の値は 2 つしかないため、コピー/貼り付けされるコードの量は実際にはそれほど多くありません。

于 2013-09-20T10:06:37.767 に答える
1

CLR ジェネリックは、C++ テンプレートよりもはるかに制限されています。

ただし、他の種類のテンプレートもあります。T4を例にとってみましょう。D-ary ヒープを T4 テンプレートとして記述し、そこから具体的なバージョンを生成できます。T4 との自動統合を可能にする Visual Studio を使用していると仮定します。これにより、DRY (テンプレート自体のみを変更するため) と高速 (最適な実装があるため) が維持されます。そして最高の部分は、C++ テンプレートで行うようなメタ言語ではなく、実際の言語を使用してコードを生成できることです。

于 2013-09-20T11:22:21.497 に答える