[REBOL] Re: [algo] Intervals and parsing
From: didec:tiscali at: 12-Mar-2004 14:07
Re: [algo] Intervals and parsing
See at bottom
> On Thu, 11 Mar 2004, Didec wrote:
>
> > [algo] Intervals and parsing
> > Hi all,
> >
> > For one of my apps, I have to manage a very long list of integer!
> > I need to know if an integer! is in the list, and i need to add it to the list.
> >
> > To avoid an infinite block of integer! that will overflow the memory for nothing,
and considering the fact that most of the values will follow themselve,
> > I use an intervals dialect and some funcs.
> >
> > The values are stored in a block, but consecutives values are replaced by first and
last values separate by a minus sign "-".
> >
> > I.e. : [0 1 2 3 4 5 10 11 12 13 15 19 20 21 22]
> > become [0 - 5 10 - 13 15 19 - 22]
> >
> > I use 2 functions, one to check if a value exists in list, and one to add the value
to the list.
> >
> > I post the funcs here for 2 reasons :
> > 1) Maybe someone would need it
> > 2) Maybe someone can do better or simpler
> >
> > Anyway, comments are welcome
> >
> > DideC
> >
>
> Hi DideC,
>
> as much as I do like parse I am unconvinced it is the ideal solution for
> managing a list of integers.
>
> I changed your interval datastructure to be a list of pairs!,
> each representing an interval, and used binary search instead of parse
> to locate solutions/insertion-points.
> it has not been tested beyond a few runs of your automatic testing and it
> is incomplete as it does not merge adjecent intervals when they meet.
>
> but I would be curious as to how it fairs in comparison to the parse
> version on your large data sets.
>
Thank you very much Tom.
I have not make benchmark to compare, but I like the pair! idea and the dichotomical
search. It will be surely faster as the most search occurs on the high value (end of
the series.
Sure, for performance, the best is to reverse the order of the series or to search from
the end (in my case)
But performance is not the main problem, as this system reduce the series from thousand
of values to about 15 intervals.
But I keep your idea in mind.
FOR PARSE GURUS !
How can I stop the parsing if I find the correct value (and considering the test is done
in the code next to the rule, not by the rule himself) ?
DideC
