Re: Search Algorithm

From: Eric Gaumer (gaumerel_at_ecs.fullerton.edu)
Date: 11/15/04

  • Next message: Brian Pack: "Re: why debian" 
    To: debian-user@lists.debian.org
Date: Mon, 15 Nov 2004 14:10:10 -0800

    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. 

    -- 
Eric Gaumer <gaumerel@ecs.fullerton.edu>



    -- 
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org 
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
  • Next message: Brian Pack: "Re: why debian"

    Relevant Pages

    • Re: Search Algorithm
      ... >> same with Hashing Tables and it suits to what I am ... If you need fast search times then why use ... > In this case I would suggest a different language. ... > algorithm itself but rather the language. ...
      (Debian-User)
    • Re: Looking for an algorithm to accomplish the following
      ... Are the entries to be added always in the same position? ... I guess you could use hashing to cut down on the time, ... What language are you using? ... but an algorithm would be a starting point for a software I am ...
      (sci.math)
    • Hashing
      ... particular domain due to inherited capacity to avoid hashing collisions ... would be suitable for authentication (where rare occurances of collisions ... algorithm to avoid collisions within the domain is extremely important. ... '_' characters only), with token length no larger than 32 characters. ...
      (alt.lang.asm)
    • [Full-disclosure] Re: choice-point screw-up and secure hashes
      ... > discover your salting algorithm directly). ... a keyed hashing algorithm would be great. ... encryption won't solve the problem. ... help protect the data in transit, it would help protect the data from ...
      (Full-Disclosure)
    • Re: Search Algorithm
      ... >> know there is the binarysearch algorithm, ... And a simple algorithm, too. ... same with Hashing Tables and it suits to what I am ... The all-new My Yahoo! ...
      (Debian-User)