-1

我的意思是，要衡量某种算法的性能，我需要用某个单位来衡量。所以，基本上如果我忽略对象的声明和定义而只考虑操作，你将如何估计每个操作在运行时消耗的时间？

4

4 回答 4

1

在c++11你有std::chrono图书馆（见std::chrono）。否则，您可以使用boost::chrono（参见boost::chrono）。这两个是您可以开始使用的非常基本的时间测量库。

编辑：在 c++0x 中你有这个clock()功能——但正如评论部分所述——它不是一个非常准确的测量。此外，大多数平台还为与计时相关的操作提供某种 API。

如何衡量性能取决于上下文。首先，您需要在足够大且足够多样化的样本数据上比较性能。足够大意味着它至少可以在几秒钟内测量。足够多样化意味着它可以统一地或单独地覆盖所有运行场景的重复（您至少应该知道样本数据代表什么切割）。

对于足够简单的情况，您要做的第一件事是将您的算法划分为尽可能多的部分，让我们称它们为A_1,...,A_N（或者可能A_1...A_N是同一问题的不同解决方案，这个概念仍然成立）。您要做的是测量每个分区在相同样本数据上花费的时间。在伪代码中：

times <- (0,...,0) //vector of size N
for each input in sample data:
    start = now()
    //Run A_1 on input
    end = now()
    times[1] <- times[1] + (end-start)
    ...
    ...
    ...
    start = now()
    //Run A_N on input
    end = now()
    times[N] <- times[N] + (end-start)

在此运行结束时，您会看到一个时间向量，它显示您在每个元素上花费了多少时间。这是最基本的方法。但剖析的关键要素是：解剖青蛙的方法有很多。您还可以查看您在可以从算法的许多分区调用的特定操作上花费了多少时间。您可以选择查看加载/存储操作的数量、缓存性能等。变化很多，而且巨大的回报通常来自意想不到的来源（至少对于粗心的观察者而言）。

对于更高级的分析，您可以使用第 3 方分析框架（一些 IDE 带有内置分析功能）。

于 2013-02-18T19:21:35.580 回答
0

在现代机器上，它很大程度上取决于上下文。大多数指令将在一个时钟内执行；在某些机器上，您甚至可以在每个时钟中获得几条指令。另一方面，内存访问时间可能会有很大差异，具体取决于被访问的位置是在缓存中、在主内存中还是被换出——如果操作系统必须进入磁盘来映射内存，你说的是访问大约需要几毫秒，就好像数据在顶级缓存中一样，它可能几乎是立即的。（换句话说，我们谈论的是 100 皮秒而不是 10 毫秒。）这就是为什么您会听到很多关于局部性的信息。

于 2013-02-18T19:19:13.867 回答
0

有很多方法可以衡量性能，而“正确”的方法在很大程度上取决于您实际在做什么。很多时候，确定性能的简单方法就是让应用程序做它通常做的事情，然后测量时间——如果需要的时间足够长，只需使用秒表（例如手机应用程序，打开实际的手表或类似的）会很好用。对于较短的时间段，您可能需要其他方法 - 一直到使用带有“TSC”的“CPU时钟周期” - CPU本身的时间戳计数器。

如果它只需要很短的时间，但你的应用程序会做很多事情，那么多次运行相同的代码。

对于其他应用程序，由于花费的时间并没有真正花费在 CPU 时钟周期上，因此变得更加困难——例如，如果您的应用程序的一部分正在读取一些大文件，那么所使用的 CPU 时间可能只有 2-3%，剩下的时间花在等待硬盘从那里的实际磁盘中获取数据。

同样，如果应用程序使用网络，CPU 可能只使用通过 1GB 网络链接发送数据包所需时间的百分之几。

数据的类型以及数据的组织、排序和使用方式也很重要。如果您从已排序的源插入要排序的内容，它的执行可能与未排序的项目列表完全不同 - 令人惊讶的是，它可能更好或更糟，具体取决于数据的存储/排序方式。

“查看代码”并确定其性能可能非常困难。除了“代码看起来像什么”之外，还有很多其他因素会影响它。

如果您有一个可以运行的现有应用程序，请测量它的性能，并使用分析软件来查看一个好的计划在哪里花费了多少时间。

于 2013-02-18T19:34:46.083 回答
0

所有这些答案都取决于您运行算法的硬件。如果您想对算法的复杂程度进行通用测量，则应该执行大 O 和大 Omega 分析。

如果您对此有更多疑问，请告诉我，但根据您的问题标题，您应该寻找算法作为其数据输入函数的指令数量，而不是基于特定硬件测量性能。

于 2013-02-18T19:41:37.647 回答