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

[REBOL] Re: Algorithm challenge: compacting integers

From: SunandaDH:aol at: 21-Jan-2007 19:16

There's been a flurry of entrants and versions on Altme/REBOL3. Which is great -- I'm delighted so many people are taking an interest. But it's confusing me -- as to which versions to benchmark. It's not really fair to publish benchmark results here for versions that are not public. So here is the code I am using for the benchmarks.....Feel free to tune yours (or any one else's) versions using this. You'll need three source files for the benchmarks: file 1: profile-timer -- download it from the Library: http://www.rebol.org/cgi-bin/cgiwrap/rebol/view-script.r?script=profile-timer. r file 2: cut'n'paste the source below, and save it as (say) cd-timer-tests.r Then do %cd-timer-tests.r to run the benchmarks file 3: the block of code below. Cut'n'paste it and save it as ce-entries.r It is a block containing people's functions. The note at the start of cd-timer-tests.r explains how to extend it to add other people's functions. The version of cd-entries.r I've published here has only mine and Victor's offerings in it -- ie only the versions published on the mailing list. And good luck if you are about to enter! Sunanda. ========= File 2 -- cd-timer-tests.r ========== rebol [] ;; test driver for compact // decompact code ;; ----------------------------------------- ;; assumes cd-entries.r is a block looking like this: ;; make object! [ ;; "name" ;; compact-func ;; decompact-func ;; "name" ;; compact-func ;; decompact-func ;; etc ;; ] ;; ;; ie three entries per entrant: ;; 1. their name (as a string that can be hefted into a REBOL word) ;; 2. their compact algorithm or NONE (if they don't have one) ;; 3. their decompact algorithm or NONE (if they don't have one) do %profile-timer.r ;; it's in the Library ;; load the test data sets ;; ======================= cd-entries: reduce first reduce load/all %cd-entries.r sort/skip cd-entries 3 ;; function to produce random test sequences ;; ========================================= seed-test-block: func [ size [integer!] gaps [number!] /local generated-block ][ generated-block: make block! size loop size [append generated-block to-integer (random/secure size * gaps)] return unique sort generated-block ] ;; Time the compact functions ;; =========================== ;; set up data areas ;; ================= expected-res: copy [] elapse-time: none res-object: make object! [note: "Compact times" run-on: now] foreach [entrant-name compact-func decompact-func] cd-entries [ if function? :compact-func [ res-object: make res-object reduce [to-set-word entrant-name 0.0] ] ] foreach [b-size gap iters] [ 30000 1.20 10 25000 0.95 20 10000 2.25 5 ][ foreach [entrant-name compact-func decompact-func] cd-entries [ if function? :compact-func [ test-block: seed-test-block b-size gap ;; ------------------------------------------- ;; by definition, Sunanda's is right as it has ;; been running live for several years. (okay, we ;; may find an error, but let's hope not) expected-res: do first next find cd-entries "sunanda (live code)" test-block ;; --------------------------------------------- test-res: make block! length? test-block profile-timer/reset "" prin ["testing: " entrant-name b-size gap iters " ..... " ] profile-timer/start entrant-name ;; run the test many times: ;; ----------------------- loop iters [test-res: compact-func test-block] profile-timer/stop entrant-name elapse-time: get in profile-timer/show entrant-name 'total-time prin elapse-time set in res-object to-word entrant-name (get in res-object to-word entrant-name) + (elapse-time / iters / b-size) if test-res <> expected-res [prin [" BAD COMPACT"] halt] print "" ] ;; if ] ;; for ] ;; for probe res-object ;; ============================================================ ;; Time the decompact functions ;; ============================= ;; set up data areas ;; ================= expected-res: copy [] elapse-time: none res-object: make object! [note: "Decompact times" run-on: now] foreach [entrant-name compact-func decompact-func] cd-entries [ if function? :decompact-func [ res-object: make res-object reduce [to-set-word entrant-name 0.0] ] ] foreach [b-size gap iters] [ 30000 1.20 10 25000 0.95 20 10000 2.25 5 ][ foreach [entrant-name compact-func decompact-func] cd-entries [ if function? :decompact-func [ test-block: seed-test-block b-size gap expected-res: copy test-block test-block: do first next next find cd-entries "sunanda (live code)" test-block test-res: make block! length? test-block profile-timer/reset "" prin ["testing: " entrant-name b-size gap iters " ..... " ] profile-timer/start entrant-name ;; run the test many times: ;; ----------------------- loop iters [test-res: decompact-func test-block] profile-timer/stop entrant-name elapse-time: get in profile-timer/show entrant-name 'total-time prin elapse-time set in res-object to-word entrant-name (get in res-object to-word entrant-name) + (elapse-time / iters / b-size) if test-res <> expected-res [prin [" BAD DECOMPACT"]] print "" recycle ] ;; if ] ;; for ] ;; for probe res-object ======== end of file2 ========== ========file 3: cd-entries.r ========= [ sunanda (live code) ;; Compact ;; ------- func [eid-block [block!] /local packed-block run-start run-length ][ ;; We got something like: ;; [100 140 141 142 150 200 201] ;; We return: ;; [100 140x3 150 200x2] packed-block: copy [] ;;make block! length? eid-block ;; at least enough if (length? eid-block) = 1 [return copy eid-block] run-start: eid-block/1 run-length: 0 for nn 2 length? eid-block 1 [ run-length: run-length + 1 if eid-block/:nn <> (run-start + run-length) [ either 1 = run-length [insert tail packed-block run-start] [insert tail packed-block make pair! reduce [run-start run-length]] run-start: eid-block/:nn run-length: 0 ] ] ;; for either 0 = run-length [insert tail packed-block run-start] [insert tail packed-block make pair! reduce [run-start run-length + 1]] return packed-block ] ;; Decompact ;; --------- func [eid-block [block!] /local temp unpacked-block ][ ;; We got something like: ;; [100 140x3 150 200x2] ;; We return: ;; [100 140 141 142 150 200 201] unpacked-block: copy [] ;;make block! 5 * length? eid-block ;; a guess foreach ent eid-block [ either integer? ent [append unpacked-block ent] [ if not none? ent [ temp: ent/1 - 1 repeat nn ent/2 [insert tail unpacked-block temp + nn] ] ] ] return unpacked-block ] Viktor v3 ;; compact ;; ------- func [blk /local result fst a b runl][ if empty? blk [return blk] result: make list! length? blk runl: 1 fst: a: first blk foreach b next blk [ either = + 1 a b [ if runl = 1 [fst: a] runl: runl + 1 ][ insert result either runl = 1 [a][as-pair fst runl] runl: 1 ] a: b ] insert result either runl = 1 [a][as-pair fst runl] to-block head result ] ;; decompact ;; --------- func [blk /local result item][ result: make list! 2 * length? blk foreach item blk [ either pair? item [ i: item/1 - 1 loop item/2 [insert result i: i + 1] ][ insert result item ] ] to-block head result ] ] ;; ========== end of file 3=========