2

我有一个正在为一个项目运行的代码。它是 O(N^2)，对于我来说，N 是 200。有一种算法可以将此 O(N^2) 转换为 O(N logN)。这意味着，使用这种新算法，它应该快 100 倍左右。但是，我只得到了 2 倍的增长（也就是 2 倍快）。

我试图缩小范围，看看我是否搞砸了，或者这是否是我编写这个程序的方式所固有的。对于初学者，我在嵌套类中有很多函数开销。例如，我有很多这样的（在许多循环中）：

energy = globals->pair_style->LJ->energy();

由于我在实际数据方面得到了正确的结果，只是错误的速度增加，我想知道函数开销是否真的会导致速度降低多达 50 倍。

谢谢！

4

5 回答 5

9

首先，您的解释O(N logN)比O(N^2)for快约 100 倍N=200是不正确的。big-Oh 表示法处理limit 中的上限和行为，并且不考虑复杂性中的任何乘法常数。

其次，是的，由于管道中断，现代硬件函数调用往往相对昂贵。要了解这对您的情况有多大影响，您必须提出一些微基准。

于 2011-10-12T13:01:34.723 回答
4

绝对最大的打击是缓存未命中。L1 缓存未命中相对便宜，但是当您在 L2（或 L3，如果有）上未命中时，您可能会丢失数百甚至数千个周期到即将到来的停顿。

事情是虽然这可能只是问题的一部分。在对代码进行概要分析之前，不要优化您的代码。识别慢速区域，然后找出它们慢速的原因。一旦您了解了它运行缓慢的原因，您就有很好的机会对其进行优化。

顺便说一句，O 表示法非常方便，但不是全部和全部。我已经看到 O(n^2) 算法的工作速度明显快于 O(n log n)，因为它们缓存的效率更高。

于 2011-10-12T13:00:17.390 回答
1

Big O 表示法的重要之处在于它只指定了执行时间的限制，随着数据集大小的增加——任何常量都会被丢弃。虽然 O(N^2) 确实比 O(N log N) 慢，但实际运行时间可能是 N^2 与 1000N log N - 也就是说，O(N^2) 可能比O(N log N) 在一些数据集上。

没有更多细节，很难说更多 - 是的，函数调用确实有相当多的开销，这可能就是为什么你没有看到性能有更大的提升 - 或者可能只是你的 O( N log N) 在您大小的数据集上表现不佳。

于 2011-10-12T13:04:24.500 回答
1

我研究过图像处理算法，并且每像素调用一个函数（即：对于 640x480 将是 307200）会显着降低性能。尝试将您的函数声明为内联，或将函数设为宏。这可以快速显示是否是因为函数调用。尝试查看一些分析工具。VS 2010 自带了一些不错的工具，否则还有 Intel VTune、glowcode。他们可以帮助显示您在哪里花费时间。

恕我直言，我认为 1600 次函数调用根本不会降低性能（200 log 200）

于 2011-10-12T13:08:59.400 回答
1

我建议使用对其进行分析

关于分析的大常见问题解答主题在这里：如何分析在 Linux 中运行的 C++ 代码？

  • gprof（需要编译时检测）
  • valgrind --tool=callgrind和kcachegrind; 具有出色可视化效果的出色工具-此处的屏幕截图：

在此处输入图像描述

在此处输入图像描述

于 2011-10-12T13:13:25.247 回答