OpenEuphoria

range_find()

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

Sorry for the number of posts.

I've made it faster again :P
Pretty sure this is the last one. Don't know why I didn't see it 
already...
Clocked at 1.15 for 100 elements

here it is:
function range_find(object x, sequence s, integer pos1, integer pos2)
   for i = pos1 to pos2 do
      if equal(x,s[i]) then return i end if
   end for
   return 0
end function

Chris

bensler at mail.com wrote:
> I just made range_find() even faster.
> They even out at 100 elements now, clocking at 1.27 secs. More than 100 
> elements, and range_find() has the benefit.
> 
> Here it is:
> 
> function range_find(object x, sequence s, integer pos1, integer pos2)
>  integer pos
>    pos = pos1
>    while pos <= pos2 do
>       if equal(x,s[pos]) then exit end if
>       pos +=1
>    end while
>    if pos > pos2 then return 0
>    elsif pos = pos1 then return 0
>    else return pos
>    end if
> end function
> 
> Chris
> 
> bensler at mail.com wrote:
> > I should point out, that using sequences of length < 200, range_find() 
> > is drastically slower. Using 200 elements or less, range_find() clocks 
> > in at 2 seconds. It doesn't seem to drop less than 2 secs.
> > fastest time I got for find() was 0.68 using 10 elements.
> > 
> > Chris
> > 
> > bensler at mail.com wrote:
> > > 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()
<snip>