2

我为某事写了一个新算法。现在我需要将它与现有的方法进行比较，其中一些已经有 10 年的历史了。

我的想法是查看多年来不同处理器的基准测试，以确定我的处理器（i7-920）比 2003 年的平均处理器快多少。然后我只需将旧方法的执行时间除以加速因子并使用这些数字与我自己的算法进行比较。

  1. 有没有做过这样的事情？所以我不会重做现有的工作。
  2. 这种比较可以通过其他方式进行吗？
  3. 是否有一些我可以参考的关于此类比较的科学论文？
4

4 回答 4

4

我不知道其中哪些对你来说是可能的，但这里有一个我能想到的选项列表：

  1. 在您的机器上与您的机器并排运行它们的实现。
    这是最好的选择。

  2. 重写他们的实现并执行（1）。
    您最好需要将其与他们的测试进行比较，以确保您获得大致相似的结果。

  3. 找到一个实现其算法（或多个库）的库并执行（1）。
    如果可能，我建议使用多个库，因为单个库可能无法有效地实现该算法。您可能还想将这些与他们的测试进行比较。

  4. 在数学上比较算法。
    这可能很困难，但并非不可能。

  5. 做你提出的。
    (a) 我不建议这样做，因为除了处理器速度之外，您的计算机中还有其他决定因素会影响算法的速度。获得一个完美平衡这些的方程可能会非常困难。
    (b) 顶级计算机和低端计算机之间存在巨大差异，因此使用平均值并不是一个特别好的主意。如果作者没有提供这方面的细节，恐怕你的基准不太可能太准确。

  6. 出去购买一台与所需测试所使用的规格相似的机器进行基准测试。
    一台 10 年的机器应该很便宜，如果你能找到的话。另见 (5.b)。

  7. 联系作者以允许任何其他选项。
    论文通常会提供作者的联系方式，或者如果他们有任何形式的在线存在并且您在使用 Google 方面还算得上，您应该能够在其他地方找到他们。

于 2013-07-08T16:12:58.590 回答
1

如果我正在查看您的结果，如果您试图以这种方式证明不到一个数量级的加速，我会很生气。决定算法性能的变量有很多，我怀疑通用基准测试能否捕获正确的基准。我的黄金标准是由同一个程序员实现的新旧算法，在相同的硬件上运行类似的优化工作。在实验算法文献中，使用以前作者的实现而不是制作新的实现是司空见惯的，但使用不同的硬件却不是。

于 2013-07-08T12:57:03.787 回答
0

算法性能通常以大 O 术语衡量，为此最好计算基本操作，如比较，并针对一系列输入大小进行计算。

如果您必须测量总时间，至少要消除其他差异来源。正如@larsmans 所说，在同一个处理器上进行。

此外，如果有现有的工作，重复它也没有坏处。一般来说，在科学领域，这是一件好事。

于 2013-07-08T12:41:04.147 回答
0

您应该尝试减少两次运行之间不同因素的数量。我认为只是在同一台机器上并排运行两种算法和/或比较它们的大 O 时间都是同样有效和重要的。您还应该尝试使用更新的库和其他外部功能；使用过时的也是导致计时结果的原因。

于 2013-07-08T17:57:13.443 回答