Is my algorithm genuinely this fast? Or is my clock incorrectly coded

Question

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>

template<class Type>
Type lnSearch(std::vector<Type>& Data, Type Target) {
    for (typename std::vector<Type>::iterator Iterator = Data.begin(); Iterator != Data.end(); Iterator++) {
        if (*Iterator == Target)    return *Iterator;
        else   continue;
    }
    return Type{};
}

int main(void) {
    std::vector<int> data;
    for (int i = 0; i < 100000000; i++) {
        data.push_back(i);
    }
    std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
    std::cout << lnSearch(data, 99999999);
    std::chrono::high_resolution_clock::time_point stop = std::chrono::high_resolution_clock::now();
    std::chrono::seconds sduration = std::chrono::duration_cast<std::chrono::seconds>(stop - start);
    std::chrono::milliseconds msduration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
    std::cout << "Time taken by function: " << sduration.count() << "." << msduration.count() << "s" << std::endl;
    return 0;
}

Is my algorithm genuinely fast, is my clock coded incorrectly or is my perception of fast wrong?

in Release mode on vs22, it runs through 100,000,000 iterations in a range of 0.133s - 0.344s

`std::chrono::high_resolution_clock` is arguably not good for anything and is allowed to jump back in time. For a timing task like this, you want to use `std::chrono::steady_clock`. — Drew Dormann, Jun 23 '22 at 22:21
[Here's what one of the folks who came up with `high_resolution_clock` has to say about its usefulness.](https://stackoverflow.com/a/37440647/4581301) — user4581301, Jun 23 '22 at 22:22
It would be better to use lower_bound to search as it is genuinely faster. — QuentinUK, Jun 23 '22 at 22:22
@DrewDormann That is not a useful observation here. hrc is not a random CERN-approved quantum clock. It is a system clock allowed to overflow. on a 64-bit value. — Captain Giraffe, Jun 23 '22 at 22:24
It depends if you can make assertions about your data. If you always get a sorted list like you are presenting it, your algorithm is very slow, and should be using something like a binary search. — Natio2, Jun 23 '22 at 22:38

score 1 · Answer 1 · answered Jun 23 '22 at 22:19

1

Since the if statement in your code is very predictable, the processor can optimize this code very well.
An in depth explanation can be found here:
Why is processing a sorted array faster than processing an unsorted array?

answered Jun 23 '22 at 22:19

Daniel

30,896
18
85
139

2

The array being sorted is a misleading statement, the search is simply coded to find the last value in the array. If the first 99999998 values in the vector were randomly shuffled the end results will be exactly the same. Pedantically, the array is sorted only to the effect that the ***linear*** search always results in the comparator returning false, until it is not. ***Linear*** search is the key here. – Sam Varshavchik Jun 23 '22 at 22:28

score 1 · Answer 2 · answered Jun 23 '22 at 22:39

This is what is expected.

Search 100,000,000 or 1e9 elements. Super simple. Your CPU does about 1e10 things every second. (1)

So to find this operation is about 0.1 seconds is unsurprising.

[1] (I'm guessing you are on a modern desktop computer suitable for gaming).

Natio2 · Answer 3 · 2022-06-23T23:24:25.983

Your optimizer would have change the code to either return 99999999 or return vector[99999999]

Either:

Run in debug, there will be a debug over-head but at least it wont change your code
Turn optimizer off around the code you want left alone "#pragma optimize( "[optimization-list]", {on | off} )"
Make a tonne of different vectors for the algorithm to work on so there isn't an obvious optimization

But running in debug where the optimizer hasn't changed this to just returning the value We have something like this, comparing it to a standard search algorithm.

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>

template<class Type>
Type lnSearch(std::vector<Type>& Data, Type Target) {
    for (typename std::vector<Type>::iterator Iterator = Data.begin(); Iterator != Data.end(); Iterator++) {
        if (*Iterator == Target)    return *Iterator;
        else   continue;
    }
    return Type{};
}

class Timer
{
private:
    std::chrono::high_resolution_clock::time_point start;

public:
    Timer()
    {
        start = std::chrono::high_resolution_clock::now();
    }

    ~Timer()
    {
        std::chrono::high_resolution_clock::time_point stop = std::chrono::high_resolution_clock::now();
        std::chrono::seconds sduration = std::chrono::duration_cast<std::chrono::seconds>(stop - start);
        std::chrono::milliseconds msduration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
        std::cout << "Time taken by function: " << sduration.count() << "." << msduration.count() << "s" << std::endl;
    }

};

int main(void) {
    const int size = 100000000;
    const int valueToFind = 99999999;

    std::vector<int> data;
    data.reserve(size);
    for (int i = 0; i < size; i++) {
        data.push_back(i);
    }

    int* result = nullptr;
    std::cout << "YOUR ALGORITHM\n";
    {
        Timer t1;
        lnSearch(data, valueToFind);
    }


    std::cout << "\nBINARY SEARCH\n";
    {
        Timer t2;
        if (std::binary_search(data.begin(), data.end(), valueToFind)){
        }
    }
    
    return 0;
}

Which running on my computer outputs:

YOUR ALGORITHM Time taken by function: 65.65407s

BINARY SEARCH Time taken by function: 0.0s

Definitely recommend reading some search and sort algorithm strategies that lets you do smart things with your data. Binary search only works if it's a sorted list, like the one in your example.

Checking every element like you are is basically the slowest way to search for an item. Your code needs to check 99999999 elements, binary search only checks 23:

Doesn't really answer the question. Asker's not concerned about the program being slow, they're wondering why it is so fast. — user4581301, Jun 23 '22 at 23:14
They are asking if there algorithm is fast, they should be able to read the code and say no. People have already explained the optimizer which will change there entire code to either "return 999999999" or return vector[999999999]. I'm trying to help them not write an algorithm like that — Natio2, Jun 23 '22 at 23:17
So for binary search would you would have to run sorting algorithm? If so which one would you recommend. — IllusiVeXI _ 11, Jun 23 '22 at 23:40
Depends on your data, the example given was already sorted. There's lots of different algorithms based on the data you expect to get. Part of making fast algorithms is being smart about how you store your data that you will need to search through — Natio2, Jun 23 '22 at 23:44
Sorry to answer your question more directly I would do the sorting on the insert (if the data is random), something like the answer to this: https://stackoverflow.com/questions/15843525/how-do-you-insert-the-value-in-a-sorted-vector — Natio2, Jun 23 '22 at 23:56

Is my algorithm genuinely this fast? Or is my clock incorrectly coded

3 Answers3