OpenEuphoria

RE: Sequence Slicing (Was RE: Tough ciphers?)

• Posted by bensler at mail.com Mar 15, 2002
• 439 views

If I did my test correctly, and you're repetitively searching slices of 
a sequence, yes.

Because of your question, I did a bit of further testing. I've 
discovered, the turning point between the benefit of find() vs 
range_find() is somewhere between 200 to 300 elements.

At 300 elements, iterated 1000000/fl times, range_find() beats find() 
with 2.09 vs 2.58 consistently. The higher the number of elements, the 
larger the difference.

I haven't tested with nested sequences, or sequences with varied data.

Here are both complete tests:
<CONTROL TEST>
constant fl=300
integer fn
fn = open("words.txt","rb")

sequence temp     temp = repeat(0,fl)

for i = 1 to fl do
   temp[i] = getc(fn)
end for

close(fn)

atom t   t=time()
integer count  count = 0
integer f,found
for i = 1 to 10000000/fl do
f=1
found=find('\n',temp)
while found != 0 do
   count +=1
   f +=found
   found = find('\n',temp[f..length(temp)])
end while
end for

? f
? count
? time()-t
while get_key()=-1 do end while
<END CONTROL TEST>

<range_find() TEST>
constant fl = 300
integer fn
fn = open("words.txt","rb")

sequence temp     temp = repeat(0,fl)

for i = 1 to fl do
   temp[i] = getc(fn)
end for

close(fn)

function range_find(object x, sequence s, integer pos1, integer pos2)
 atom found
   found = 0
   while not found and pos1 <= pos2 do
      found = equal(x,s[pos1]) * pos1
      pos1 +=1
   end while
   return found
end function

atom t   t=time()
integer count  count = 0
integer f,found
for i =1 to 10000000/fl do
f=0
found=find('\n',temp)
while found != 0 do
   count +=1
   f =found+1
   found = range_find('\n',temp,f,length(temp))
end while
end for

? f
? count
? time()-t
while get_key()=-1 do end while
<END range_find() TEST>

Chris

Rod Jackson wrote:
> ???
> 
> Am I reading this right? Are you saying that this routine
> will actually find elements in a sequence faster than
> taking a slice of the sequence and using find() to search
> the slice?
> 
> Rod Jackson
> 
> 
> bensler at mail.com wrote:
> > This is fast and works on any slice of a sequence. Sanity checks could 
> > be added.
> > 
> > function range_find(object x, sequence s, integer pos1, integer pos2)
> >  atom found
> >    found = 0
> >    while not found and pos1 <= pos2 do
> >       found = equal(x,s[pos1]) * pos1
> >       pos1 +=1
> >    end while
> >    return found
> > end function
> > 
> > This is the test that I used. I wasn't concerned with accuracy, because 
> > the routine beats find() by a long shot.
> > 
> > <TEST>
> <snip>
> > <END TEST>
> > 
> > The control test used:
> > found = find('\n',temp[f..length(temp)]
> > 
> > instead of:
> > found = range_find('\n',temp,f,length(temp))
> 
>