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, pharo-users-request@lists.gforge.inria.fr wrote:
Date: Wed, 12 Oct 2011 22:27:26 +0200 From: Lukas Renggli<renggli@gmail.com> Subject: Re: [Pharo-users] red-black and other trees To: A friendly place where any question about pharo is welcome <pharo-users@lists.gforge.inria.fr> Message-ID: <CANoDCG-osEdoF85ikhn2xShe6T=gpu9hKe4r9w-zVGUJxrp5hw@mail.gmail.com> 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<pdebruic@gmail.com> 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.h...
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