1

I have a list of 300 numbers, they are not ordered. I would like to find the most efficient way to determine if a number is in that list.

The simple answer is in_array(). This of course has a Big O of O(n).

But since I have complete control over this list, I believed I can make it faster.

So I made the list an associative array where key is the number I am looking for which an isset() will yield me O(1). 

$myArray = array('434342'=>true, '345235'=>true, '562211'=>true, '3333245'=>true, '99087782'=>true);

Is this the best way? Since the array size is small the hit of O(n) where n=300 its not worth the extra effort.

Gwenc37
  • 2,064
  • 7
  • 18
  • 22
Duane
  • 4,460
  • 1
  • 25
  • 27
  • does the array have only numbers as keys? – Guns Apr 09 '14 at 15:38
  • 1
    I have to assume that using an associate array and `isset()` is not noticeably more efficient than just using a numerical array and `in_array()`. It definitely, in my opinion, is not worth the decrease of legibility to another programmer (I would scratch my head if I saw an array like the one in your example). If you really want to know, benchmark it. – Sam Apr 09 '14 at 15:42
  • 1
    There is an interesting Diskussion here: http://stackoverflow.com/questions/6436577/php-in-array-and-fast-searches-by-the-end-in-arrays – Florian Bauer Apr 09 '14 at 15:43
  • @Guns The numbers can be anything I want it to be, so if you have a better data structure I'm open to it. – Duane Apr 09 '14 at 15:44
  • @Sam Readability also is a concern of mine, so your point is very valid, so that may be the right answer. – Duane Apr 09 '14 at 15:45

3 Answers3

4

300 array elements:

in_array()    
0.00000000000000000000 seconds    
bool(true)

isset()    
0.00000000000000000000 seconds    
bool(true)

500,000 array elements:

in_array()    
0.00500106811523437500 seconds    
bool(true)

isset()    
0.00000000000000000000 seconds    
bool(true)
AbraCadaver
  • 78,200
  • 7
  • 66
  • 87
3

As long as you have a full control over the list, your way is the most efficient.

A small change: instead of using associative array, use a simple array, numeric based.
The isset() will work as well, and won't need to compare strings.

ANYWAY, it is the most efficient way, but in this kind of data size - it is probably a waste of time.

yossi
  • 3,090
  • 7
  • 45
  • 65
0

If your array is not sorted, you can't do better than O(n) on average

It can be proved by some statistic formula, using the equiprobability of finding a specific element in an unstructured (unsorted) array

Some algorithms are faster in some cases, if the array have a particular structure. Maybe it will help us if we have more details about this array

Gwenc37
  • 2,064
  • 7
  • 18
  • 22