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

From: Victor A. Wagner Jr. (vawjr_at_[hidden])
Date: 2004-12-20 02:17:08

At Sunday 2004-12-19 21:16, you wrote:
>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... :(
> >
> >
> > On Sun, 19 Dec 2004 20:22:01 -0700, Victor A. Wagner Jr.
> > <vawjr_at_[hidden]> wrote:
> >> At Sunday 2004-12-19 17:54, you wrote:
> >> >This seems like the type of thing boost may have an answer to, yet I
> >> >still havn't found it:
> >> >
> >> >I have two std::lists, about 50,000 items in each.  The items are all
> >> >number ranges so two uints start and end.  I need to remove one list
> >> >from the other - exact matches or subranges only.  Currently I'm using
> >> >remove_if() to remove/shrink/split them but it is taking forever,
> >> >around 30sec.
> >> >
> >> >Anyone know of a better solution?
> >>
> >> are the lists sorted?
>
>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.

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.  I think it's worth pursuing for ranges tho.

>--
>Dave Abrahams
>Boost Consulting
>http://www.boost-consulting.com
>
>_______________________________________________
>Boost-users mailing list
>Boost-users_at_[hidden]
>http://lists.boost.org/mailman/listinfo.cgi/boost-users

Victor A. Wagner Jr.      http://rudbek.com
The five most dangerous words in the English language:
               "There oughta be a law"