algorithm - 改进的算法实现

Question

我相信我们有算法实现（例如，特定排序算法的 c++ 实现）可能没有它们可能的效率。

我想写一篇研究论文，讨论如何改进这种实现。这可以是任何编程语言，但是 C、C++、Python、Java 或任何非专有语言都是理想的。

您是否知道任何您认为可能有改进空间的算法实现？

Answer 1

在我的经验中：

• 并行化：
  • Visual C++ - OpenMP
  • MATLAB 的并行计算工具箱，例如parfor
  • 集群计算，例如Lustre
• 硬件特定：
  • Intel Pentium 4 - SSE2 优化

特别是在 MATLAB 中，您可以通过编写可以通过MEX-functions访问的 C/C++ 函数来加快速度。

我意识到其中一些是专有的！

Answer 2

Jon Bentley（某处）有一个例子，说明旅行商算法如何在性能提高 50 倍的同时仍保持相同的大 O 签名。

在一次演讲中，他谈到那些对这个结果嗤之以鼻的学者，他们可能不介意自己的薪水因类似的因素而提高！

我个人已经将一些程序优化了 100 倍，而没有改变它们的 big-O。

这是一个在不改变 big-O 的情况下优化约 40 倍的示例。

如果尚未完成，您可以对任何程序执行此操作。它越大越好。

这有帮助吗？

Answer 3

已有大量论文描述了某些排序算法何时何地更好/改进。例如：直到某一点线性搜索最好快速排序。（我知道亵渎神明，但这取决于顺序（如果之前知道的话）和小数据集。）

我的建议是，在尝试发明新事物之前，先进行研究以找到这些论文。您的作品有可能是您不正确或已经发表。你的作品很有可能是新的。