• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 459
  • Last Modified:

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

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?
0
Slimshaneey
Asked:
Slimshaneey
3 Solutions
 
gr8gonzoConsultantCommented:
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).
0
 
zappafan2k2Commented:
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.
0
 
Ray PaseurCommented:
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.
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now