Last active
September 30, 2019 16:31
-
-
Save bfraboni/5eeb70c1a15b1d27f001faf92e2c53b4 to your computer and use it in GitHub Desktop.
Comparison between exhaustive search, binary search, and linear fit / interpolation search for sorted arrays.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <chrono> | |
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
#include <functional> | |
#include <random> | |
#include <cassert> | |
// Comparison between exhaustive search, binary search, and linear fit / interpolation search for sorted arrays. | |
typedef std::vector<float>::iterator iterator; | |
int exhaustive(const std::vector<float>& vec, const float value) | |
{ | |
int vsize = vec.size(); | |
for(int i = 0; i < vsize; ++i) | |
if(vec[i] > value) | |
return i; | |
return -1; | |
} | |
iterator exhaustive(iterator first, iterator last, const float value) | |
{ | |
for(; first != last; ++first) | |
if(*first > value) | |
return first; | |
return last; | |
} | |
int binary(const std::vector<float>& vec, const float value) | |
{ | |
int p = 0, q = vec.size(); | |
int m; | |
while(p < q) | |
{ | |
m = (p + q) / 2; | |
if(vec[m] < value) | |
p = m + 1; | |
else | |
q = m; | |
} | |
return p; | |
} | |
iterator binary(iterator first, iterator last, const float value) | |
{ | |
iterator mid; | |
while(first < last) | |
{ | |
mid = first + (last - first) / 2; | |
if(*mid < value) | |
first = mid + 1; | |
else | |
last = mid; | |
} | |
return first; | |
} | |
// cf : https://blog.demofox.org/2019/03/22/linear-fit-search/ | |
int linear_fit_search(const std::vector<float>& vec, const float value) | |
{ | |
int p = 0, q = vec.size() - 1, g; | |
float vmin = vec.front(), vmax = vec.back(); | |
while( p < q ) | |
{ | |
g = p + int((value - vmin) * (q - p) / (vmax - vmin)); | |
if( vec[g] < value ) | |
{ | |
vmin = vec[g]; | |
p = g+1; | |
} | |
else | |
{ | |
vmax = vec[g]; | |
q = g; | |
} | |
} | |
return p; | |
} | |
// cf : https://blog.demofox.org/2019/03/22/linear-fit-search/ | |
iterator linear_fit_search(iterator first, iterator last, const float value) | |
{ | |
iterator mid; | |
--last; | |
float vmin = *first, vmax = *last; | |
while( first < last ) | |
{ | |
mid = first + (value - vmin) * (last - first) / (vmax - vmin); | |
if( *mid < value ) | |
{ | |
first = mid + 1; | |
vmin = *mid; | |
} | |
else | |
{ | |
last = mid; | |
vmax = *mid; | |
} | |
} | |
return first; | |
} | |
static std::vector<float> generate_data(size_t size) | |
{ | |
using value_type = float; | |
static std::uniform_real_distribution<value_type> distribution(0.f, 1.f); | |
static std::random_device rnd; | |
static std::mt19937 engine(rnd()); | |
std::vector<value_type> data(size); | |
std::generate(data.begin(), data.end(), []() { return distribution(engine); }); | |
return data; | |
} | |
struct Timer | |
{ | |
typedef std::chrono::high_resolution_clock clock; | |
typedef std::chrono::duration<int, std::nano> nanoseconds; | |
typedef std::chrono::duration<int, std::micro> microseconds; | |
typedef std::chrono::duration<int, std::milli> milliseconds; | |
typedef std::chrono::duration<int, std::ratio<1>> seconds; | |
typedef std::chrono::duration<int, std::ratio<60>> minutes; | |
explicit Timer(bool run = true) {if (run) reset();} | |
void reset() {start = clock::now();} | |
nanoseconds nano() const {return std::chrono::duration_cast<nanoseconds>(clock::now() - start);} | |
microseconds micro() const {return std::chrono::duration_cast<microseconds>(clock::now() - start);} | |
seconds sec() const {return std::chrono::duration_cast<seconds>(clock::now() - start);} | |
template <typename T, typename Traits> | |
friend std::basic_ostream<T, Traits>& operator<<(std::basic_ostream<T, Traits>& out, const Timer& timer) | |
{ | |
return out << timer.nano().count() << " ns"; | |
} | |
clock::time_point start; | |
}; | |
int main( int argc, char * argv[] ) | |
{ | |
std::vector<float> data = generate_data(1000000); | |
std::sort(data.begin(), data.end()); | |
float value = 0.724356548f; | |
// float value = 0.000024356548f; | |
Timer timer; | |
int a = exhaustive(data, value); | |
// std::cout << "exhaustive index " << timer << std::endl; | |
timer.reset(); | |
a = exhaustive(data, value); | |
std::cout << "exhaustive index " << timer << std::endl; | |
timer.reset(); | |
auto ita = exhaustive(data.begin(), data.end(), value); | |
std::cout << "exhaustive iterator " << timer << std::endl; | |
timer.reset(); | |
int b = binary(data, value); | |
std::cout << "binary index " << timer << std::endl; | |
assert( value >= data[b-1] && value <= data[b] ); | |
timer.reset(); | |
auto itb = binary(data.begin(), data.end(), value); | |
std::cout << "binary iterator " << timer << std::endl; | |
assert( value >= *(itb-1) && value <= *itb ); | |
timer.reset(); | |
int c = linear_fit_search(data, value); | |
std::cout << "linear fit index " << timer << std::endl; | |
timer.reset(); | |
iterator itc = linear_fit_search(data.begin(), data.end(), value); | |
std::cout << "linear fit iterator " << timer << std::endl; | |
assert( a == b ); | |
assert( a == c ); | |
assert( a == (int)(std::distance(data.begin(), ita))); | |
assert( a == (int)(std::distance(data.begin(), itb))); | |
assert( a == (int)std::distance(data.begin(), itc) ); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment