red-black and other trees

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

red-black and other trees

Paul DeBruicker
Hi -

I am considering implementing a Centered Interval Tree
(http://en.wikipedia.org/wiki/Interval_tree) because I have to get the
set of Timespans a particular Timespan overlaps from an arbitrary set of
Timespans.


In looking around I can only find the BTree implementation on
SqueakSource, and the Left-Leaning-Red-Black-Tree linked to in the
following list posting:
http://forum.world.st/Interesting-survey-about-smalltalk-tp2261561p2263370.html


Does Pharo either not need/benefit from the various kinds of trees?

Or is it trivial to implement/adapt the BTree to behave as a Red-Black
Tree (or, in my case, the Centered Interval Tree) and as such I just
need to learn how to do that?

Thanks

Paul

Reply | Threaded
Open this post in threaded view
|

Re: red-black and other trees

Lukas Renggli
The BTree package contains a class called DateTree for exactly that
purpose. Works very well with huge collections of date intervals.

Lukas

On 12 October 2011 22:13, Paul DeBruicker <[hidden email]> wrote:

> Hi -
>
> I am considering implementing a Centered Interval Tree
> (http://en.wikipedia.org/wiki/Interval_tree) because I have to get the set
> of Timespans a particular Timespan overlaps from an arbitrary set of
> Timespans.
>
>
> In looking around I can only find the BTree implementation on SqueakSource,
> and the Left-Leaning-Red-Black-Tree linked to in the following list posting:
> http://forum.world.st/Interesting-survey-about-smalltalk-tp2261561p2263370.html
>
>
> Does Pharo either not need/benefit from the various kinds of trees?
>
> Or is it trivial to implement/adapt the BTree to behave as a Red-Black Tree
> (or, in my case, the Centered Interval Tree) and as such I just need to
> learn how to do that?
>
> Thanks
>
> Paul
>
>



--
Lukas Renggli
www.lukas-renggli.ch

Reply | Threaded
Open this post in threaded view
|

Re: red-black and other trees

Paul DeBruicker
In reply to this post by Paul DeBruicker
I created the CenteredIntervalTree repo on Squeaksource.  The
CenteredIntervalTree is about 2x slower  to create than a DateTree but
50-500x faster to query in Pharo 1.3 on Linux. The speed difference
remains relatively constant as the tree size grows.   I only tested up
to 1,000,000 timespans.   It works with instances of class Interval and
Timespan.  Converting the Timespans to Intervals using #asSeconds makes
the creation process faster than the DateTree creation process.

I used the code below to approximate the speed differences.  You need to
have the BTree package loaded from SqueakSource to try the example below.


Paul


|timespanDatabase  dateTree centeredIntervalTree timespansOfInterest
timingResults results size iterations interval tmpResults citResults
dtResults|
size:=10.
iterations:=10.
interval:=1 to: size.
results:=Dictionary new.
timingResults := Dictionary new.
timespanDatabase:= OrderedCollection new.
interval do:[:eachMonth | interval do: [:eachDay| interval
do:[:eachHour| timespanDatabase add:(Timespan starting: (DateAndTime now
+ (eachMonth*30) days + eachDay days + eachHour hours) duration: 2
hours)]]].
timespansOfInterest :=OrderedCollection new.
timespansOfInterest add: (timespanDatabase at: 20).
interval do:[:each | timespansOfInterest add: timespanDatabase atRandom].
results at: 'timespanDatabase-size' put:timespanDatabase size.
"results at: 'timespanDatabase' put: timespanDatabase ."
timingResults at:'dateTree-creation' put:([iterations
timesRepeat:[dateTree:=DateTree new.
                        timespanDatabase do:[:eachTimespan| dateTree at: eachTimespan put:
eachTimespan]]] timeToRun).
timingResults at:'dateTree-query' put:([iterations
timesRepeat:[tmpResults:=Dictionary new.
                timespansOfInterest do: [:each | tmpResults at: each put: (dateTree
during: each)]]] timeToRun).
results at:'dateTree-results' put: tmpResults.

timingResults at:'centeredIntervalTree-creation' put:([iterations
timesRepeat:[centeredIntervalTree :=CenteredIntervalTree from:
timespanDatabase ]] timeToRun).

timingResults at:'centeredIntervalTree-query' put:([iterations
timesRepeat:[tmpResults:=Dictionary new.
                timespansOfInterest do:[:each | tmpResults at: each put:
(centeredIntervalTree intervalsThatInclude: each) asSet]]] timeToRun).
results at:'centeredIntervalTree-results' put: tmpResults.
citResults:=OrderedCollection new.
(results at: 'centeredIntervalTree-results') keysAndValuesDo: [:timespan
:col| citResults addAll:col].
dtResults:=OrderedCollection new.
(results at: 'dateTree-results') keysAndValuesDo: [:timespan :col|
dtResults addAll:col].
dtResults size = citResults size ifFalse:[self halt.].
(dtResults includesAllOf: citResults) ifFalse:[self halt].
(citResults includesAllOf: dtResults) ifFalse:[self halt].
timingResults

On 10/13/2011 03:03 AM, [hidden email] wrote:

> Date: Wed, 12 Oct 2011 22:27:26 +0200
> From: Lukas Renggli<[hidden email]>
> Subject: Re: [Pharo-users] red-black and other trees
> To: A friendly place where any question about pharo is welcome
> <[hidden email]>
> Message-ID:
> <CANoDCG-osEdoF85ikhn2xShe6T=[hidden email]>
> Content-Type: text/plain; charset=ISO-8859-1
>
> The BTree package contains a class called DateTree for exactly that
> purpose. Works very well with huge collections of date intervals.
>
> Lukas
>
> On 12 October 2011 22:13, Paul DeBruicker<[hidden email]>  wrote:
>> >  Hi -
>> >
>> >  I am considering implementing a Centered Interval Tree
>> >  (http://en.wikipedia.org/wiki/Interval_tree) because I have to get the set
>> >  of Timespans a particular Timespan overlaps from an arbitrary set of
>> >  Timespans.
>> >
>> >
>> >  In looking around I can only find the BTree implementation on SqueakSource,
>> >  and the Left-Leaning-Red-Black-Tree linked to in the following list posting:
>> >  http://forum.world.st/Interesting-survey-about-smalltalk-tp2261561p2263370.html
>> >
>> >
>> >  Does Pharo either not need/benefit from the various kinds of trees?
>> >
>> >  Or is it trivial to implement/adapt the BTree to behave as a Red-Black Tree
>> >  (or, in my case, the Centered Interval Tree) and as such I just need to
>> >  learn how to do that?
>> >
>> >  Thanks
>> >
>> >  Paul
>> >
>> >