Skip to content

Instantly share code, notes, and snippets.

@bfraboni
Last active September 30, 2019 16:31
Show Gist options
  • Save bfraboni/5eeb70c1a15b1d27f001faf92e2c53b4 to your computer and use it in GitHub Desktop.
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.
#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