A common issue in lots of applications is tree sorting with unlimited
depth. Phorum has used a recursive function since 1999 to solve this
problem. However, at MySQL Conference this year, we finally wrote a non
recursive function for it and acheived both memory and time savings on
very large data sets. I always knew it could be done, I had just never
stopped and worked it out. Most examples I found involved a left/right
model that our data does not use. The left/right model involves
altering rows when new rows are inserted into the tree. That is not
attractive. Phorum uses just a parent_id field to track child members.
We would like to take this to another level and make a PHP internal
funciton to do the work. In fact, since MySQL Conference, one of team
members has written the function as a PHP extension. My questions is,
if we made a generic tree sorting function, could this be a function
that we could get considered for addition to the other array sorting
functions. I have probably ported the Phorum PHP based for tree sorting
over to 100 different other applications for sorting trees in PHP. It
would be very nice to finally have an internal function for it.
Speed is not our main benefit, although there is a noticable speed
boost. In addition to sorting the function, each node would be assigned
a depth value (optionally named by a function parameter if needed).
This is where the biggest memory savings have been found for us. On
large data sets (2000 members) in PHP, we have found that altering the
input array would cause copy of the whole array, blowing up the memory
usage of the script to as much as 10x. Doing this in C helps to remove
that problem.
Basically, an array would look like:
$array = array(
1 => array(
"id" => 1,
"parent" => 0,
"name" => "item 1"
),
2 => array(
"id" => 2,
"parent" => 0,
"name" => "item 2"
),
3 =>array(
"id" => 3,
"parent" => 1,
"name" => "item 1"
),
);
The function call would look like:
array_treesort($array, "id", "parent");
The returned array would look like:
$array = array(
1 => array(
"id" => 1,
"parent" => 0,
"name" => "item 1",
"depth" => 0
),
3 =>array(
"id" => 3,
"parent" => 1,
"name" => "item 1",
"depth" => 1
),
2 => array(
"id" => 2,
"parent" => 0,
"name" => "item 2",
"depth" => 0
),
);
Its a little funky to have a function take names of fields like this,
but this is the only way we could think of to make this work for people
without them having to change their data structure.
You can see our current work at
http://www.phorum.org/tracfcgi/browser/phorum5/trunk/extension_src That
code has been written specifically for Phorum to replace our existing
PHP function. It does more than the PHP internal function would do.
But, the extra parts are not the things that we were trying to overcome.
They are just gravy.
--
Brian Moon
Senior Developer
------------------------------
http://dealnews.com/
It's good to be cheap =)
--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
