OpenEuphoria

Re: Euphoria Standard Library

• Posted by Tone Skoda <tone.skoda at siol.net> Jul 23, 2001
• 385 views

I have one function for you:
For searching word (Eu object) in sorted sequence. It's faster that find (),
esspecially with big sequences.
You can put it in cathegory searching, or algorithm.


include sort.e
include misc.e

-- Finds 'find_me' in sorted sequence 's'.
-- Fast searching.
-- Returns index or 0 if not found.
-- Benchmark results:
-- This function is especially fast when there are a lot of words
-- in array 's'. If there are less than about 50 words in 's', then builtin
find() is faster.
-- Length of 's' shouldn't be 0.
global function find_in_sorted (object find_me, sequence s)
 integer cur -- current compared, index
 integer res -- result
 integer upp -- upper bound, index
 integer low -- lower bound, index
 integer dif -- difference

 if compare (find_me, s [1]) = -1 or compare (find_me, s [length (s)]) = 1
then
  return 0
 end if

 low = 0
 upp = length (s) + 1

 while 1 do
  dif = upp - low
  if dif = 1 then -- manually check it
   if compare (find_me, s [low + 1]) = 0 then
    return low + 1
   else
    return 0
   end if
  end if
  cur = low + floor (dif / 2)
  res = compare (find_me, s [cur])
  if res = -1 then -- find_me is less
   upp = cur
  elsif res = 1 then -- find_me is greater
   low = cur
  else -- res = 0
   return cur -- found!
  end if
 end while
 return 0 -- not found
end function








Benchmarks:



Finding words which exist:
find_in_sorted() took 0.110000 seconds.
find() took 1.320000 seconds.
my_find() took 2.750000 seconds.
find_in_sorted() was 12.000000x faster than find().

Finding words which most possibly don't exist
        (generating random words time added):
find_in_sorted() took 0.440000 seconds.
find() took 2.960000 seconds.
my_find() took 5.770000 seconds.
find_in_sorted() was 6.727273x faster than find().
Testing find functions.
Number of words in array: 10000
Word lengths: 10
Iterations: 20

Finding words which exist:
find_in_sorted() took 0.880000 seconds.
find() took 344.710000 seconds.
my_find() took 486.200000 seconds.
find_in_sorted() was 391,715909x faster than find().

Finding words which most possibly don't exist
        (generating random words time added):
find_in_sorted() took 2.360000 seconds.
find() took 706.340000 seconds.
my_find() took *a lot* seconds.
find_in_sorted() was 299,296610x faster than find().
Testing find functions.
Number of words in array: 5000
Word lengths: 10
Iterations: 5

Finding words which exist:
find_in_sorted() took 0.060000 seconds.
find() took 19.380000 seconds.
my_find() took 27.740000 seconds.
find_in_sorted() was 323.000000x faster than find().

Finding words which most possibly don't exist
        (generating random words time added):
find_in_sorted() took 0.220000 seconds.
find() took 43.670000 seconds.
my_find() took 61.900000 seconds.
find_in_sorted() was 198.500000x faster than find().
Testing find functions.
Number of words in array: 20
Word lengths: 10
Iterations: 10000

Finding words which exist:
find_in_sorted() took 0.330000 seconds.
find() took 0.110000 seconds.
my_find() took 0.330000 seconds.
find_in_sorted() was 0.333333x faster than find().

Finding words which most possibly don't exist
        (generating random words time added):
find_in_sorted() took 1.320000 seconds.
find() took 1.260000 seconds.
my_find() took 1.490000 seconds.
find_in_sorted() was 0.954545x faster than find().
Testing find functions.
Number of words in array: 30
Word lengths: 10
Iterations: 10000

Finding words which exist:
find_in_sorted() took 0.550000 seconds.
find() took 0.280000 seconds.
my_find() took 0.600000 seconds.
find_in_sorted() was 0.509091x faster than find().

Finding words which most possibly don't exist
        (generating random words time added):
find_in_sorted() took 2.090000 seconds.
find() took 1.980000 seconds.
my_find() took 2.470000 seconds.
find_in_sorted() was 0.947368x faster than find().