Re: Reverse: fastest yet, long post
Hawke writes:
<long post about how he now has the fastest reverse()>
I ran your program on my Pentium-150 and confirmed that
your new reverse() is faster than mine. So... I made an even
faster reverse() that beats your new one on all sizes from
about 10 up. I copied it into your program below:
Run number:1
length Hawke Rob !=winner
----------------------------
0 0.1220! 0.2940 reps:100000
1 0.1210! 0.3230 reps:100000
2 0.3439 0.3439! reps:100000
3 0.3819! 0.4219 reps:100000
4 0.4249! 0.4289 reps:100000
5 0.4719! 0.5129 reps:100000
6 0.5149! 0.5189 reps:100000
7 0.5589! 0.5909 reps:100000
8 0.6019 0.5979! reps:100000
9 0.6709! 0.6939 reps:100000
10 0.6649 0.6459! reps:100000
25 0.1300 0.1280! reps:10000
50 0.2340 0.2180! reps:10000
75 0.3429 0.3190! reps:10000
100 0.4579 0.4309! reps:10000
100 0.4489 0.4209! reps:10000
200 0.9139 0.8859! reps:10000
300 1.3528 1.2578! reps:10000
400 1.8557 1.7347! reps:10000
500 2.2827 2.1527! reps:10000
1000 0.4829 0.4529! reps:1000
1500 0.7449 0.6919! reps:1000
2000 1.0028 0.9409! reps:1000
2500 1.2688 1.1798! reps:1000
3000 1.6667 1.5708! reps:1000
3500 1.9027 1.7747! reps:1000
4000 2.0727 1.9617! reps:1000
4500 2.5276 2.3826! reps:1000
5000 2.9605 2.6516! reps:1000
10000 0.5899 0.5449! reps:100
15000 0.8899 0.8309! reps:100
20000 1.2128 1.1198! reps:100
25000 1.5138 1.4328! reps:100
30000 1.8707 1.7387! reps:100
35000 2.2907 2.0557! reps:100
40000 2.5706 2.3446! reps:100
45000 2.7946 2.6456! reps:100
50000 3.1335 2.9925! reps:100
Run number:2
length Hawke Rob !=winner
----------------------------
0 0.1210! 0.2420 reps:100000
1 0.1200! 0.3230 reps:100000
2 0.3289! 0.3299 reps:100000
3 0.3819! 0.4249 reps:100000
4 0.4259! 0.4269 reps:100000
5 0.4699! 0.5109 reps:100000
6 0.5779 0.5749! reps:100000
7 0.5579! 0.5939 reps:100000
8 0.6029 0.5949! reps:100000
9 0.6969! 0.7219 reps:100000
10 0.6619 0.6499! reps:100000
25 0.1300 0.1280! reps:10000
50 0.2330 0.2180! reps:10000
75 0.3399 0.3200! reps:10000
100 0.4629! 0.4789 reps:10000
100 0.4529 0.4139! reps:10000
200 0.9119 0.8729! reps:10000
300 1.3468 1.2438! reps:10000
400 1.8437 1.7247! reps:10000
500 2.2767 2.1427! reps:10000
1000 0.4869 0.4529! reps:1000
1500 0.7309 0.6839! reps:1000
2000 1.0008 0.9139! reps:1000
2500 1.3118 1.2258! reps:1000
3000 1.5098 1.4218! reps:1000
3500 1.8077 1.6797! reps:1000
4000 2.1597 2.0037! reps:1000
4500 2.3326 2.1927! reps:1000
5000 2.6126 2.4596! reps:1000
10000 0.5619 0.5269! reps:100
15000 0.8649 0.8029! reps:100
20000 1.1678 1.0918! reps:100
25000 1.4658 1.3788! reps:100
30000 1.8637 1.7367! reps:100
35000 2.3116 2.0627! reps:100
40000 2.5726 2.3496! reps:100
45000 2.8016 2.6366! reps:100
50000 3.1275 2.9945! reps:100
Run number:3
length Hawke Rob !=winner
----------------------------
0 0.1200! 0.2420 reps:100000
1 0.1210! 0.3240 reps:100000
2 0.3319 0.3309! reps:100000
3 0.3809! 0.4229 reps:100000
4 0.4239! 0.4299 reps:100000
5 0.4709! 0.5119 reps:100000
6 0.5149! 0.5179 reps:100000
7 0.5629! 0.5929 reps:100000
8 0.6629 0.6519! reps:100000
9 0.6479! 0.6769 reps:100000
10 0.7099 0.6989! reps:100000
25 0.1310 0.1280! reps:10000
50 0.2420 0.2240! reps:10000
75 0.3389 0.3190! reps:10000
100 0.4719 0.4399! reps:10000
100 0.4579 0.4139! reps:10000
200 0.9079 0.8769! reps:10000
300 1.3448 1.2468! reps:10000
400 1.8447 1.7237! reps:10000
500 2.2727 2.1417! reps:10000
1000 0.4839 0.4559! reps:1000
1500 0.7309 0.6799! reps:1000
2000 1.0018 0.9139! reps:1000
2500 1.3118 1.2228! reps:1000
3000 1.5088 1.4258! reps:1000
3500 1.8107 1.6797! reps:1000
4000 2.1587 2.0037! reps:1000
4500 2.3336 2.1937! reps:1000
5000 2.6116 2.4636! reps:1000
10000 0.5629 0.5259! reps:100
15000 0.8659 0.8049! reps:100
20000 1.1678 1.0938! reps:100
25000 1.4658 1.3828! reps:100
30000 1.8517 1.7367! reps:100
35000 2.3186 2.0647! reps:100
40000 2.5696 2.3496! reps:100
45000 2.7936 2.6416! reps:100
50000 3.1265 2.9965! reps:100
Here's your program with my new rev2():
--------------------------BEGIN CODE
without type_check
include machine.e
tick_rate(1000)
object junk, before, after, fn
procedure bothputs(object data)
puts(1, data) puts(fn,data)
end procedure
procedure bothprintf(sequence format,object data)
printf(1, format,data) printf(fn,format,data)
end procedure
function min(atom a, atom b)
if b<a then return b end if return a
end function
function rev1(sequence d) -- Hawke'
sequence new --t is to, f is from
integer len, f
len = length(d)
if len < 2 then return d end if --simple case, bye!
f = 0 new = repeat(0,len)
for t = len to 1 by -1 do --faster to make loop go down
f = f + 1 new[t] = d[f] --and INCrement inside loop
end for
return new
end function
-- function rev2(sequence s) -- Rob Craig -- old
-- object temp
-- integer n
-- n = length(s)
-- for i = 1 to floor(n/2) do
-- temp=s[i] s[i]=s[n] s[n]=temp n=n-1
-- end for
-- return s
-- end function
function rev2(sequence s) -- Rob Craig, new!
integer lower, n
sequence t
n = length(s)
t = repeat(0, n)
lower = 1
for upper = n to floor(n/2)+1 by -1 do
t[upper] = s[lower]
t[lower] = s[upper]
lower = lower + 1
end for
return t
end function
function measure(sequence what, integer reps)
-- time a routine, pass the timing result back
atom start
object junk, res res = {0,0}
junk = {} start = time()
for i = 1 to reps do junk = rev1(what) end for
res[1]= time() - start
junk = {} start = time()
for i = 1 to reps do junk = rev2(what) end for
res[2]= time() - start
if get_key() then end if
return res
end function
procedure preproc(integer reps)
for i = 1 to length(before) do
junk = before[i]
bothprintf ("%6d", length(junk))
after= measure(junk, reps)
junk = min(after[1],after[2])
bothprintf( "%10.4f" & (' ' + (junk = after[1])), after[1] )
bothprintf( "%10.4f" & (' ' + (junk = after[2])), after[2] )
bothprintf( " reps:%d", reps )
bothputs('\n')
end for
end procedure
after = {0,0,0}
fn = open("results.rev","w")
if fn = -1 then puts(1,"cant open") abort(1) end if
for run = 1 to 3 do
bothputs(sprintf("Run number:%d\n",run))
bothputs("length Hawke Rob !=winner \n")
bothputs("---------------------------- \n")
before = {{},"a","aa","AAA","AAAA"}
for i= 5 to 10 do before=append(before,repeat('a',i)) end
for
preproc(100000)
before = {}
for i= 25 to 100 by 25 do before=append(before,repeat('b',i)) end
for
for i= 100 to 500 by 100 do before=append(before,repeat('c',i)) end
for
preproc(10000)
before = {}
for i=1000 to 5000 by 500 do before=append(before,repeat('d',i)) end
for
preproc(1000)
before = {}
for i=10000 to 50000 by 5000 do before=append(before,repeat('d',i))
end for
preproc(100)
bothputs("\n\n")
end for
close(fn)
------------------END CODE
Regards,
Rob Craig
Rapid Deployment Software
http://members.aol.com/FilesEu/
|
Not Categorized, Please Help
|
|
