Finding gaps in a double vector

[Goedel]

Hi,

I have a large amount of double <vectors> each of them containing up to several 100s of values. Just for your information the values belong to a time series, the values are just measured time distances in seconds.

Now I am looking for a performant way to find gaps within a vector. For each value in the vector there should be a tolerance +/- 10% add to the value itself. After streching my values this way I want to determine areas which are not covered by this strechings.

e.g. for the vector containing the values

2.0 2.1 2.13 2.2 3.5 3.6 3.9 6.4 7.0

the function should output the unoccupied areas 2.42-3.15 and 4.29-5.76.

Is there a library function I could use for an efficient calculation of theses gaps?


Greeting, Matthew

[keskiverto]

So, in essence you would look at each pair of consecutive elements (A and B), and if their difference is large (A*1.1 < B), then store a pair of values (A*1.1, B*0.9).

You could do the iteration with std::transform, but I don't know whether that is more efficient than explicit loop.

[JLBorges]

> Is there a library function I could use for an efficient calculation of theses gaps?

For a sorted sequence, it would be O(N), no matter what you do.

#include <iostream>
#include <utility>
#include <algorithm>

std::vector< std::pair<double,double> > unoccupied( const std::vector<double>& seq )
{
    constexpr double multiplier_after = 1.10 ;
    constexpr double multiplier_before = 0.90 ;

    std::vector< std::pair<double,double> > result ;

    if( seq.size() > 1 && std::is_sorted( std::begin(seq), std::end(seq) ) )
    {
        double prev = seq.front() * multiplier_after ;
        for( auto iter = ++std::begin(seq) ; iter != std::end(seq) ; ++iter )
        {
            double curr = *iter * multiplier_before ;
            if( curr > prev ) result.emplace_back( prev, curr ) ;
            prev = *iter * multiplier_after ;
        }
    }

    return result ;
}

int main()
{
    for( const auto& p : unoccupied( { 2.0, 2.1, 2.13, 2.2, 3.5, 3.6, 3.9, 6.4, 7.0 } ) )
        std::cout << '[' << p.first << '-' << p.second << "] " ;
    std::cout << '\n' ;
}

http://ideone.com/evSeRC

[keskiverto]

"Measured series" could mean that that data is not "sorted" and cannot be reordered (i.e. sorted). Even then it is O(N), but obviously with a larger constant.