[REBOL] Re: [algorithm] Algorithm challenge: selecting a range from multiple blocks
From: dhsunanda::gmail::com at: 26-Sep-2007 8:34
[re-sent as it seems to have been lost during a mailing list outage]
I've had a chance to run some tests and timings on the solutiond
put forward to this challenge.
Tom and Steve contributed code that was broadly similar to my
approach -- take a linear scan through the block selecting the
items you want. Max did it the other away around -- delete the
ones you do not want.
Tom and Max took advantage of being permitted to overwrite the
input structures. Steve and I both went for side-effective-free
code that did not.
Gregg's code sadly tripped over a couple of boundary conditions
(as he'd hinted it might); I've excluded it from the timing tests
-- but, who knows? it may be just a point release away from being
an outright winner :-)
****
The timings on live size datasets seem to show that deletion is
faster than selection; and that working on the original is faster
than creating a new copy.
The test data consisted of a block with six objects. Each object
has 10'000 items.
Each test was run 25 times to get the total time. Times do not
The results are:
Select all but last item -- range: [1 59998]
sunanda..... 0:00:00.182
tom..... 0:00:00.078
steve..... 0:00:00.156
max..... 0:00:00.016
Select last item only -- range: [59999 59999]
sunanda..... 0:00:00.113
tom..... 0:00:00.031
steve..... 0:00:00.047
max..... 0:00:00.009
Select some items from the middle across 3 objects -- range:
[21000 31000]
sunanda..... 0:00:00.119
tom..... 0:00:00.11
steve..... 0:00:00.109
max..... 0:00:00.014
Your results may vary, depending on the size of your datasets and
the number of items you need for each subset.
Thanks to everyone who entered!
Sunanda