-4

我正在寻找一种标准方法来识别程序的运行时间复杂度。如此处所述，我不是在寻找通过查看代码来分析相同问题的解决方案，而不是在程序运行时通过其他一些参数。

考虑一个要求用户将二进制字符串转换为其十进制等效项的程序。当一次处理每个二进制数字时，这种程序的时间复杂度最坏应该是 O(n)。有了一些智能，运行时间可以减少到 O(n/4)（一次处理来自二进制字符串的 4 位数字，假设二进制字符串对于所有 k=1,2,3 都有 4k 位......）

我用 C 语言编写了这个程序，并使用 time 命令和一个使用 gettimeoftheday（两者）的函数来计算具有 64 位四核处理器（每个内核为 800 MHZ）的 linux 机器上的运行时间，分为两类：

  1. 系统正常负载时（核心使用率 5-10%）
  2. 系统负载较重时（核心使用率 80-90%）

以下是 O(n) 算法的读数，二进制字符串的长度为 100000，在正常负载下：

Time spent in User (ms) - 216
Time Spent in Kernel (ms) - 8
Timed using gettimeofday (ms) - 97

以下是 O(n) 算法的读数，二进制字符串的长度为 200000，在高负载下：

Time spent in User (ms) - 400
Time Spent in Kernel (ms) - 48
Timed using gettimeofday (ms) - 190

我在找什么：

  1. 如果我使用 time 命令，我应该考虑哪个输出？真实的，用户还是系统？
  2. 是否有计算程序运行时间的标准方法？
  3. 每次执行这些命令时，我都会得到不同的读数。考虑到代码不变，我应该采样多少次才能使平均值始终相同。
  4. 如果我想使用多个线程并通过在此类程序上调用 execve 来测量每个线程中的时间怎么办。

根据我所做的研究，我没有遇到任何标准方法。此外，我似乎使用的任何命令/方法每次都会给我不同的输出（我理解这是因为上下文切换和 cpu 周期）。我们可以在这里假设我什至可以使用依赖于机器的解决方案。

4

1 回答 1

0

要回答您的问题：

  1. 取决于您的代码在做什么，输出的每个组件time可能很重要。这个问题涉及这些组件的含义。如果您正在计时的代码不使用系统调用，那么计算“用户”时间可能就足够了。我可能只是使用“真实”时间。
  2. 有什么问题time？如果您需要更好的粒度（即您只想对一段代码而不是整个程序进行计时），您总是可以在您正在分析的代码块之前获取开始时间，运行代码，然后获取结束时间，然后计算为您提供运行时的差异。切勿使用gettimeofday，因为时间不会单调增加。系统时间可由管理员或 NTP 进程更改。你应该clock_gettime改用。
  3. 为了最大程度地减少运行之间的运行时间差异，我会检查 CPU 频率缩放是否关闭，特别是如果你得到非常不同的结果。这让我以前很困惑。
  4. 一旦开始进入多个线程，您可能想要开始查看分析器。gprof 是一个很好的起点。
于 2013-05-15T08:30:41.787 回答