Is searching a huge associative array with binary search faster than accessing via array key ?

Posted on 2012-08-23
Last Modified: 2012-10-08
I'm on the move at the moment and want to settle an argument. Say I have a dictionary loaded into an assoc array. Elements are sorted, and there are a million Items. The dictionary is in the form term = > definition. Would it be quicker to search for a definition by using array($term) to access the key, or doing a binary search on the array? Would it be quicker over single pass or multiple term searches?
Question by:Slimshaneey
    LVL 34

    Accepted Solution

    If you know the key, then accessing the element by key will always be faster than trying to loop over an array. The size doesn't matter - in one case you are iterating through every element in the array, while in another case you are essentially going straight to a single element.

    If you were trying to get to byte 20,000,000 in a 30-megabyte file, you could loop through 20 million bytes, or you could fseek straight to offset 20,000,000. I'll guarantee that fseek is faster. It's a somewhat similar situation with arrays (purists may correctly differ).
    LVL 12

    Assisted Solution

    Off topic question here, but isn't there a better way to do this?  When you're talking about a million key/value pairs, it just strikes me that doing this in PHP is asking for trouble.

    Don't you run out of memory?  How are they being loaded?  Doesn't this kill your system?  Will there ever be the case when this script is run more than once simultaneously?

    Heck, I've had memory issues storing two arrays with 17k values in the past.
    LVL 107

    Assisted Solution

    by:Ray Paseur
    If your programming knows the value of $term, then you would find the definition in $array($term).  In other words, as the problem is defined, there is not any "search" involved.

    Binary search might make sense if the dictionary array was ordered and you did not know the key.

    Where would you get a million term definitions?  There are only about 80,000 English language words in the largest vocabularies.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    IT, Stop Being Called Into Every Meeting

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    Both Easy and Powerful How easy is PHP? (  Very easy.  It has been described as "a programming language even my grandmother can use." How powerful is PHP?  http://en.wikiped…
    These days socially coordinated efforts have turned into a critical requirement for enterprises.
    The viewer will learn how to count occurrences of each item in an array.
    The viewer will learn how to create a basic form using some HTML5 and PHP for later processing. Set up your basic HTML file. Open your form tag and set the method and action attributes.: (CODE) Set up your first few inputs one for the name and …

    737 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now