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

creation of a block with a lot of integers

 [1/6] from: peoyli:algonet:se at: 5-Oct-2000 16:55


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]
>>
A work-around, appending a 'clear testblock' after the testblock: [] will fix this, but shouldn't testblock: [] do it in the first place ? /PeO

 [2/6] from: al::bri::xtra::co::nz at: 5-Oct-2000 17:24


> Is there a efficient way of creating a block consisting of a range of
integers? For 1 to N, yes (based on jn's code: Iota: function [N [integer!]] [Block] [ Block: make block! N repeat I N [insert tail Block I] Block ]
>> iota 6
== [1 2 3 4 5 6] If you want to put in a refinement /Initial etc, feel free.
> also.. is this supposed to function like this (local variable is not
cleared between function calls) ?
> testblock: [] > >> maybe-bug 1 5 > == [5 4 3 2 1] > >> maybe-bug 1 5 > == [5 4 3 2 1 5 4 3 2 1]
That's correct. Check out Rebol Core .pdf manual, page 261, 8-19, Local Variables Containing Series for an explanation. Alternatively, use: testblock: copy [] or: testblock: make block! YourLengthValue Andrew Martin ICQ: 26227169 http://members.nbci.com/AndrewMartin/

 [3/6] 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
<<quoted lines omitted: 23>>
> == [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-

 [4/6] from: peoyli:algonet:se at: 6-Oct-2000 10:59


This is a MIME encoded multipart message. The fact that you are reading this means you don't have a MIME capable mail program. You might still be able to read part of the mail's content, but some of it may require a MIME capable mail reader to decode. Following are some URLs where you can find MIME-capable mail programs for common platforms: Amiga............: MicroDot-II http://www.vapor.com/ Unix.............: Metamail ftp://ftp.bellcore.com/nsb/ Windows/Macintosh: Eudora http://www.qualcomm.com/ General info about MIME can be found at: http://www.cis.ohio-state.edu/hypertext/faq/usenet/mail/mime-faq/top.html --=_=8<==MD239DE23B4-42B45C89==8<=_Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit
> Hi, peoyli, >
...
> 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-
Ok,, here comes my test results, along with the code being tested.. Method 0: 1st try: unallocated block, for-loop, insert Method 1: 2nd try: allocated block, for-loop, insert tail Method 2: 3rd try: allocated block, modified iota to accept a minimum value (repeat-loop) Method 3: 4th try: allocated block, map iota... (repeat-loop) Method 4: 5th try: allocated block, filter iota / range... Method 5: 6th try: allocated block, fromto function... (while-loop) Summary: Method 0 is slow (only timed with 5000 values) Method 2 is twice as fast as method 1 (repeat vs. for) Method 3 always gave incorrect result or failed otherwise (and was also twice as slow as method 1) Method 4 did not work with negative values, and was about as slow as method 3 Method 5 is almost as fast as method 2 Method 2 (3rd try) & Method 5 (6th try) are those who produce the desired result, and is most efficient. num of values range 5000 50000 100000 200000 400000 20001-25000 20001-70000 20001-120000 20001-220000 20001-420000 Method 0 0:00:34 - - - - 1 0:00:01 0:00:10 0:00:19 0:00:38 - 2 0:00 0:00:05 0:00:10 0:00:20 0:00:41 3 *1) 0:00:17 *2) 0:00:37 *2 0:01:16 *2) - 4 0:00:05 0:00:17 0:00:30 0:00:59 - 5 0:00 0:00:05 0:00:11 0:00:24 0:00:46 100001 100001 -50000 - 50000 -150000 - -50000 0 - - 1 0:00:20 0:00:18 2 0:00:10 0:00:10 3 0:00:37 *3) 0:00:38 *3) 4 0:00:13 *4) *5) 5 0:00:11 0:00:11 *1) Script Error (caused by the result printing, block size = 0) 27.Work:Programming/REBOL_core_2.3> rebol -q ../REBOL/intblock.r 20001 25000 3 0:00:01 4th try: allocated block, map iota... Size of block: 0 ** Script Error: Out of range or past end. ** Where: first b *2) Incorrect result 27.Work:Programming/REBOL_core_2.3> rebol -q ../REBOL/intblock.r 20001 70000 3 0:00:17 4th try: allocated block, map iota... Size of block: 30000 Block's first value: 20001 Block's last value: 50000 27.Work:Programming/REBOL_core_2.3> rebol -q ../REBOL/intblock.r 20001 120000 3 0:00:37 4th try: allocated block, map iota... Size of block: 80000 Block's first value: 20001 Block's last value: 100000 27.Work:Programming/REBOL_core_2.3> rebol -q ../REBOL/intblock.r 20001 220000 3 0:01:16 4th try: allocated block, map iota... Size of block: 180000 Block's first value: 20001 Block's last value: 200000 *3) Incorrect result intblock -50000 50000 3 intblock -150000 -50000 3 0:00:37 4th try: allocated block, map iota... Size of block: 100001 Block's first value: 1 Block's last value: 100001 *4) Incorrect result intblock -50000 50000 4 0:00:13 5th try: allocated block, filter iota / range... Size of block: 50000 Block's first value: 1 Block's last value: 50000 *5) Script Error (caused by the result printing, block size = 0) 0:00 5th try: allocated block, filter iota / range... Size of block: 0 ** Script Error: Out of range or past end. ** Where: first b --=_=8<==MD239DE23B4-42B45C89==8<=_Content-Type: text/plain; charset=us-ascii; name="intblock.r" Content-Transfer-Encoding: plain (7/8 bit) Content-Disposition: attachment; filename="intblock.r" X-MD2-FilePath: Work:Programming/REBOL/intblock.r REBOL [] ; Parameters: num, min iota_mod: function [n [integer!] min [integer!]] [r i] [ r: make block! n repeat i n [insert tail r i + min - 1] r ] ; Parameters: num iota: function [n [integer!]] [r i] [ r: make block! n repeat i n [insert tail r i] r ] 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 ] 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 ] range: func [lb [integer!] ub [integer!]] [ filter iota ub func [n] [n >= lb] ] fromto: function [lb [integer!] ub [integer!]] [r] [ r: make block! (ub - lb + 1) while [lb <= ub] [insert tail r lb lb: lb + 1] r ] intblock: func [ "Create an array with a range of integers" min [integer!] "The lowest number to include" max [integer!] "The highest number to include" meth [integer!] "Method of creating block with values" /local temp ][ if min > max [temp: min min: max max: temp] num: max - min + 1 switch meth [ ; 1st try: unallocated block, for-loop, insert 0 [ tim1: now/time b: [] clear b for temp min max 1 [ insert b temp ] ; Generate array with valid numbers print reduce [now/time - tim1 " 1st try: unallocated block, for-loop, insert"] ] ; 2nd try: allocated block, for-loop, insert tail 1 [ tim1: now/time b: make block! num for temp min max 1 [ insert tail b temp ] ; Generate array with valid numbers print [now/time - tim1 " 2nd try: allocated block, for-loop, insert tail"] ] ; 3rd try: allocated block, modified iota to accept a minimum value 2 [ tim1: now/time b: iota_mod abs (max - min + 1) min print [now/time - tim1 " 3rd try: allocated block, modified iota to accept a minimum value"] ] ; 4th try: allocated block, map iota... 3 [ tim1: now/time b: map iota (max - min + 1) func [n] [if n >= min [n]] print [now/time - tim1 " 4th try: allocated block, map iota..."] ] ; 5th try: allocated block, filter iota / range... 4 [ tim1: now/time b: range min max print [now/time - tim1 " 5th try: allocated block, filter iota / range..."] ] ; 6th try: allocated block, fromto function... 5 [ tim1: now/time b: fromto min max print [now/time - tim1 " 6th try: allocated block, fromto function..."] ] ] print reduce ["Size of block: " length? b] print reduce ["Block's first value: " first b] print reduce ["Block's last value: " last b] b ] ;args: load system/script/args ;args: parse first args " " ;min: to-integer args/1 ;max: to-integer args/2 ;meth: to-integer args/3 ;intblock min max meth intblock -150000 -50000 4 --=_=8<==MD239DE23B4-42B45C89==8<=_=-- (end of MIME multipart message)

 [5/6] from: joel:neely:fedex at: 6-Oct-2000 14:36


