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: moliad::gmail::com at: 21-Sep-2007 10:45

hi Sunanda, here is my lean and mean attempt... it is severely tested... tried all boundaries I could think of (even returning a slice from within one object), and obeys all the fine print AFAIK. Warning: this is Carl S. type compact code. This may cause your brain to reboot ;-). it has the merit of being the submission with the smallest footprint so far ;-) but also probably is the least obvious to analyse. I have done no benchmarking so some little things might be optimised still ... but will be faster/slower based on the metrics of source data and slice you are extracting. in the current ordering, AFAICT its optmised for smaller subsets of large data sets. (but I still thinks its damn fast in any case!) ;-------------------- ;- get-subset() ;-------------------- get-subset: func [ data s e /local i t ][ my-data: copy/deep data t: 0 remove-each ctx my-data [ i: t any [ (i >= e) all [(t: i + length? ctx/items) < s ] empty? ctx/items ( all [t > e clear at ctx/items (e - i + 1)] all [i < s remove/part ctx/items (s - i - 1)] false ) ] ] my-data ] ----------- NOTES: ----------- we supply the data set, meaning we can extract a subset of a subset pretty easily. I use a native copy/deep ONCE at the head of the function, so this should be pretty fast, when compared to copying single objects over and over in a loop. note that this also makes sure the original and subset are completely independent. so cutting up / mangling the items in subset will not break the original data the remove-each function is usually one of the fastest loops in rebol, and I tried to optimise the ordering of the nesting of any/all for maximum performance. the last two ALL can only occur once, so they are only verified at the end of loop... meaning, they will only be compared whenever we are within the subset. I also used an intermediate index 'T, to limit the number of arithmetics involved. note that once we are beyond the end of the subset, the loop is EXTREMELY fast, as it only does one boolean operation before qualifying the 'ANY and deleting the object from the list. have fun, I know I did :-) -MAx