On Mon, 2004-11-15 at 12:09 -0800, Sergio Basurto
Juarez wrote:
First of all thanks for the note, I think I will
use a
Hashing Table as some one suggest here, becuase in
this case seems to be more suitable for the
problem,
why am so worry about speed, is becuase is a web
application in php, and it takes to long with the
binarysearch algorithm, nevertheless I am testing
the
same with Hashing Tables and it suits to what I am
looking in time consuming.
Also I was wondering if there were some magic
equation
that do the trick without hashing tables, but I
think
the time that will take me to find some one is too
much so I will use hashing tables meanwhile.
Thanks again.
The binary search is O(logn) which is quite fast. It
reduces your
problem by half on each iteration (divide and
conquer). The problem is
the sort. You haven't really specified enough about
the problem to
helpful. If you need fast search times then why use
an array? You should
be using some tree structure if you really want
efficient search times.
Obviously a good hash is going to be O(1) depending
on your collision
handling.
In this case I would suggest a different language.
It's not the
algorithm itself but rather the language. Try coding
this part in a
different language. Even Perl will me much faster.
The STL is the way to
go these days. Try using a vector with the STL sort
and find algorithms
and you'll see it's very fast and probably meets the
speeds of a hash in
PHP.
Don't get me wrong, I'm not bashing PHP. It's just
that it wasn't
designed for intense algorithmic purposes. The web
is very flexible and
mixing languages shouldn't be too difficult to do. I
know Python does
extending and embedding.
Don't just look at the algorithm, look at the whole
picture.