Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[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