c++ - 为什么这个线性和二进制搜索的基准代码不起作用？

Question

我正在尝试将线性搜索和二分搜索作为作业的一部分进行基准测试。我已经编写了必要的搜索和随机函数。但是当我尝试对它们进行基准测试时，即使对于更大的数组大小，我也会得到 0 延迟。

代码:

#include<iostream>
#include <time.h>
#include <windows.h>
using namespace std;

double getTime()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}


int linearSearch(int arr[], int len,int target){
    int resultIndex = -1;
    for(int i = 0;i<len;i++){
        if(arr[i] == target){
           resultIndex = i;
           break;
        }
    }

    return resultIndex;
}

void badSort(int arr[],int len){
    for(int i = 0 ; i< len;i++){
        int indexToSwapWith = i;
        for(int j = i+1;j < len;j++){
            if(arr[j] < arr[indexToSwapWith] )
                indexToSwapWith = j;
        }
        if(indexToSwapWith != i){
            int t = arr[i];
            arr[i] = arr[indexToSwapWith];
            arr[indexToSwapWith] = t;
        }
    }
}

int binSearch(int arr[], int len,int target){
    int resultIndex = -1;

    int first = 0;
    int last = len;
    int mid = first;

    while(first <= last){
        mid = (first + last)/2;
        if(target < arr[mid])
            last = mid-1;
        else if(target > arr[mid])
            first = mid+1;
        else
            break;
    }

    if(arr[mid] == target)
        resultIndex = mid;

    return resultIndex;
}

void fillArrRandomly(int arr[],int len){
    srand(time(NULL));
    for(int i = 0 ; i < len ;i++){
        arr[i] = rand();
    }
}

void benchmarkRandomly(int len){

    float startTime = getTime();

    int arr[len];
    fillArrRandomly(arr,len);
    badSort(arr,len);

    /*
    for(auto i : arr)
        cout<<i<<"\n";
    */

    float endTime = getTime();
    float timeElapsed = endTime - startTime;
    cout<< "prep took " << timeElapsed<<endl;

    int target = rand();

    startTime = getTime();
    int result = linearSearch(arr,len,target);

    endTime = getTime();
    timeElapsed = endTime - startTime;
    cout<<"linear search result for "<<target<<":"<<result<<" after "<<startTime<<" to "<<endTime <<":"<<timeElapsed<<"\n";

    startTime = getTime();
    result = binSearch(arr,len,target);
    endTime =  getTime();
    timeElapsed = endTime - startTime;
    cout<<"binary search result for "<<target<<":"<<result<<" after "<<startTime<<" to "<<endTime <<":"<<timeElapsed<<"\n";
}

int main(){
    benchmarkRandomly(30000);
}

示例输出:

准备用了 0.9375

701950到701950:0之后29445:26987的线性搜索结果

从701950到701950:0之后的29445:26987的二分查找结果

我也尝试过使用 clock_t，但结果是一样的。我需要更大的数组大小还是我的基准测试方式有误？

在类(class)中，我必须自己实现大部分内容。这就是我不使用 STL 的原因。我不确定是否允许使用 STL::chrono，但我想首先确保问题不在其他地方。

编辑:如果不清楚，我不能在基准测试中包括排序和随机生成的时间。

Answer 1

一个问题是您在用随机值打包测试数组之前设置了 startTime = getTime()。如果随机数生成速度很慢，这可能会主导返回的结果。主要工作是对数组进行排序，与此相比，搜索时间将非常短。 正如您所建议的那样，这可能太过间隔了。对于 30k 对象的二进制搜索，我们只讨论 12 或 13 次迭代，因此在现代机器上最多 20/1000000000 秒。这大约是零毫秒。

增加数组条目的数量不会有太大帮助，但您可以尝试增加数组大小，直到接近内存限制。但现在你的问题是准备随机数生成和排序将永远花费。

我会建议:-

一个。检查大量项目:-

unsigned int total;
startTime = getTime();
for (i=0; i<10000000; i++)
    total += binSearch(arr, len, rand());
endTime = getTime();

B.修改您的代码以计算您比较元素的次数并使用该信息而不是计时。