Thanks for the numbers! [peoyli--algonet--se] wrote:
> > Hi, peoyli, > >
<<quoted lines omitted: 21>>
> Method 2 (3rd try) & Method 5 (6th try) are those who produce the > desired result, and is most efficient.
Method 3 is buggy as written: ; 4th try: allocated block, map iota... 3 [ tim1: now/time b: map iota (max - min + 1) func [n] [if n >= min [n]] print [now/time - tim1 " 4th try: allocated block, map iota..."] ] Taking as an example MIN=2000 and MAX=5000, the expression iota (max - min + 1) evaluates to [1 2 3 4 5 ... 2999 3000 3001] The function func [n] [if n>= min [n]] applied by MAP essentially says "discard everything below 2000". The result is that you should get [2000 2001 2002 2003 ... 2998 2999 3000 3001] as the result, which isn't the range MIN thru MAX. To use a combination of MAP and IOTA to create the range MIN thru MAX, you'll need to do one of the following: 1) Create the full range of values (1 thru MAX), then discard all values outside the desired range (below MIN). I gave this as an example in my earlier post, using something like: map iota max func [n] [if n >= min [n]] 2) Create the correct number of values (1 thru something), then adjust all values in the created block up/down to the desired range. This would look something like this: map iota (max - min + 1) func [n] [n + min - 1] (The IOTA (MAX - MIN + 1) gets you [1 ... 3001], then the MAP adds 1999 to each of those values, leaving you with [2000 ... 5000].) If you mix these two techniques, they don't play well together. It's also no surprise that this will be slower than the custom-made versions, as it is creating the block of numbers and then revisiting all of them a second time. Classic tradeoff #27: speed vs. generality! -jn- -- ; Joel Neely [joel--neely--fedex--com] 901-263-4460 38017/HKA/9677 REBOL [] print to-string debase decompress #{ 789C0BCE0BAB4A7176CA48CAB53448740FABF474F3720BCC B6F4F574CFC888342AC949CE74B50500E1710C0C24000000}

 [6/6] from: peoyli:algonet:se at: 7-Oct-2000 15:05


