473,320 Members | 1,861 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

how are php arrays indexed?

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
4 1438
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
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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Mark | last post by:
Does Smarty support assigning multidimensional arrays? I've tried to get it working, but just can't get it. can someone help me? this is what I have in my php file: $side_bar = array('link'...
11
by: - Steve - | last post by:
For a school assignment I need to write a class to work with the following code. The IntArray b(-3, 6) basically means that I need to produce an array of integer values that has an index going...
3
by: ABC | last post by:
I am not a javascript guru or anything so I was wondering if someone could tell me what the code below is doing. Is it creating a multidimensional array? Would it be better to create an object? ...
21
by: Matteo Settenvini | last post by:
Ok, I'm quite a newbie, so this question may appear silly. I'm using g++ 3.3.x. I had been taught that an array isn't a lot different from a pointer (in fact you can use the pointer arithmetics to...
34
by: Christopher Benson-Manica | last post by:
If an array is sparse, say something like var foo=; foo=4; foo='baz'; foo='moo'; is there a way to iterate through the entire array? --
4
by: meltedown | last post by:
Theres something very basic about javascript arrays I'm missing. The value of unit.value is 17.00 and value of the qty.value is 5 and I put these values into an array: myarray.value]=qty.value;...
3
by: Mike Scott | last post by:
What is the best way to index an array by an enum. Pascal has a nice feature in that arrays can be indexed by an enum, for example type ButtonType = ( Left, Middle, Right ) ; var buttons :...
1
by: Joel Whitehouse | last post by:
Is there any way I can get the effects of declaring objects using WithEvents while also having indexed addressing? I'm designing a control that has several buttons, the functions of which vary...
10
by: Peter Duniho | last post by:
This is kind of a question about C# and kind of one about the framework. Hopefully, there's an answer in there somewhere. :) I'm curious about the status of 32-bit vs 64-bit in C# and the...
6
by: Emiurgo | last post by:
Hi there to everyone! I've got a problem which may be interesting to some of you, and I'd be very grateful if there is someone who can give me some advice (or maybe redirect me to some other place)....
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.