Algorithm Ideas?

[Armitage]

So I have a vector of objects. Each object has a range represented by a high & low value associated with it. For every object in the list, I need to find every other object which has an overlapping range.

I have an algorithm that works, but I suspect it could be faster.

Currently, I form a vector of pointers to the original list and sort it by the low value for the objects. I then walk through this list, and for each object, I do a binary search of the list from the current point forward for the objects high value. This diagram may help. This only captures the overlappers that have a higher low value then the current object, but that's OK. As long as each overlapping pair is captured somewhere, we're good, and these missing overlaps are captured in the other objects.

Any ideas? I was thinking of making a list with both the low & high values of each object, and sorting that. If you could look at each object and can know where it's high & low values resided in the list, you wouldn't have to do all those searches. You could just grab everything in the list between those positions, eliminate the duplicates, and go. But I can't seem to come up with a data structure that will accomplish that? How can I sort a list of objects such that each object knows its position in the final sorted list? I was thinking maybe some kind of tree representation instead of a flat vector, but haven't quite wrapped my mind around that yet.

I know I'm using list & vector interchangebly - I'm not worried about what kind of container I actually use. I currently use STL vectors. I need to do this in C++.
Any ideas?

 

[Zugzwang152]

How can I sort a list of objects such that each object knows its position in the final sorted list?

I may be missing something here, but if your objects are being sorted into an array/list/vector/whatever, won't they know their position in the sorted list just by the index they occupy in the final list?

 

[Armitage]

Originally posted by: Zugzwang152

How can I sort a list of objects such that each object knows its position in the final sorted list?

I may be missing something here, but if your objects are being sorted into an array/list/vector/whatever, won't they know their position in the sorted list just by the index they occupy in the final list?

If I know the index in the final list, I know the object. But not vice-versa. Remember the "final list" is an array of pointers to the original list I'm looking for a way to look at the original object, and know its position in the sorted list of pointers.

Each object will exist in the pointer list twice - once for its low value, and once for its high value. So, what I'd like to do is iterate on the original object list, and retrieve the indexes in the sorted object list ("final list") for it's high & low values.

 

[Extrarius]

You could add 'operator <' to your object (if it doesn't have one) and use a map<object, int> to store the object->index mapping to be able to get the index of an object. If you have two indexes per object, you could either maintain two maps as you sort or make it a map<object, pair<int, int> >

 

[Zugzwang152]

Originally posted by: Armitage

Originally posted by: Zugzwang152

How can I sort a list of objects such that each object knows its position in the final sorted list?

I may be missing something here, but if your objects are being sorted into an array/list/vector/whatever, won't they know their position in the sorted list just by the index they occupy in the final list?

If I know the index in the final list, I know the object. But not vice-versa. Remember the "final list" is an array of pointers to the original list I'm looking for a way to look at the original object, and know its position in the sorted list of pointers.

Each object will exist in the pointer list twice - once for its low value, and once for its high value. So, what I'd like to do is iterate on the original object list, and retrieve the indexes in the sorted object list ("final list") for it's high & low values.

that sounds complicated as hell, but my guess would be you'd need an attribute in the object to hold either the indexes themselves (passed to the object while the pointer array is being populated) or at least a pointer to the array of pointers (in which case you'd have to iterate through the whole damn array everytime you wanted to find the position of those two values).

how to implement that is beyond my CS-flunked-out MIS ass.

 

[Armitage]

Just took a closer look at it - the idea appears to be DOA. The cost of simply sorting a list that's twice as long eats up and passes any potential gains.

My current method: O(nlog(n) + sum(log(n-i)) where i=1->n-1)
Other idea: > O(2nlog(2n))

For n in the neighborhood that I'm interested in, the 2nd method is already 14% greater.

edit - More simply, my existing method is better then O(2nlog(n)) while the newer idea is worse then O(2nlog(2n))

Ideas encountered on airplanes and in a state of sleep deprivation may not survive closer examination when well rested and on the ground I knocked out my other "inspiration" from that flight yesterday.

Any other ideas about fast algorithms to find these overlaps?

 

[znaps]

Sounds like you'd need an array of Sets. Each set will contain one or more objects in your original Vector. Creating it wouldn't be too difficult but I have no idea on the performance.