PHP Most efficient way to find a number in a list

Question

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.

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
– Sam, Commented Apr 9, 2014 at 15:42
There is an interesting Diskussion here: stackoverflow.com/questions/6436577/… — Florian Bauer
– Florian Bauer, Commented Apr 9, 2014 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
– Duane, Commented Apr 9, 2014 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
– Duane, Commented Apr 9, 2014 at 15:45

AbraCadaver · Accepted Answer · 2014-04-09 15:58:04Z

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)

answered Apr 9, 2014 at 15:58

AbraCadaver

79.2k7 gold badges75 silver badges91 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

yossi · Accepted Answer · 2014-04-09 16:05:05Z

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.

edited Apr 9, 2014 at 16:05

answered Apr 9, 2014 at 15:47

yossi

3,1748 gold badges51 silver badges70 bronze badges

Comments

Gwenc37 · Accepted Answer · 2014-04-09 15:57:06Z

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

edited Apr 9, 2014 at 15:57

answered Apr 9, 2014 at 15:43

Gwenc37

2,0467 gold badges19 silver badges22 bronze badges

Collectives™ on Stack Overflow

PHP Most efficient way to find a number in a list

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related