This is a MIME encoded multipart message. The fact that you are reading this means you don't have a MIME capable mail program. You might still be able to read part of the mail's content, but some of it may require a MIME capable mail reader to decode. Following are some URLs where you can find MIME-capable mail programs for common platforms: Amiga............: MicroDot-II http://www.vapor.com/ Unix.............: Metamail ftp://ftp.bellcore.com/nsb/ Windows/Macintosh: Eudora http://www.qualcomm.com/ General info about MIME can be found at: http://www.cis.ohio-state.edu/hypertext/faq/usenet/mail/mime-faq/top.html --=_=8<==MD239DFB81A-66DA01C5==8<=_Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit
> Thanks for the numbers! >
Here's some more tests.. I did the same test using perl, and its native .. range operator: 50000 100000 200000 400000 20001-70000 20001-120000 20001-220000 20001-420000 REBOL 5s 10s 20s 41s Perl 1s 3s 8s 15s 100001 100001 -50000 - 50000 -150000 - 50000 REBOL 10s 10s Perl 5s 4s I can run a test in assembly language too, but I think it will be too fast to be timed even with 400000 values... Maybe REBOL could need a native range operator anyway (I've seen that discussion some time ago) ? /PeO
> [peoyli--algonet--se] wrote: > >
<<quoted lines omitted: 12>>
> > here comes my test results, along with the code being tested.. > >
--=_=8<==MD239DFB81A-66DA01C5==8<=_Content-Type: text/plain; charset=us-ascii; name="jox.pl" Content-Transfer-Encoding: plain (7/8 bit) Content-Disposition: attachment; filename="jox.pl" X-MD2-FilePath: Ram Disk:jox.pl #!/usr/local/bin/perl intblock(20001, 25000); intblock(20001, 70000); intblock(20001, 120000); intblock(20001, 220000); intblock(20001, 420000); intblock(-50000, 50000); intblock(-150000, -50000); sub intblock { my($min,$max) = @_; local($len_a,$tim1); $tim1 = time(); @a = ($min..$max); print "\nElapsed time: ", time() - $tim1, " seconds\n"; $len_a = @a; print "Size of array: $len_a\n"; print "Array's first value: $a[0]\n"; print "Array's last value: $a[$len_a - 1]\n"; } --=_=8<==MD239DFB81A-66DA01C5==8<=_=-- (end of MIME multipart message)

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted