Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:29375
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain googlemail.com designates 64.233.184.232 as permitted sender)
DomainKey-Status: bad
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=googlemail.com; s=beta;
        h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=m+kOcPtoR2wL3RKFcY8Fq4sCAY04OsuwoxEMWPh2gSLi1H6NmQSxzDm3p4Qq2RPBZRYFJsB6Mm6RMPhcL8HXftA7s7+tE+CzXeChkx5bJAXIpDCXkvTkc2hpePzWyFmlz8v3qtFzOmqaZJxLeV3GeK3kks2ZUhyskxcTXlsXPk4=
Message-ID: <10845a340705090743v6aba7896y45b9f7d60a4e77ba@mail.gmail.com>
Date: Wed, 9 May 2007 15:43:21 +0100
Reply-To: RQuadling@GoogleMail.com
To: "Brian Moon" <brianm@dealnews.com>
Cc: internals@lists.php.net, maurice@phorum.org
In-Reply-To: <4641D92C.4050208@dealnews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <4641D92C.4050208@dealnews.com>
Subject: Re: [PHP-DEV] Tree sort in C
From: rquadling@googlemail.com ("Richard Quadling")

On 09/05/07, Brian Moon <brianm@dealnews.com> wrote:
> 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
>
>

Take a look at http://www.php.net/manual/en/function.array-multisort.php#68689
/ http://rquadling.php1h.com/array_multisort_column.php

Richard.



-- 
-----
Richard Quadling
Zend Certified Engineer : http://zend.com/zce.php?c=ZEND002498&r=213474731
"Standing on the shoulders of some very clever giants!"