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.
as already answered, you can use brand new classes provided by spl http://www.php.net/spl
ReplyDeleteBUT 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
You also have the chdb (constant hash database) extension - which is perfect for this.
ReplyDelete