c语言中搜索算法的执行时间(准确性)

Question

我试图比较这3种搜索算法，起初我使用time.h库，但什么都没发生，输出总是0.00000秒。现在我试图在循环中使用一些计数器。但我也有问题，有人能帮我写代码吗？

这是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include<time.h>
void binarySearch(int a[],int,int,int*);
int interpolationSearch(int [],int,int,int*);
int linearSearch(int a[],int,int,int*);
int main()
{
    int size=10;
    int a[size],i,search,pos,pos2;
    double extime1,extime2,extime3;
    int t=0,b=0,c=0;
    int *counter1,*counter2,*counter3;
    counter1=&t;
    counter2=&b;
    counter3=&c;
    for(i=0;i<size;i++)
    {
        a[i]=i;
    }
    printf("ENTER A NUMBER TO FINDn");
    scanf("%d",&search);
    //BINARY SEARCH
    clock_t start1,end1;
    start1=clock();
    binarySearch(a,size,search,counter1);
    end1=clock();
    extime1=(double)(end1-start1)*100000/CLOCKS_PER_SEC;
    printf("EXECUTION TIME FOR THE BINARY SEARCH IS %f SECONDS:nn",extime1);
    //LINEAR SEARCH
    clock_t start2,end2;
    start2=clock();
    pos=linearSearch(a,size,search,counter2);
    if(pos==-1)
    {
        printf("%d IS NOT PRESENT IN ARRAY.n",search);
    }
    else
    {
        printf("%d IS PRESENT AT LOCATION %d.n",search,pos+1);
    }
    end2=clock();
    extime2=(double)(end2-start2)*100000/CLOCKS_PER_SEC;
    printf("EXECUTION TIME FOR THE LINEAR SEARCH IS %f SECONDS:nn",extime2);
    //INTERPOLATION SEARCH
    clock_t start3,end3;
    start3=clock();
    pos2=interpolationSearch(a,size,search,counter3);
    if(pos2==-1)
    {
        printf("ELEMENT %d NOT FOUNDn",search);
    }
    else
    {
        printf("ELEMENT %d FOUND AT POSITION %dn",search,pos2+1);
    }
    end3=clock();
    extime3=(double)(end3-start3)*100000/CLOCKS_PER_SEC;
    printf("EXECUTION TIME FOR THE INTERPOLATION SEARCH IS %f SECONDS:nn",extime3);
    //COUNTERS
    printf("%dn",t);
    printf("%dn",b);
    printf("%dn",c);
    return 0;
}
void binarySearch(int a[],int size,int search,int *counter1)
{
    int first=0;
    int last=size-1;
    int middle=(first+last)/2;
    while(first<=last)
    {
        *counter1++;
        if(a[middle]<search)
        {
            first=middle+1;
        }
        else if(a[middle]==search)
        {
            printf("%d FOUND AT LOCATION %d.n",search,middle+1);
            break;
        }
        else
        {
            last=middle-1;
        }
        middle=(first+last)/2;
    }
    if(first>last)
    {
        printf("NOT FOUND.%d IS NOT PRESENTED INT THE LIST.n",search);
    }
}
int linearSearch(int a[],int size,int search,int *counter2)
{
    int i;
    for(i=0;i<size;i++)
    {
        *counter2++;
        if(a[i]==search)
        {
            return i;
        }
    }
    return -1;
}
int interpolationSearch(int a[],int n,int k,int *counter3)
{
    int low=0,up=n-1,pos;
    while(low<=up)
    {
        *counter3++;
        if((k<a[low])||(k>a[up]))
        {
            return -1;
        }
        pos=low + (int) ((double) (up - low))*(((double) (k - a[low])) / ((double) (a[up] - a[low])));
        if(a[pos]==k)
        {
            return pos;
        }
        else if(a[pos]>k)
        {
            up=pos-1;
        }
        else
        {
            low=pos+1;
        }
    }
    return (-1);
}

Answer 1

您可以执行以下操作：

#define MAX_ITER_COUNT 1000000
...
clock_t start1,end1;
start1=clock();
for(iteration = 0; iteration < MAX_ITER_COUNT; ++iteration) {
  binarySearch(a,size,search,counter1);
}
end1=clock();
extime1=(double)(end1-start1)*100000/CLOCKS_PER_SEC/MAX_ITER_COUNT;
printf("EXECUTION TIME FOR THE BINARY SEARCH IS %f SECONDS:nn",extime1);

这将重复搜索一百万次，以使时间可测量。尽管使用这种方法，您最终也会增加调用开销。为了避免这种情况，您可能需要将循环放在要评测的函数中。

检查此链接以获取使用gettimeofday和timersub 的计时器实现和性能测量

Answer 2

clock()是cpu时间，如果您想要在符合POSIX的操作系统上需要clock_gettime()的执行时间，并且还有其他操作系统的解决方案，请阅读此链接。

Answer 3

根据cplusplus.com的参考，我建议定义一个小的基准方法，如下所示：

<template class Func>
public inline static double measureExecutionTime(const Func& method) {
    clock_t time = -clock(); //start
    method(); //execute method
    time += clock(); //end
    return time / (double)CLOCKS_PER_SEC; //return execution time, in seconds
}

---

很抱歉发布c++代码，我希望你能把那篇文章翻译成c代码。我的大学课程决定不再教授c和c++之间的区别：/