5

I have a set of items strictly ordered on time. Each item can either be single (no Next, no Previous) or part of a span (with either 1 or 2 further endpoints). For example in the picture A is part of a 3 element span 1 -> 4 -> 5, B is part of a 2 element span 2 -> 3 and C is part of a 2 element span 6 -> 16. As you can see, spans can overlap each other (start2 > start1, end1 > end2).

enter image description here

What I want to do is work out a fast algorithm for finding which spans (or individuals) are intersecting a given span Min -> Max.

My naive approach is to simply test every single item in the set, with something like:

for(auto const & e : items)
{
    if(e.Previous)
    {
        // Middle or last item in a set (already been tested).

        continue;
    }

    auto t1 = e.Time, t2 = e.Time;

    if(e.Next)
    {           
        if(e.Next.Next)
        {
            // Part of a 3 item span (start, middle, end).

            t2 = e.Next.Next.Time;
        }
        else
        {
            // Part of a 2 item span (start, end).

            t2 = e.Next.Time;
        }
    }       

    if(t1 > MaxTime || t2 < MinTime)
    {
        // Does not intersect the span.

        continue;
    }       

    ... Do something with the item, such as draw it.
}

This doesn't perform too badly with 250,000 items actually but starts to be pretty slow when you get into millions.

I have plenty of time available at start-up to get a std:future up and running to pre-process these things into some more useful structure if that helps. I also need to be able to append to the end of the set, though keeping strictly ascending time order (i.e. now() >= items.last().time).

Does anything occur to anyone?

10
  • Are your times times or could they be used as index values as in your example? – Simon Kraemer Mar 22 '16 at 14:59
  • If you partition the set into N sections, where N is some time span T (an hour, say), you could use the time as a hash, yes (integer divide by T). Then you can only consider buckets in the hash that intersect T. The trouble is many items won't be in the buckets considered because their start is in a bucket < Min or the end in a bucket > Max (I tried this). I'd need to put the interval into all intermediate buckets between start and end. Then my problem is how to avoid considering an item twice. – Robinson Mar 22 '16 at 15:17
  • Do you check one min-max range or do you have a list of ranges to check? For only one range your algorithm seems OK. – Carra Mar 22 '16 at 15:28
  • 1
    Maybe you are faster if you structure your items in sets. These sets could have a start and endtime and you can check for intersection only using 2 values per set (Should be (Min < Start < Max || Min < End < Max || (Start < Min && Max < End)). Depending on how often you check and how large your sets are this might make a huge difference, – Simon Kraemer Mar 22 '16 at 15:45
  • Just one range Carra. Simon that's not a bad idea actually. Partition the data so that all items are inside a set. It's very unlikely to be continuous over time, i.e. there will always be gaps where there are no spans. A quick pass through could work out some kind of optimal sectioning. – Robinson Mar 22 '16 at 15:47
3

A good data structure for what you want to do is an Interval Tree. You can build one in O(nlogn) and queries take O(logn + k) where k is the number of intervals returned by the query.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.