1. Reverse() was: Win32Lib Update
Ralf Nieuwenhuijsen wrote:
> Why not start a thread ? 
> function reverse_flat (sequence s)
> sequence result
> result = {}
> for index = 1 to length(s) do
> result = prepend(result, s[index])
> end for
> return result
> end function
I'll jump in here :>
y'all should know i cannae r'fuse a speed tweak :>
let's try:
func rev_flat(seq data)
seq result
int len, from
len = length(data)
from = len --i really could reuse len....
result = repeat(0,len) --BOOM, call alloc *once*
for toindex = 1 to len do
result[toindex] = data[from]
from = from - 1 --and this takes 1 single tick...
end for
return result
end func
now, this (should be/is) faster than prepend...
1:im not having to worry about all that alloc,
alloc even more, alloc even more AGAIN... etc...
that prepend/append will do as it grows a new seq...
yes, pre/append DOES alloc a little more... but,
i have seen EU take a realllyyyy hard, long "think"
in my fuzzy logic library on attempting to find a
'truth' while performing image recognition chores...
this is how/why i found this method, and no, i haven't
had time to update all of the fuzzy library to take
advantage of this...
someone once said on the list that repeat() doesn't
work good on large sequence creation, like after a
couple hundred thousand or so.... i never found that...
has anyone???
2: im only swapping pointers :)
and, of course, recursing this would be easy....
func recurseREV(seq data)
seq result
int len, from
object temp
len = length(data)
from = len
result = repeat(0,len)
for toindex = 1 to len do
temp = data[from]
if atom(temp) then
result[toindex] = temp
else result[toindex] = recurseREV(temp)
end if
from = from - 1
end for
return result
end func
so... who gonna bncmrk???
:)
ta! --Hawke'
2. Re: Reverse() was: Win32Lib Update
Hawke suggested:
>now, this (should be/is) faster than prepend...
>1:im not having to worry about all that alloc,
>alloc even more, alloc even more AGAIN... etc...
>that prepend/append will do as it grows a new seq...
As I recall, an append/prepend as only statement in a for-block will be
optimized to one alloc, one pass proccesing.
>yes, pre/append DOES alloc a little more... but,
>i have seen EU take a realllyyyy hard, long "think"
>in my fuzzy logic library on attempting to find a
>'truth' while performing image recognition chores...
You were prolly appending/prepending to an sliced/indexed sequence. All
optimization fails at this point: result, for every append/prepend, it
reallocates a sequence of the new length, copies the old sequence, copies
the new part, frees the old sequence. And yes, this is sloooww indeed.
>someone once said on the list that repeat() doesn't
>work good on large sequence creation, like after a
>couple hundred thousand or so.... i never found that...
>has anyone???
Me neither.
>so... who gonna bncmrk???
Maybe later today.. still working on my new graphical botmatch routines..
Ralf
3. Re: Reverse() was: Win32Lib Update
Ralf Nieuwenhuijsen wrote:
> Hawke suggested:
> >now, this (should be/is) faster than prepend...
> >1:im not having to worry about all that alloc,
> >alloc even more, alloc even more AGAIN... etc...
> >that prepend/append will do as it grows a new seq...
> As I recall, an append/prepend as only statement in a for-block will be
> optimized to one alloc, one pass proccesing.
errrrr.... i really don't think so....
see irv's benchmarks...
ummmm.... the prepend came in last... :/
i could make mine go even faster, especially for large
iterations of piddly sized sequences (like the one
thrown at it in the benchmark...)
the newer, tweaked just a little more (alot for large
iteration/small sequences) is:
func rev(seq data)
int junk
seq result
junk = length(data)
for from = 1 to junk do
result[from] = data[junk]
junk = junk - 1
end for
return result
end func
i just saved 100000 clock ticks for irv's bnchmrk...
not shabby...
a million length seq? saved 1000000 clock ticks...
the reason this came in second to mine is:
x = length(s)
r = repeat(0,x)
for i = 1 to x do
r[i] = s[x-i+1] --right here, you blew 100000 ticks...
end for --million length? 1000000 ticks...
return r
> >yes, pre/append DOES alloc a little more... but,
> >i have seen EU take a realllyyyy hard, long "think"
> >in my fuzzy logic library on attempting to find a
> >'truth' while performing image recognition chores...
> You were prolly appending/prepending to an sliced/indexed sequence. All
> optimization fails at this point: result, for every append/prepend, it
> reallocates a sequence of the new length, copies the old sequence, copies
> the new part, frees the old sequence. And yes, this is sloooww indeed.
actually, i was doing nearly exactly what you were...
to wit:
you have a pair of sequences... indicies matching element for element...
you want to know the minimum value at each index and grab that
element...
a={10,20,10,0,10,20}
b={20,20,10,20,0,10}
u have min()
func min (atom a, atom b)
if a>b then a=b end if
return a
end func
(its faster than the one by carl for large seq...)
so.... i tried this first... it's what u are suggesting,
a one statment for block...
func one(seq: l1, l2)
seq r r={}
for i = 1 to length(l1) do
r = r & min(l1,l2)
end for
return r
end func
and.... it's slowwwww...
throw a few 800x600x16.7M images at it... u snore...
(remembering to adjust for each pixel being a length3 seq)
i then did:
func two(seq l1,l2)
int len
seq r
len = length(l1)
r = repeat(0,len)
for i = 1 to len do
r[i] = min(l1,l2)
end for
return i
end for
and i began clocking decent speeds....
*shrug*...
i wouldn't have offered my observations about this pre/appending
issue had i not watched EU suddenly BOG when i went over about
a 400x400x16.7M image....
i was clocking what i thought were good timings in the fuzzy logic
computations... i tried a 100x100x1 sequence... flew along, had
to do a couple thousand iterations to build up to a second... went
to 200x200x1... roughly doubled time... 300x300x1.. still no worries...
started working on really bigXfew iterations....
1000000x1... clipped along... 100000x10... no worries... etc...
then reversed that... really smallXlots iterations...
10x10000... no prob... 100x1000... zoom...
so i said... lets go truecolor...
100x100x3 was bout 3 times as long as 100x100x1...
took like a second... 200x200x3 was bout 5 (i think...,
these numbers don't need to be accurate, because it was
the relationship of the values that will bear out in a moment)
and 300x300x3 was.. mebbe a minute...
i hit 400x400x3 (or so...) and **WHAM**
i went, got coffee, came back, smoked a cig, came back,
... nada... it took like 15 minutes... just out of nowhere...
shoulda been ...ohhh... maybe 3 minutes *tops*
so i said this won't do... and found the problem to be
appending/prepending... once i started playing the shuffle
pointer game, it smoothed out and its a pretty fast library
as a result of the extensive benchmarking i did on this issue...
hope this helps someone... --Hawke'
4. Re: Reverse() was: Win32Lib Update
>> As I recall, an append/prepend as only statement in a for-block will be
>> optimized to one alloc, one pass proccesing.
>errrrr.... i really don't think so....
>see irv's benchmarks...
>ummmm.... the prepend came in last... :/
;-(
Robert, said append and prepend were like, really really optimized.
And for-statements as well..
So, Robert (or Junko now it seems again, could there be some 'extra'
optimization with statement blocks like for- and while- . Esspecially when
they contain only one statement. (which should be fairly easy to optimize).
But I was also thinking of multiple 'slices'/'indexes' to be looked up only
once, within a statement block. And off couse the "for each item in
my-sequence do" - syntax provides both optimization 'oppertunities' as well
as increased error checking, and more readable code.
Ralf
5. Re: Reverse() was: Win32Lib Update
My attemp:
function reverse(object data)
object aux
integer midway
if sequence(data) then
midway = floor(length(data) / 2)
if midway != (length(data) / 2) then
for index = 1 to midway do
aux = reverse(data[index])
data[index] = reverse(data[(midway*2) - index + 2])
data[(midway*2) - index + 2] = aux
end for
data[midway+1] = reverse(data[midway+1])
else
for index = 1 to midway do
aux = reverse(data[index])
data[index] = reverse(data[(midway*2) - index + 1])
data[(midway*2) - index + 1] = aux
end for
end if
end if
return data
end function
I'm no speed demon, but I belive this routine is fairly fast and most
important... it's generic and flexible.
Regards,
Daniel Berstein
daber at pair.com
6. Re: Reverse() was: Win32Lib Update
Ad Rienks writes:
> I'm sorry, but I made a mistake. The function reverse() *is*
> in the 'official' release of Win32Lib v0.15a, it was only missing
> from the copy sent with the calc021 program.
Thanks for pointing this out. It was my mistake. It's corrected now.
Since adding a reverse() function to misc.e for 2.1, I have to
remove Cuny's reverse() before running win32lib programs. I
accidentally uploaded calc021 minus his reverse().
This raises a couple of issues:
1. I should probably not make it an error (just a warning) to override
a global symbol with a local symbol. The local should
take precedence within the file it is declared in.
I'm not sure if I'll do it for this release. It involves changes
to compile-time symbol lookup, run-time symbol lookup
(trace and routine_id) as well as the bind.ex program.
It would alleviate some of the namespace conflicts.
2. Which reverse() is the fastest? I was planning to add a
Euphoria-coded reverse() to misc.e. A few weeks ago
I coded reverse5() below, but it looks like reverse2() (Hawke)
is the fastest, so I'll use his unless someone comes up
with something even faster.
-- taken from Irv's last post:
without type_check
include machine.e
tick_rate(100)
sequence before, after
atom start, fini
before = "Now is the time for all good men to come get drunk at the party."
function reverse1(sequence s) -- Ralf
sequence r
r = {}
for i = 1 to length(s) do
r = prepend(r,s[i])
end for
return r
end function
function reverse2(sequence data) -- Hawke' (newer one)
sequence result
integer len
len = length(data)
result = repeat(0,len) --BOOM, call alloc *once*
for toindex = 1 to len do -- initial value of len sets the limit
result[toindex] = data[len]
len = len - 1
end for
return result
end function
function reverse3 (sequence s) -- Irv
atom temp, left, right
left = 1
right = length(s)
while left < right do
temp = s[left]
s[left] = s[right]
s[right] = temp
left = left + 1
right = right - 1
end while
return s
end function
function reverse4 (sequence s) -- Ad Rienks
atom x
sequence r
x = length(s)
r = repeat(0,x)
for i = 1 to x do
r[i] = s[x-i+1]
end for
return r
end function
function reverse5(sequence s) -- Rob Craig
object temp
integer n
n = length(s)+1
for i = 1 to floor((n-1)/2) do
temp = s[i]
s[i] = s[n-i]
s[n-i] = temp
end for
return s
end function
function reverse6( sequence s1 ) -- David Cuny
-- reverse a sequence
-- Ex: reverse( "12345" )
-- --> "54321"
sequence s2
s2 = {}
for i =length(s1) to 1 by -1 do
s2 = append( s2, s1[i] )
end for
return s2
end function
procedure measure(sequence name)
-- time a routine
integer id
id = routine_id(name)
start = time()
for i = 1 to 100000 do
-- not a normal call, but shouldn't make much difference
after = call_func(id, {before})
end for
fini = time()
printf(1, "%s: %.2f seconds for 100000 iterations\n", {name,
fini-start})
puts(1, after)
puts(1, '\n')
end procedure
measure("reverse1") -- 5.06
measure("reverse2") -- 3.30
measure("reverse3") -- 3.68
measure("reverse4") -- 4.08
measure("reverse5") -- 3.86
measure("reverse6") -- 5.20
Regards,
Rob Craig
Rapid Deployment Software
http://members.aol.com/FilesEu/
7. Re: Reverse() was: Win32Lib Update
- Posted by Daniel Berstein <daber at PAIR.COM>
Nov 28, 1998
-
Last edited Nov 29, 1998
>I'm no speed demon, but I belive this routine is fairly fast and most
>important... it's generic and flexible.
Well.... after Rob's post I realized that it ain't "fairly fast"... ;) At
least
compared to the other 6 routines posted.
But I still like the "idea" of:
1.- Iterate n/2 times
2.- Don't create a new sequence. What if the sequence is very large?
Memory swaping time would be significant?
Regards,
Daniel Berstein
daber at pair.com
8. Re: Reverse() was: Win32Lib Update
Daniel Berstein wrote:
>But I still like the "idea" of:
>1.- Iterate n/2 times
that has promise... need better implementation that doesn't
require any calculations *within* the loop (which is the other
reason reverse#2 is the fastest: i only do a *single* "inc()"
with the next best doing a subtraction AND an inc() within
the loop, requiring TWICE as many clock ticks.
>2.- Don't create a new sequence.
>What if the sequence is very large?
>Memory swaping time would be significant?
actually, repeat() is extremely fast, likely nothing more than:
function repeat(object what, integer howmuch)
pointertype pntr, where
pntr = alloc(howmuch + GLOBALVARSEQOVERHEAD)
where= pntr + GLOBALVARSEQOVERHEAD
memset(where, what, howmuch)
--return pointer
--return where --dunno which you return...
end function
so the very large sequence issue is not a factor.
we can then address the memory swapping time by simply saying
what was in the comments in my first post of reverse2(), namely:
we are only swapping pointers. *fast*
okay.....
i thought of another way, that is 'approaching assembly'
and, at this point, i'm rather sure this is bad code...
it's presented as a *concept* or as *pseudocode* and
if someone can actually take this and make it work,
i'd be happy to share credit :)
this may work real well for single dim sequences...
ie: strings.
it could be *the* speed demon for strings, i think...
can't use memcopy/memset that i can see, as we cannot
"reverse" the order of their element grabbing, so that's out.
at this point, the only reason it "won't work" is that
we aren't returning a *sequence* but a pointer...
but then, what is the *actual* definition of a sequence after all...
likely a *pointer* to a block of data, and that data is either a
byte(s), or a pointer(s) to another block(s) of data at an
element's index for atoms and other sequences occupying that
element, along with a few bytes for overhead describing start
and end memory addresses...
so, how do i retrieve the overhead?
if i had the overhead, we could, in theory, recreate
a "sequence pointer" by prepend/appending the overhead
to the pointer variable in the example below...
if Rob is planning to use the #2 algorithm for reverse,
i would think an examination of this methodology
would be in order first. I'm not sure anyone but
Rob, with his intimate knowledge of "sequence" as
defined in ex(w).exe, could pull this off.
Pete, of course, might, for PEU, be able to as well...
and i'm not insulting anyone's intelligence with that
last paragraph, nor am i intending to do so, nor am
i intending to ruffle any feathers. please, don't
take what i said wrong...
i would really like to see someone make this algorithm
work, at least for strings, to see it's benchmrk
against the fastest algorithm to date.
code follows.
take care all--Hawké
-----reverse function presented in Rob's Measure() format:
-----Hawké, tweak to reverse2
-----begin pseudocode of non-functional function
function reverse7( sequence data )
object old
integer len
atom pointer
len = length(data)
pointer = alloc(len) -- + GLOB_VAR_SEQ_OVERHEAD??
--if not alloc() then blahblahblah end if
for toindex = 1 to len do
old = peek( data + len, 1 ) -- +/- GLOB_VAR_SEQ_OVERHEAD??
poke( pointer + toindex, old )
len = len - 1
end for
----ummm what do we do about the return???
----return pointer???? NOT! it's not a sequence...
end function
-----------end broken function
9. Re: Reverse() was: Win32Lib Update
I tweaked mine a bit to eliminate a subtraction.
It now seems to be a tad faster than Hawke's, but they're
close enough that I decided to try various lengths
of sequence.
function reverse5(sequence s) -- Rob Craig
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
length reverse2 (Hawke) reverse5 (Rob)
0 0.33 0.25
1 0.43 0.25
2 0.50 0.48
5 0.65 0.60
10 0.84 0.85
100 5.01 4.55
1000 62.33 48.19
10000 830.77 528.14
Regards,
Rob Craig
Rapid Deployment Software
http://members.aol.com/FilesEu/
10. Re: Reverse() was: Win32Lib Update
Rob,
Can you test my reverse function out and compare its speed to yours and
hawkey's?
Thanks
Albert
11. Re: Reverse() was: Win32Lib Update
Albert Brauneis writes:
> Can you test my reverse function out and compare its speed to
> yours and hawkey's?
Your inner loop is:
back = back & rev[junk]
This is wrong. What if rev[junk] is a sequence?
You should have said:
back = append(back, rev[junk])
which is the way you originally had it. append() will be
just as fast as &.
Looping with append() will be similar to Cuny's reverse(),
which is one of the slowest.
Timing code is not rocket science. Just use:
atom t
t = time()
for i = 1 to 10000 do
-- call your routine here
end for
? time() - t
Regards,
Rob Craig
Rapid Deployment Software
http://members.aol.com/FilesEu/
12. Re: Reverse() was: Win32Lib Update
>>2.- Don't create a new sequence.
>>What if the sequence is very large?
>>Memory swaping time would be significant?
>actually, repeat() is extremely fast, likely nothing more than:
>
>function repeat(object what, integer howmuch)
>pointertype pntr, where
> pntr = alloc(howmuch + GLOBALVARSEQOVERHEAD)
> where= pntr + GLOBALVARSEQOVERHEAD
> memset(where, what, howmuch)
> --return pointer
> --return where --dunno which you return...
>end function
>
>so the very large sequence issue is not a factor.
That's not the point. The point is that if the sequence is very large, we
can get off physical memory. Disk read/write is far slower than
RAM. In such a situation would it be faster to use a slower algorithm,
but that doesn't create a new sequence?
Regards,
Daniel Berstein
daber at pair.com
13. Re: Reverse() was: Win32Lib Update
>I tweaked mine a bit to eliminate a subtraction.
>It now seems to be a tad faster than Hawke's, but they're
>close enough that I decided to try various lengths
>of sequence.
>length reverse2 (Hawke) reverse5 (Rob)
>0 0.33 0.25
>1 0.43 0.25
>2 0.50 0.48
>5 0.65 0.60
>10 0.84 0.85
>100 5.01 4.55
>1000 62.33 48.19
>10000 830.77 528.14
Mmmm... my machine says other thing. I also created another reverse
routine, it's between your's and Hawke'. I suppose it's slower than
Hawke''s routine because substraction is slower than addtion
(complement-2 computed, then addition?). Does having a hard
typed constant as end value of a loop increase performance?
function reverse9(sequence s)
integer n, m, q, k
sequence r
n = length(s)
m = floor(n/2)
r = repeat(0,n)
q = n+1
for i = m to n do
k = q-i
r[k] = s[i]
r[i] = s[k]
end for
return r
end function
Using the benchmark posted earlier (64 charcters sequence with
100000 iterations):
reverse2 reverse5 reverse9
(Hawke) (Rob) (Daniel)
1.21 sec. 1.69 sec. 1.39 sec.
The fastest (read: unbeatable) reverse function will be one that iterates
n/2 times, and do not make any substraccion inside the loop.
My machine is a Celeron 300, with *no* cache... I guess that gives pure
algorithmic results?
I'm having fun with this thread! Can we expand it to a recursive version
too...
Regards,
Daniel Berstein
daber at pair.com
14. Re: Reverse() was: Win32Lib Update
>This raises a couple of issues:
> 1. I should probably not make it an error (just a warning) to override
> a global symbol with a local symbol. The local should
> take precedence within the file it is declared in.
> I'm not sure if I'll do it for this release. It involves changes
> to compile-time symbol lookup, run-time symbol lookup
> (trace and routine_id) as well as the bind.ex program.
> It would alleviate some of the namespace conflicts.
Ive mentioned this before, a warning might be in place, but you should
always be able to overwrite a global identifer with a local identifer. I
only think you should see a warning when you overwrite a global identifer.
> 2. Which reverse() is the fastest? I was planning to add a
> Euphoria-coded reverse() to misc.e. A few weeks ago
> I coded reverse5() below, but it looks like reverse2() (Hawke)
> is the fastest, so I'll use his unless someone comes up
> with something even faster.
Good, it sounds like we're going to see some general purpose routines, and
maybe containing a boolean type. Ive had many conflicts with them that I
decided to add them to the beginning of every file *locally* .. if they
would in an standard Euphoria file, one could trust the convention.
Its just:
global constant
TRUE = 1,
FALSE = 0,
NONE = -1
global type boolean (object x)
if integer (x) then
return x > -2 and x < 2
else
return FALSE
end if
end type
The none is just a flag value. And could be used with result of find () or
any of the input routines.
Ralf
15. Re: Reverse() was: Win32Lib Update
Daniel wrote:
>I'm having fun with this thread! Can we expand it to a recursive version=
>too...
>Regards,
> Daniel Berstein
So Ralf, it was a good idea of you (as many of your ideas are, btw) --
Slime, slime
Ad
