[REBOL] Re: cyclic values
From: joel:neely:fedex at: 29-Sep-2002 7:52
Hi, Pat,
Ingeneous!!!
(...of course, with me, there's always a "but"... ;-)
pat665 wrote:
> I want to get values in order from a block, the first value
> coming again after the last, and this forever. Is there a
> better way than the one I am using now ?
>
> colors: [red green blue]
>
> ; I want color to be red, then green, then blue, then red
> ; again forever
> ; the first value is duplicated
>
> color: first colors
> append colors color
>
> ; then forever
> color: select colors color
>
That's a nice compact way to accomplish your stated result,
but under two constraints:
1) the number of values in the block is very small, and
2) the values are all distinct.
SMALL NUMBER OF VALUES
----------------------
Given REBOL 1-origin indexing, the fastest/simplest way I've
found for cycling an integer counter through the range of
values 1..N is
cnt: 0 ;; initialization
cnt: cnt // N + 1
which means we could get your "forever" case above by using
color: pick colors cnt: cnt // + 1
The alternative to using the modulus operator is explicit
logic, as in
color: pick colors counter:
either counter < length? colors [counter + 1] [1]
but that is very sub-optimal...
In any case, the time complexity of modifying the integer
index is O(1) -- constant -- while the time complexity of
SELECT on an ordinary block is O(N) -- linear on the size
of the block. A little quick benchmarking shows that this
adds up very quickly. On my old slow benchmarking box
(200 MHz Pentium, w95) the timings are (in microseconds)
SELECT modulus EITHER...
3 elements 13.94 14.28 18.73
10 elements 16.76 14.72 19.33
(As you can see from the second column, there's still some
statistical variability...)
The above times were taken using function evaluations, so
after removing that overhead, we get the following ratios:
SELECT EITHER...
vs vs
modulus modulus
3 elements 0.97 1.41
10 elements 1.18 1.41
With only three elements, the SELECT approach saves 3% over
the modulus approach, but the EITHER strategy costs 41% extra.
But with ten elements, SELECT is now 18% slower than modulus,
while EITHER is still 41% slower.
CONCLUSION: The SELECT strategy doesn't scale well.
DISTINCT VALUES
---------------
Suppose you wanted to simulate a monitor which was cycling between
the primary colors (e.g. using your original COLORS data), but went
off in between each color (e.g. interspersed black displays). If
we change our block to contain:
colors: [red black green black blue black]
color: first colors
and then try
color: select colors color
We'll find that we're stuck in a green/black cycle, since the first
occurrence of black is always the one that's found by SELECT.
CONCLUSION: The SELECT strategy doesn't handle cases with values
that occur more than once in the block.
HOWEVER... With all of the above said, for small blocks with
distinct values, your approach is quite elegant. Thanks for
posting it!
-jn-
--
; Joel Neely joeldotneelyatfedexdotcom
REBOL [] do [ do func [s] [ foreach [a b] s [prin b] ] sort/skip
do function [s] [t] [ t: "" foreach [a b] s [repend t [b a]] t ] {
| e s m!zauafBpcvekexEohthjJakwLrngohOqrlryRnsctdtiub} 2 ]