如何计算动态规划算法每秒更新的单元数

Question

我正在尝试使用每秒单元更新数（CUPS）指标来衡量序列比对算法的性能。我看到几篇论文（ref1，ref2）中使用了该指标，但没有一篇论文解释了它是如何真正计算的。

它本质上是在处理二维矩阵中的单元。

我的尝试如下：

gettimeofday(&tv1, NULL);
alignment_score = alignment(seq1, seq2, seq1_len, seq2_len);
gettimeofday(&tv2, NULL);

double elapsed_time =  (double) (tv2.tv_usec - tv1.tv_usec) / 1000000 +(double) (tv2.tv_sec - tv1.tv_sec);
printf ("elapsed time = %f seconds\n",elapsed_time);
double gcups = ((seq1_len * seq2_len )/1000000000.0) / (elapsed_time) ;
printf("GCUPS: %10f \n", gcups);

但我不确定这是否是正确的定义。您能否确认或给我提供有关如何测量的参考？

Answer 1

您使用

gettimeofday

进行时间流逝测量。我建议使用

clock_gettime

。

clock_gettime

（带有

CLOCK_MONOTONIC

标志）保证是单调的。这意味着即使系统时钟被调整，返回的时间也将始终相对于程序的启动而增加。这对于基准测试至关重要，因为它确保测量的时间反映实际的执行时间。但

gettimeofday

并不是单调的。由于NTP同步或闰秒的原因，系统时钟可能会发生调整，导致返回值发生跳跃，影响基准测试精度。

此外，在某些系统上，与

clock_gettime

（微秒）相比，

gettimeofday

可以提供更高的分辨率（纳秒）。这样可以更精确地测量短执行时间。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define UNUSED(v) ((void) v)
#define BILLION   1000000000

int main(int argc, char **argv)
{
  UNUSED(argc);
  UNUSED(argv);

  struct timespec start, end;

  clock_gettime(CLOCK_MONOTONIC, &start);

  /* Do your hard work here */

  /* first argument is of type clockid_t. possible values: CLOCK_MONOTONIC and CLOCK_REALTIME */
  /* I think glibc supports CLOCK_MONOTONIC_RAW too */
  clock_gettime(CLOCK_MONOTONIC, &end);

  int64_t nanoseconds = (end.tv_sec - start.tv_sec) * BILLION;
  nanoseconds += (end.tv_nsec - start.tv_nsec);
  double seconds = (double)nanoseconds / (double) BILLION;
  printf("the hard work took %f seconds\n", seconds);

  return EXIT_SUCCESS;
}