[REBOL] Re: newlines
From: lmecir:mbox:vol:cz at: 13-Nov-2001 10:36
Hi all,
I was curious, how the speed of PARSE-based algorithms compares with the
speed of some loop-based algorithms.
I used my TIME-BLOCK function (can be found at http://www.sweb.cz/LMecir/)
to compute the results, my system was an AMD 600 based 128 MB RAM Windows
98.
General results:
1) PARSE based versions of algorithms are faster than their loop-based
counterparts
2) Copy based algorithms are the fastest for high workload
3) CHANGE/PART work looks very strange, slow and unnatural. I would suggest
some revisions from RT. (any comments?)
4) Recursive algorithms don't work for texts of this size
5) My results slightly differ from Joel's
algorithms: [
PANY: [
while [s: find/tail s "..."] [
parse s [any #"." t:]
s: remove/part back s t
]
]
PRS1: [
parse/all s [
any [
".." mark1: any #"." mark2: (remove/part mark1 mark2) :mark1
|
skip
]
]
]
PRS2: [
nondot: complement charset {.}
parse/all s [
any [
some nondot
|
".." mark1: any #"." mark2: (remove/part mark1 mark2) :mark1
|
skip
]
]
]
BINR: [
newlen: length? s
until [
oldlen: newlen
oldlen = newlen: length? replace/all s ".................." ".."
]
replace/all s ".........." ".."
replace/all s "......" ".."
replace/all s "...." ".."
replace/all s "..." ".."
]
PASS: [
while [s: find s "..."][remove s]
]
comment {a PARSE based version of the PASS algorithm}
PARPASS: [
m: [any [to "..." s: (remove s)] to end]
parse/all s m
]
comment {a copy-like algorithm}
PARCHAN: [
method6: [
to "..." 2 skip t: sub |
to end
]
sub: [
any [
any #"."
copy u [
to "..." 2 skip (w: [(t: change t u)]) |
end (w: [(clear t) end skip]) |
to end (w: [(clear change t u) end skip])
]
w
]
]
parse/all s method6
]
comment {a PARSE-based version of PANY, a cross of my and Brett's
algorithms}
PARANY: [
method5: [
any [to "..." 2 skip t: any #"." u: :t (remove/part t u)]
to end
]
parse/all s method5
]
comment {Volker's COPY-based algorithm}
CS: [
out: clear ""
parse/all s [any [
start: thru "..." end1: any "."
(insert/part tail out start back end1)
]]
insert tail out start
out
]
comment {Volker's CHANGE/PART-based algorithm}
IPC: [
out: s
parse s [any [
start: thru "..." end1: any "."
(
change/part out start back end1
out: skip out subtract index? back end1 index? start
)
]]
change out start
clear skip out length? start
out: s
]
]
The results:
The last column contains the speed of the algorithm in per cent relative to
the fastest algorithm
10000 xxxxxxxxx.
CS 3E-4 100
PARANY 3.06E-4 98.01
PARPASS 3.1E-4 96.85
PASS 3.2E-4 93.71
PANY 3.41E-4 88.17
PARCHAN 6.15E-4 48.86
BINR 1.373E-3 21.88
IPC 2.338E-3 12.84
PRS2 2.419E-3 12.41
PRS1 5.915E-3 5.08
10000 xxxxx.....
CS 3.4E-3 100
PARCHAN 3.71E-3 91.64
PARANY 4.662E-3 72.92
PANY 6.727E-3 50.54
PARPASS 7.821E-3 43.47
PASS 9.11E-3 37.32
PRS2 9.325E-3 36.46
PRS1 9.491E-3 35.82
BINR 1.0829E-2 31.39
IPC 0.102694 3.31
10000 x.........
PARCHAN 4.414E-3 100
CS 4.497E-3 98.15
PARANY 5.786E-3 76.29
PRS1 6.563E-3 67.26
PRS2 6.851E-3 64.43
PANY 8.403E-3 52.53
BINR 1.8491E-2 23.87
PARPASS 4.2417E-2 10.41
PASS 4.9487E-2 8.92
IPC 0.131909 3.35
20000 xxxxxxxxx.
CS 6.3E-4 100
PARPASS 7.11E-4 88.67
PARANY 7.11E-4 88.67
PASS 7.62E-4 82.71
PANY 8.04E-4 78.44
PARCHAN 1.287E-3 48.98
BINR 2.818E-3 22.37
PRS2 5.123E-3 12.31
IPC 6.915E-3 9.12
PRS1 1.212E-2 5.2
20000 xxxxx.....
CS 6.918E-3 100
PARCHAN 7.562E-3 91.48
PARANY 1.4603E-2 47.37
PANY 1.8998E-2 36.41
PRS2 2.4037E-2 28.78
PRS1 2.4681E-2 28.03
PARPASS 2.6615E-2 25.99
BINR 2.7357E-2 25.29
PASS 2.931E-2 23.6
IPC 0.378842 1.83
20000 x.........
PARCHAN 8.588E-3 100
CS 8.862E-3 96.91
PARANY 1.6967E-2 50.62
PRS1 1.8334E-2 46.84
PRS2 1.8881E-2 45.49
PANY 2.2397E-2 38.35
BINR 4.1928E-2 20.48
PARPASS 0.144467 5.94
PASS 0.160795 5.34
IPC 0.459467 1.87
30000 xxxxxxxxx.
CS 1.04E-3 100
PARANY 1.179E-3 88.2
PARPASS 1.208E-3 86.06
PASS 1.248E-3 83.37
PANY 1.299E-3 80.08
PARCHAN 1.985E-3 52.4
BINR 4.307E-3 24.15
PRS2 7.568E-3 13.74
IPC 1.3799E-2 7.54
PRS1 1.8096E-2 5.75
30000 xxxxx.....
CS 1.0313E-2 100
PARCHAN 1.1387E-2 90.57
PARANY 2.8916E-2 35.66
PANY 3.5654E-2 28.92
PRS2 4.3857E-2 23.51
PRS1 4.4287E-2 23.29
BINR 4.9365E-2 20.89
PARPASS 5.5381E-2 18.62
PASS 5.9287E-2 17.39
IPC 0.809209 1.27
30000 x.........
PARCHAN 1.2888E-2 100
CS 1.322E-2 97.49
PARANY 3.3942E-2 37.97
PRS1 3.6325E-2 35.48
PRS2 3.7419E-2 34.44
PANY 4.1911E-2 30.75
BINR 7.0934E-2 18.17
PARPASS 0.304841 4.23
PASS 0.330466 3.9
IPC 0.974216 1.32
