[Boost-users] Re: Efficient removal of std::list items

From: David Abrahams (dave_at_[hidden])
Date: 2004-12-20 15:30:41

Victor A. Wagner Jr. wrote:
> At Monday 2004-12-20 05:42, you wrote:
>>Victor A. Wagner Jr. wrote:
>> >> >> are the lists sorted?
>> >> >
>> >>Cory Nelson wrote:
>> >> > Yep.  If you're going where I think you're going (binary search), I
>> >> > was about halfway through the modifications when I opened the email.
>> >> > Lack of sleep will get to you... :(
>> >>
>>
>>Dave Abrahams wrote:
>> >>That'll only work if the ranges are non-overlapping.  Otherwise you'll
>> >>need to use an interval tree to avoid an O(N) search for each interval
>> >>you want to remove.
>> >
>>Victor A. Wagner Jr. Replied:
>> > you're likely correct, but we were looking at handling some stuff with
>> > imprecise (error probabilities) results and we were on the track of doing
>> > some stuff along these lines.  The project was cancelled (shame, I 
>> think it
>> > would fit well with the physical quantities systems... you just can't
>> > measure things as closely as you'd like) so we never got to see how/if all
>> > of the algorithms would work or whether we'd have to specialize them for
>> > "fuzzy" numbers.
>>
>>Have you seen the Boost Interval library?

By the way, have you?

>> > I think it's worth pursuing for ranges tho.
>>
>>Why should the OP pursue anything that's likely (your words) to be
>>O(N^2) when there's a known and proven O(N log N) approach?
> 
> you know dave, sometimes I think you just like to dis me.  

I don't.  I am trying to protect someone who's asking for help from
going down an unproductive path.  I've been through this problem before.
 I know that sorted linear ranges don't work; there's just not enough
information and structure there to make the job efficient.

It was an honest question, you know.  If you're going to suggest that
someone pursue that path I think you ought to be able to explain why.

> You sure as hell 
> don't pay attention to anything I actually write.

I do.  It appears from what you write below that if anything I paid too
much attention to what you actually wrote and failed to perceive what
you actually meant. Please; you are at least just as susceptible to
communication error as I am.  There's no need to make me out to be a
villain here.

> I never suggested anyone pursue ANY O(N^2) approach.
> I was SUGGESTING that maybe there is an O(N+M) approach 

I don't know how anyone (including the OP) was supposed to understand
that, considering there has been no mention of O(N+M) so far in this thread.

> although allowing that perhaps YOU are correct and there isn't.

Here's the other part of the communication  error.  First of all, you
said that I was "likely" to be correct, which is much stronger than
"perhaps."  And what I was claiming wasn't that there's no O(N+M)
approach, but that binary search will not work (i.e. be efficient)
unless the ranges are non-overlapping.  Let me just point out that I
*did* actually write that.  Were you paying attention?

> btw, "these lines" referred to my previous message about 
> modifying   set_difference() not your silly O(n) search for every interval 
> you want to remove.

In the general case (unless the ranges are non-overlapping), using
set_difference will also be a silly O(n) search for every interval that
needs to be removed, because although you can avoid O(n) for each
starting value, you still potentially need to look through all the rest
of the elements until you find one that starts later than the current
range's end value, which could be anything.

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com