Are there alternative data structures than array in PHP, where I can benefit from different index techniques?

Question

Lately I had an issue with an array that contained some hundred thousands of values and the only thing I wanted to do was to check whether a value was already present. In my case this were IPs from a webserver log. So basically something like:

in_array(ip2long(ip),$myarray) did the job

However the lookup time increased dramatically and 10k of lookups took around 17 seconds or so.

So in this case I didn't care whether I had duplicates or not, I just needed to check for existence. So I could store the IPs in the index like this:

isset($myarray[ip2long($ip)])

And boom, lookup times went down from 17 seconds (and more) to a static time of 0.8 seconds for 10k lookups. As a value for the array entry I just used int 1.

I think the array index is probably based on some b-tree which should have log(n) lookup time and the index on a hashmap.

In my case using the index worked fine, but are there any data structures where I can use hashmaps as a value index, where multiple values may also occour (i realize that this makes only sense if do not have too many duplicates and I cannot use range/search requests efficiently, which is the primary benefit of tree structures)?

Mark Baker · Accepted Answer · 2012-01-21 16:21:11Z

8

There are a whole range of alternatives datastructures beyond simple arrays in the SPL library bundled with PHP, including linked lists, stacks, heaps, queues, etc.

However, I suspect you could make your logic a whole lot more efficient if you flipped your array, allowing you to do a lookup on the key (using the array_key_exists() function) rather than search for the value. The array index is a hash, rather than a btree, making for very fast direct access via the key.

However, if you're working with 10k entries in an array, you'd probably be better taking advantage of a database, where you can define your own indexes.

edited Jan 21, 2012 at 16:21

answered Jan 21, 2012 at 16:15

Mark Baker

213k34 gold badges354 silver badges390 bronze badges

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

3 Comments

Smamatti Over a year ago

Sometimes good solutions are right in front of you and you just think too complicated. -- Nicely done.

Alix Axel Over a year ago

He flipped it from what I understand.

BurninLeo Over a year ago

Using isset($a[$key]) is much (!) faster than array_key_exists($key, $a), because isset is a structure and array_key_exists() is a function.

Alix Axel · Accepted Answer · 2012-01-21 16:36:56Z

2

You also have the chdb (constant hash database) extension - which is perfect for this.

answered Jan 21, 2012 at 16:36

Alix Axel

155k100 gold badges406 silver badges509 bronze badges

Comments

Smamatti · Accepted Answer · 2012-01-21 16:06:07Z

1

Arrays have an sequential order and it's quick to access certain elements, because you don't need to traverse a tree or work through a sequential list structure.

A set is of course faster here, because you only check unique elements and not all elements (in the array).

Tree's are fine for in example sorted structures. You could implement a tree with IPs sorted by their ranges, then you could decide faster if this IP exist or not. I'm not sure if PHP provides such customised tree structures. I guess you'll need to implement this yourself, but this will take about half an hour.

You'll find sample codes on the web for such tree structures.

answered Jan 21, 2012 at 16:06

Smamatti

3,9313 gold badges34 silver badges44 bronze badges

Comments

user652649 · Accepted Answer · 2012-01-21 16:42:53Z

as already answered, you can use brand new classes provided by spl http://www.php.net/spl

BUT apparently they are not as fast as people think. probably they are not implemented as we expect. it is my opinion that splfixedarray, for example, is not a real array, but a hashtable as classic php's arrays

BUT also, you have some alternative solutions

first you can store your result in a database. queries are fast because db indexes may be better optimized than a php datastructure

you can use http://www.php.net/sqlite3 and store results in a temporary database (a file or in memory)

I suggest a temporary file, because you don't have to load all in memory, and in plus you can add each row individually (using http://www.php.net/fgets for example)

HTH!

feel free to correct my English

Collectives™ on Stack Overflow

Are there alternative data structures than array in PHP, where I can benefit from different index techniques?

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related