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

[REBOL] Re: FW: Re: [append][series]Appending to a series of strings

From: joel:neely:fedex at: 20-Nov-2003 13:22

Hi, Ladislav, Actually, it's not faster (for sufficiently large cases). See below. Ladislav Mecir wrote:
> Hi, my solution using Parse (I think, that it is much faster, than > other solutions): >
I did a bit of benchmarking with functions that use each of the three strategies to generate a block of answers (value/count pairs). I'll include those functions at the end, in case anyone wants to verify that I didn't mangle any code. Using a SCORES block of random numbers between 0 and 100 (inclusive), the iterative version scales up better than the parse-based version as the size of the SCORES block increases (all times in seconds): size iterative remove-each parse-based 1000 1E-2 0.28 0 10000 0.351 2.874 0.24 100000 3.024 36.813 4.637 200000 4.787 -- 4.556 300000 6.74 -- 6.94 400000 8.832 -- 14.371 500000 11.887 -- 18.517 1000000 21.891 -- 39.227 I gave up VERY quickly on the remove-each-based version; it gets eaten alive by memory management overhead. Since the parse-based version sorts (a copy of) the scores block, its time complexity must be at least O (n log n). The iterative version is only O (n), so it will be faster for sufficiently large n. I should also point out that the iterative version requires only one value at a time; it can work on an arbitrarily large set of values (e.g., being retrieved across a network connection, read from a huge data file, resulting from computation in a loop, etc.), but the remove- and parse-based versions require the entire set to be available for sorting. There's one final point, but I'll post it separately. -jn- Ladislav Mecir wrote:
> scores: clear [] > loop 30 [append scores random 20] > group: [p: set i integer! any i q: (print ["score:" i "tallies:" > offset? p q])] > parse probe sort scores [any group] > >>-----Original Message----- >>From: Anton Rolls [mailto:[antonr--iinet--net--au]] >> >>; initialize some random scores >>scores: clear [] >>loop 30 [append scores random 20] >> >>; figure out how many of each score >>tallies: clear [] >>foreach uscore sort unique scores [ >> append/only tallies reduce [ >> uscore >> length? remove-each score copy scores [uscore <> score] >> ] >>] >>
SOURCE CODE FOR TIMED FUNCTIONS IS GIVEN BELOW: ;iterative version tally-i: func [ scores [block!] /local tallies result ][ tallies: copy [] foreach score scores [ either found? here: select tallies score [ here/1: here/1 + 1 ][ insert tail tallies reduce [score copy [1]] ] ] result: make block! length? tallies foreach [score tally] sort/skip tallies 2 [ insert tail result score insert tail result tally ] result ] ;remove-each-based version tally-r: func [ scores [block!] /local tallies ][ tallies: clear [] foreach uscore sort unique scores [ append/only tallies reduce [ uscore length? remove-each score copy scores [uscore <> score] ] ] ] ;parse-based version tally-p: func [ scores [block!] /local group p q result ][ result: copy [] group: [ p: set i integer! any i q: ( insert tail result i insert tail result offset? p q ) ] parse sort copy scores [any group] result ] -- ---------------------------------------------------------------------- Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446 Enron Accountingg in a Nutshell: 1c=$0.01=($0.10)**2=(10c)**2=100c=$1