Are there alternative data structures than array in PHP, where I can benefit from different index techniques?
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)?
Source: Tips4all
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.
ReplyDeleteHowever, 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.
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.
ReplyDeleteA 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.
You also have the chdb (constant hash database) extension - which is perfect for this.
ReplyDelete