[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
