c - 如何比较 C 中排序执行时间不可预测的结果

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 4 年前。

Improve this question

我试图在文件中写入以下两种排序(qsort 和插入)的执行时间，并将它们作为参数提供一个随机数组。但第二阶段每次的结果clock() - clock()是 0 或看起来不正确的东西。例如，如果我只有插入排序的计算，结果是正确的(〜2800ms，2900ms ...)如果我两者都有，结果是错误的(〜2800-2900ms ...)和(0ms，15ms)其中那是不可能的。

我尝试先进行qsort，然后进行插入，但结果相同，但以其他方式(30ms，16ms ...)和(0ms，0ms ...)。我认为出于某种原因，任何类型的第一个计算都会干扰第二个计算的初始化或时钟。任何帮助将不胜感激。

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

#define NO_DATA 200000

void quicksort_int(int left,int right,int *s)
{
int i,j,temp,mid,k,x;
  if(left<right)    
   {
      i=left;
      j=right;
      mid=(left+right)/2;
      x=s[mid];
          while(i<j)
          {
             while(s[i]<x) i++;
             while (s[j]>x) j--;
             if (i<j)
             {
                 if(s[i]==s[j])
                 {
                     if(i<mid) i++;
                     if(j>mid) j--;
                 }
                 else
                 {
                  temp=s[i];
                  s[i]=s[j];
                  s[j]=temp;
                 }
             }
          }
      quicksort_int(left,j-1,s);
      quicksort_int(j+1,right,s);
   }
}


void straight_insert_int(int *s,int n)
{
  for (int i=1;i<n;i++)
  {
      int x=s[i];
      int j=i-1;
      while((x<s[j])&&(j>=0))
      {
          s[j+1]=s[j];
          j=j-1; 
      }
      s[j+1]=x; 
  }  
}





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

  clock_t begin,end;
  double time_taken,time_taken2;
  FILE *fptr;
  fptr=fopen("E:\\results.txt","w");
  int *p=(int*)malloc(200000*sizeof(int));
  int *s=(int*)malloc(200000*sizeof(int));
  fprintf(fptr,"    QUICKSORT INSERTION SORT\n");
  srand(time(NULL));
 for(int i=0;i<3;i++)
 {
       if(fptr == NULL)
     {
        printf("Error!");   
        exit(1);             
     }
      for(int i=0;i<NO_DATA;i++)
      {
          p[i]=rand();
          s[i]=p[i];
      }
      begin=clock();
      straight_insert_int(p,NO_DATA);
      end=clock();
      time_taken=(double)(end-begin)*1000/CLOCKS_PER_SEC;

      printf("Str_ins attempt %d Completed!\n",i);

      begin=clock();
      quicksort_int(0,NO_DATA,p);
      end=clock();
      time_taken2=(double)(end-begin)*1000/CLOCKS_PER_SEC;

      printf("Quicksort attempt %d Completed!\n",i);
      fprintf(fptr,"%d.  %1d ms       %1d ms\n",i,(int)time_taken2,(int)time_taken);

 }
 fclose(fptr);
 return (EXIT_SUCCESS);
}

我预计 qsort 单独的输出约为 30 毫秒，这是正确的。我预计单独插入排序的输出约为 2800 毫秒，这是正确的。我预计插入排序和 qsort 的输出分别为 ~2800ms 和 ~30ms，实际结果为 ~2800ms ~0-16ms。

Answer 1

问题是您将相同的数据传递给两个函数，因此您要针对一种已排序的数据对一种随机数据进行计时。

较长的变量名称不会使您的代码变慢，而且可以非常容易地发现此类问题。这是更正和重构的版本。

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

#define NO_DATA 200000

void quicksort_int(int left, int right, int *s)
{
    int i, j, temp, mid, x;
    if (left < right)
    {
        i = left;
        j = right;
        mid = (left + right) / 2;
        x = s[mid];
        while (i < j)
        {
            while (s[i] < x) i++;
            while (s[j] > x) j--;
            if (i < j)
            {
                if (s[i] == s[j])
                {
                    if (i < mid) i++;
                    if (j > mid) j--;
                }
                else
                {
                    temp = s[i];
                    s[i] = s[j];
                    s[j] = temp;
                }
            }
        }
        quicksort_int(left, j - 1, s);
        quicksort_int(j + 1, right, s);
    }
}

void straight_insert_int(int *s, int n)
{
    for (int i = 1; i < n; i++)
    {
        int x = s[i];
        int j = i - 1;
        while ((x < s[j]) && (j >= 0))
        {
            s[j + 1] = s[j];
            j = j - 1;
        }
        s[j + 1] = x;
    }
}

int main(int argc, char **argv)
{
    srand(time(NULL));

    clock_t begin, end;
    int insertion_time_taken, qsort_time_taken;
    int *insertion_sort_data = (int *)malloc(NO_DATA * sizeof(int));
    int *qsort_data = (int *)malloc(NO_DATA * sizeof(int));
    for (int i = 0; i < 3; i++)
    {
        for (int i = 0; i < NO_DATA; i++)
        {
            insertion_sort_data[i] = qsort_data[i] = rand();
        }

        begin = clock();
        straight_insert_int(insertion_sort_data, NO_DATA);
        end = clock();
        insertion_time_taken = (end - begin) * 1000.0 / CLOCKS_PER_SEC;

        begin = clock();
        quicksort_int(0, NO_DATA, qsort_data);
        end = clock();
        qsort_time_taken = (end - begin) * 1000.0 / CLOCKS_PER_SEC;

        printf("%d: qsort %1d ms, insertion %1d ms\n", 
               i, qsort_time_taken, insertion_time_taken);

    }
    return (EXIT_SUCCESS);
}

在我的计算机上，快速排序大约需要 17 毫秒，插入排序大约需要 4500 毫秒。