By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,035 Members | 1,543 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,035 IT Pros & Developers. It's quick & easy.

how are php arrays indexed?

P: n/a
Hi everyone,

I'm wondering if anyone knows whether PHP does some indexing behind
the scenes to make array searches faster.

What I have is an array of around 100 000 elements, and I have a list
of 1000 given element which I need to see whether they contained in
the array. This means 1000 searches on an array of size 100 000. I'm
hoping that PHP indexes it's keys using a binary tree or
something.. :)

Thanks

Taras

May 16 '07 #1
Share this Question
Share on Google+
4 Replies


P: n/a
On 16.05.2007 13:01 Taras_96 wrote:
Hi everyone,

I'm wondering if anyone knows whether PHP does some indexing behind
the scenes to make array searches faster.

What I have is an array of around 100 000 elements, and I have a list
of 1000 given element which I need to see whether they contained in
the array. This means 1000 searches on an array of size 100 000. I'm
hoping that PHP indexes it's keys using a binary tree or
something.. :)

Thanks

Taras
php uses hash function to speed up access to array elements, namely
Bernstein's function, also known as "times 33"

--
gosha bine

extended php parser ~ http://code.google.com/p/pihipi
blok ~ http://www.tagarga.com/blok
May 16 '07 #2

P: n/a
Taras_96 wrote:
Hi everyone,

I'm wondering if anyone knows whether PHP does some indexing behind
the scenes to make array searches faster.

What I have is an array of around 100 000 elements, and I have a list
of 1000 given element which I need to see whether they contained in
the array. This means 1000 searches on an array of size 100 000. I'm
hoping that PHP indexes it's keys using a binary tree or
something.. :)
Hi,

PHP used hashing.
I understand it is all very fast, but it was many years ago I learned the
logic behind it, so I forgot all about the linked lists and stuff like
that, and cannot be of help there.

But looking up 1000 values inside 100.000 can easily be done by using
specialized array functions, like:
array_diff()
and
array_intersects()

Look them up at www.php.net.

You can bet the alghoritm used behind the scenes is optimized C-code, and
probably unbeatable by your own routines.

I would give them a shot first. If still too slow, ask again. :-)

Regards,
Erwin Moller
>
Thanks

Taras
May 16 '07 #3

P: n/a
At Wed, 16 May 2007 04:01:37 -0700, Taras_96 let his monkeys type:
Hi everyone,

I'm wondering if anyone knows whether PHP does some indexing behind
the scenes to make array searches faster.

What I have is an array of around 100 000 elements, and I have a list
of 1000 given element which I need to see whether they contained in
the array. This means 1000 searches on an array of size 100 000. I'm
hoping that PHP indexes it's keys using a binary tree or
something.. :)

Thanks

Taras
Just gave your example a test run with two arrays full of random values
using array_intersect. On my localhost it takes about 2.45 seconds, so
you have an idea of the order of magnitude.

$myarray = array();
for ($i=0;$i<100000;$i++) {
$myarray[]=mt_rand(0,1000000);
}
$mytestarray = array();
for ($i=0;$i<1000;$i++) {
$mytestarray[]=mt_rand(0,10000);
}

$start = microtime(true);
$result=array_intersect($myarray,$mytestarray);
$stop = microtime(true);
echo $stop-$start; // avg 2.45 secs on P4-3200MHz, PHP sapi/Apache

The returned array still has the keys of the first array's matching
locations. Whether you get a large intersection or not doesn't seem to be
of great influence.

How much memory do you have available to your PHP scripts? If I make the
original array 150.000 elements 16Mb doesn't suffice anymore in above
example. If your data is more complex than my ints, this might become an
issue.

Rgds
Sh.
May 16 '07 #4

P: n/a
On May 16, 1:01 pm, Taras_96 <taras...@gmail.comwrote:
Hi everyone,

I'm wondering if anyone knows whether PHP does some indexing behind
the scenes to make array searches faster.

What I have is an array of around 100 000 elements, and I have a list
of 1000 given element which I need to see whether they contained in
the array. This means 1000 searches on an array of size 100 000. I'm
hoping that PHP indexes it's keys using a binary tree or
something.. :)

Thanks

Taras
As others have pointed out, arrays in PHP are hash tables. To search
quickly, you'd want to take advantage of that. For example, if you're
writing a spell-checker, you wouldn't want to store the word list like
this:

array("a", "able", "above", ...)

but rather like this:

array("a" =1, "able" =1, "above" =1);

then check for existence of a word by accessing the array using the
word as the key.

May 16 '07 #5

This discussion thread is closed

Replies have been disabled for this discussion.