CODEWITHSUNDEEP
c++algorithmperformanceoptimizationintel-vtune
kiriloff
kiriloff

Reputation: 26333

Find index of nearest in sorted vector

I wrote a C++ routine to find nearest double element in sorted array. Is there a way to speed up?

There are two branches based on the value of boolean reversed, if reversed it is sorted in the decreasing order.

 void findNearestNeighbourIndex_new(real_T value, real_T* x, int_T x_size, int_T& l_idx)
{
    l_idx = -1;

    bool reversed= (x[1] - x[0] < 0);

    if ((!reversed&& value <= x[0]) 
                  || (reversed&& value >= x[0])){ 
        // Value is before first position in x
        l_idx = 0;
    }
    else if ((!reversed&& value >= x[x_size - 1]) 
                    || (reversed&& value <= x[x_size - 1])){ 
        // Value is after last position in x
        l_idx = x_size - 2;
    }
    else // All other cases
    {
        if (reversed)
        {
            for (int i = 0; i < x_size - 1; ++i)
            {
                if (value <= x[i] && value > x[i + 1])
                {
                    l_idx = i;
                    break;
                }
            }
        }
        else{
            for (int i = 0; i < x_size - 1; ++i)  
            {
                if (value >= x[i] && value < x[i + 1])
                {
                    l_idx = i;
                    break;
                }
            }
        }   
    }
}

In this very case where array is sorted, I do not see a way to do better. So, with profiling i see that the comparison in if (value <= x[i] && value > x[i + 1]) is expensive.

EDIT

tried with lower_bound()

std::vector<real_T> x_vec(x, x + x_size);

l_idx = std::upper_bound(x_vec.begin(), x_vec.end(), value) - x_vec.begin() - 1;

Upvotes: 1

Views: 9270

Answers (4)

mathengineer
mathengineer

Reputation: 160

The way is to substract 1 to size (to make work over higest value) and 0.5 to target value to make it accurate:

#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
    float x[10] = { 2,3,4,5,6,7,8,9,10,11 },y;
    int size = sizeof(x) / sizeof(x[0]),pos;


    y = 4.1; pos = std::upper_bound(x, x + size - 1, y - 0.5) - x;
    std::cout << "position: " << pos << " target value=" << y << " upper_bound=" << x[pos] << endl;
    y = 4.9; pos = std::upper_bound(x, x + size - 1, y - 0.5) - x;
    std::cout << "position: " << pos << " target value=" << y << " upper_bound=" << x[pos] << endl;
    y = -0.5; pos = std::upper_bound(x, x + size - 1, y - 0.5) - x;
    std::cout << "position: " << pos << " target value=" << y << " upper_bound=" << x[pos] << endl;
    y = 100; pos = std::upper_bound(x, x + size - 1, y - 0.5) - x;
    std::cout << "position: " << pos << " target value=" << y << " upper_bound=" << x[pos] << endl;
    getchar();
    return 0;
}

Upvotes: 0

NathanOliver
NathanOliver

Reputation: 180945

If you don't actually have an vector to use with upper_bound() you don't need to construct one as that is going to be an O(n) operation. upper_bound() will work with the array that you have. You can use:

l_idx = std::upper_bound(x, x + size, value) - x - 1;

Test case:

#include <iostream>
#include <functional>
#include <algorithm>

int main()
{
    const int size = 9;
    int x[9] = {1,2,3,4,5,6,7,8,9};

    auto pos = std::upper_bound(x, x + size, 5) - x;

    std::cout << "position: " << pos;

    return 0;
}

Output:

5

As the result of upper_bound() points us to 6(live example).

Upvotes: 3

kiriloff
kiriloff

Reputation: 26333

Implemented this helper routine

void findNearestNeighbourIndex_bin_search_new(real_T value, real_T* x,  
              int_T start, int_T stop, int_T& l_idx)
{
    int_T mid = ( stop - start ) / 2;

    if (value >= x[mid+1])
    {
        findNearestNeighbourIndex_bin_search_new(value, x, mid + 1, stop, l_idx);
    }
    else if (value < x[mid])
    {
        findNearestNeighbourIndex_bin_search_new(value, x, start, mid, l_idx);
    }
    else
    {
        l_idx = mid;
        return;
    }
}

Upvotes: -1

Galimov Albert
Galimov Albert

Reputation: 7357

You can use std::lower_bound to find a element equal or greater than requested, and then move iterator backwards and check preceding value too. This will use binary search and will cost O(log n), also this enables standard STL comparators and so on.

Upvotes: 12

Related Questions