1

我似乎无法D-ary Heap在 C# 中创建一个高性能类；硬编码的孩子数量（BinaryHeap,TernaryHeap等）似乎具有明显更好的性能。

BinaryHeapmy和 my D-ary Heapwith之间代码的唯一区别d=2是，前者d是 a const，后者是 readonly 成员变量（并且readonly 对性能没有影响）。

我猜该const版本可能会编译为位移操作，而成员变量版本可能会编译为内存获取 + 分区。

有没有办法可以像这样声明我的类：

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

其中const uint(d)会告诉编译器“d是编译uint时值”。因此，会让 my D-ary Heapwithd=2与 my BinaryHeap.

4

2 回答 2

1

当我尝试使用 D-ary 堆（1 , 2）时，我发现了类似的东西（那些线程中没有提到），然后放弃了。真正相关的 D 值并不多。4和8差不多。16，很少。2，不是真的：4-ary 在我的测试中总是更快（即使在它“不应该”的情况下）。我还测试了 2 的非幂，也没有提到，因为它们很烂。

所以我决定制作几个硬编码版本。这违反了一些编码原则，但由于性能是我首先使用 D-ary 堆的主要原因，所以不将 D 设为常量的性能损失简直是不可接受的。

基本上，只有 2 个 D 值很重要，因此复制/粘贴代码的数量实际上并没有那么高。

于 2013-09-20T10:06:37.767 回答
1

CLR 泛型比 C++ 模板更受限制。

不过，还有其他类型的模板。以T4为例。您可以将 D-ary 堆编写为 T4 模板，然后从中生成具体版本。我假设您使用 Visual Studio，它可以自动与 T4 集成。这使事情保持干燥（因为您只修改模板本身）而且速度也很快（因为您有最佳实现）。最好的部分是您可以使用真正的语言来生成代码，而不是像使用 C++ 模板那样使用元语言。

于 2013-09-20T11:22:21.497 回答