附录:实施研究论文

实施论文的提示:( algorithm另请参阅data structure）

  • 别。从明显的解决方案和合理的数据结构开始。
    “现代”算法往往具有较低的理论复杂性，但具有较高的常数因子和很多实施复杂性。其中一个经典例子是斐波那契堆。他们很难得到正确的，并有一个巨大的不变因素。已经发表了多篇论文，比较了不同工作负载下堆的实现方式，总体而言，4或8元的隐含堆总是排在前列。即使在Fibonacci堆应该更快（由于O（1）“减少键”）的情况下，使用Dijkstra的深度优先搜索算法的实验表明，当他们使用直接堆去除和加法时，它的速度更快。

类似地，对比更复杂的红黑或AVL树也可以找到对照或者跳过列表。在现代硬件上，“较慢”的算法可能足够快，甚至更快。

最快的算法经常可以被几乎一样快速且容易理解的算法取代。

道格拉斯W.琼斯，爱荷华大学

增加的复杂性必须足以使得回报实际上值得。另一个例子是缓存驱逐算法。不同的算法可以具有高得多的复杂度，仅命中率的小改进。当然，您可能无法在测试之前进行测试，直到您有一个可行的实施并将其整合到您的程序中。

有时候这篇论文会有图表，但很像只发布正面结果的趋势，但这些倾向往往会偏向于表示新算法的优点。

  • 选择正确的纸张。
  • 寻找他们的算法声称击败和实施的论文。

通常，早期的论文会更容易理解，并且必须具有更简单的算法。

并非所有的文件都很好。

查看论文写入的上下文。确定有关硬件的假设：磁盘空间，内存使用情况等。一些较旧的论文在70年代或80年代进行了合理的不同折衷，但不一定适用于您的使用案例。例如，他们认为什么是“合理的”内存与磁盘使用的权衡。内存大小现在增加了数量级，并且SSD改变了使用磁盘的延迟惩罚。同样，一些流媒体算法是为路由器硬件而设计的，这可能会使转换成软件变得非常痛苦。

确保算法对数据保持的假设。

这将需要一些挖掘。你可能不想实现你找到的第一篇论文。

一个良好的理解可能会让你从论文中提取关键的想法，并且可能将这个想法应用于你的问题，这可能比重新实现整个事情更简单。

  • 数据结构或算法的原始文件并不总是最好的。后来的论文可能会有更好的解释。

  • 一些论文发布了可以与之比较的参考源代码，但是

    1) 学术代码几乎普遍可怕
    2) 谨防许可限制（仅限“研究目的”）
    3) 提防错误; 边缘情况，错误检查，性能等。

还要注意GitHub上的其他实现：它们可能与您的bug相同（或不同）。

有关此主题的其他资源：