Почему этот эталонный код для линейного и двоичного поиска не работает?

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

линейный результат поиска для 29445: 26987 после 701950 до 701950: 0

бинарный результат поиска для 29445: 26987 после 701950 до 701950: 0

Я тоже пытался использовать clock_t, но результат был таким же. Нужен ли мне еще больший размер массива или я неверно тестирую?

В ходе курса я должен сам реализовать большинство вещей. Вот почему я не использую STL. Я не уверен, разрешено ли использование stl :: chrono, но я хотел бы убедиться, что проблема не лежит в другом месте.

Редактировать: Если неясно, я не могу включить время для сортировки и случайной генерации в тесте.

Answer 1

Одной из проблем является то, что вы устанавливаете startTime = getTime () перед упаковкой тестовых массивов со случайными значениями. Если генерирование случайных чисел происходит медленно, это может доминировать в возвращаемых результатах. Основное усилие - сортировка массива, по сравнению с этим время поиска будет крайне низким. Это, вероятно, слишком большой интервал, как вы предлагаете. Для бинарного поиска по 30 тыс. Объектов мы говорим только о 12 или 13 итерациях, поэтому на современном компьютере максимум 20/1000000000 секунд. Это примерно ноль мс.

Увеличение количества записей в массиве мало поможет, но вы можете попробовать увеличить размер массива, пока не достигнете предела памяти. Но теперь ваша проблема заключается в том, что предварительное генерирование и сортировка случайных чисел будут длиться вечно.

Я бы предложил либо: -

A. Проверка на очень большое количество предметов: -

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

B. Измените свой код, чтобы подсчитать, сколько раз вы сравниваете элементы и используете эту информацию вместо времени.

Answer 2

Похоже, вы используете результат поиска (печатая его с cout * вне временной области, это хорошо). И данные + ключ рандомизированы, поэтому поиск не должен быть оптимизирован во время компиляции. (Тестирование с отключенной оптимизацией не имеет смысла, поэтому вам нужны такие приемы.)

---

Вы смотрели на timeElapsed с помощью отладчика? Может быть, это очень маленький float, который печатает как 0 с настройками по умолчанию cout?

Или, может быть, float endTime - float startTime фактически равен 0.0f, потому что округление до ближайшего float сделало их равными . Вычитание двух больших соседних чисел с плавающей запятой приводит к «катастрофической отмене».

Помните, что float имеет только 24 бита значений и , поэтому независимо от частоты, на которую вы делитесь, если значения PerformanceCounter отличаются менее чем на 1 часть в 2 ^ 24, вы получите ноль , (Если эта функция возвращает необработанные значения из x86 rdtsc, то это произойдет, если последняя перезагрузка вашей системы была более чем в 2 ^ 24 раза дольше, чем временной интервал. X86 TSC начинается с нуля при загрузке системы, и (на процессорах за последние ~ 10 лет) учитывается при «эталонной частоте», которая (приблизительно) равна номинальной / «наклейке» частоты вашего ЦП, независимо от частоты турбо или холостого хода. См. Получить количество тактов ЦП? )

---

double может помочь, но гораздо лучше вычесть в целочисленной области перед делением . Кроме того, перезапись этой части займет QueryPerformanceFrequency из заданного интервала!

---

Как подсказывает @Jon, часто лучше тестировать код в цикле повтора в течение одного более длительного временного интервала, чтобы кэши (код) и предсказание переходов могли прогреться.

Но тогда у вас есть проблема, чтобы убедиться, что повторные вызовы не оптимизированы, и рандомизировать ключ поиска внутри цикла. (В противном случае умный компилятор может вывести поиск из цикла).

Может помочь что-то вроде volatile int result = binSearch(...);, потому что присвоение (или инициализация) volatile является видимым побочным эффектом, который нельзя оптимизировать. Таким образом, компилятор должен фактически реализовать каждый результат поиска в регистре.

Для некоторых компиляторов, например те, которые поддерживают встроенный ассемблер GNU C, вы можете использовать встроенный ассемблер, чтобы требовать, чтобы компилятор генерировал значение в регистре без , добавляя любые накладные расходы на его хранение в любом месте. AFAIK это невозможно с встроенным asm MSVC.