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

[REBOL] creation of a block with a lot of integers Re:

From: joel:neely:fedex at: 6-Oct-2000 0:01

Hi, peoyli, [peoyli--algonet--se] wrote:
> Hi, > > Is there a efficient way of creating a block consisting of a range > of integers.. > > using a for-loop is ok for a small amount of values, but when > reaching 1000 values, it takes about 2 seconds on a 060 equipped > Amiga, 2000 values takes about 8 seconds, and so on... > > also.. is this supposed to function like this (local variable is > not cleared between function calls) ? > > REBOL [] > > maybe-bug: func [ > min [integer!] > max [integer!] > /local testblock temp > ][ > testblock: [] > for temp min max 1 [ insert testblock temp ] > testblock > ] > > >> do %../REBOL/bug.r > Script: "Untitled" (none) > >> maybe-bug 1 5 > == [5 4 3 2 1] > >> maybe-bug 1 5 > == [5 4 3 2 1 5 4 3 2 1] > >> maybe-bug 1 5 > == [5 4 3 2 1 5 4 3 2 1 5 4 3 2 1] > >> >
In an earlier post today (wow! it's still today!) I offered the results of a small benchmark that are relevant. (If you signed up since about noon you can ask for a copy of X-SELMA: 425973.) Short version: 1) Any of loop , while , or repeat are significantly faster than for ; the first three are primitives and the last is a mezzanine function. However, that's linear on the size of the block you're trying to create. 2) When building a block of more than trivial length, you can save LARGE time by pre-allocating. (Not doing so was the mistake I had made in an earlier post and was correcting in 425973.) If you allocate an empty block, as in testblock: copy [] then appending consecutive elements to the block will require lots of under-the-hood busy-work (allocate a new chunk of space slightly larger than the old block, copy the old block to the beginning of that space, then stick the new value on the end) which gets progressively more time-consuming as the block grows. (It's proportional to the SQUARE of the final block size!)
> A work-around, appending a 'clear testblock' after the testblock: [] > will fix this, but shouldn't testblock: [] do it in the first place ? >
Andrew's already addressed the fact that testblock: [] inside a function is likely NOT to do what you want. Now... following up on Andrew's suggestion, there are LOTS of ways to skin this cat. We can begin by defining (with thanks to Andrew for the reminder that "insert tail" is faster than "append"): iota: function [n [integer!]] [r i] [ r: make block! n repeat i n [insert tail r i] r ] ...which lets us say...
>> iota 20
== [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20] Next, we can use this generic function: map: function [[catch] b [block!] f [any-function!]] [r v] [ r: make block! length? b foreach c b [ if found? v: do [f c] [insert/only tail r v] ] r ] ...to discard the ones we don't want...
>> map iota 20 func [n] [if n >= 15 [n]]
== [15 16 17 18 19 20] Of course, using map is a bit of overkill, so we could create a more specialized (and therefore faster) function: filter: function [ [catch] b [block!] f [any-function!] ][ r v ][ r: make block! length? b foreach c b [ if do [f c] [insert/only tail r c] ] r ] ...which just does a true/false keep/discard construction:
>> filter iota 20 func [x] [x >= 15]
== [15 16 17 18 19 20] ...and wrap all of this into a nice package: range: func [lb [integer!] ub [integer!]] [ filter iota ub func [n] [n >= lb] ] ...which does this:
>> range 15 20
== [15 16 17 18 19 20] Of course the drawback(s) of all of the above are: 1) We may be generating values on the left hand side that we then discard as below the desired range, and 2) We may want the lower (or lower and upper) bound(s) to be negative. The definition of iota used repeat for speed, but at some point either of the above drawbacks can bite us. So: fromto: function [lb [integer!] ub [integer!]] [r] [ r: make block! (ub - lb + 1) while [lb <= ub] [insert tail r lb lb: lb + 1] r ] ...which gives:
>> fromto 35 57
== [35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57] The tradeoff is between a small collection of general routines that work correctly but are not the fastest option, vs. tuning for speed and then having specialized functions that are "narrower" -- and we may need more of them. It would be interesting to have you try a couple of the above options along with your original for version and post the timings, if you have the spare time. -jn-