Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:29388 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 63903 invoked by uid 1010); 10 May 2007 14:41:26 -0000 Delivered-To: ezmlm-scan-internals@lists.php.net Delivered-To: ezmlm-internals@lists.php.net Received: (qmail 63885 invoked from network); 10 May 2007 14:41:26 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 10 May 2007 14:41:26 -0000 Authentication-Results: pb1.pair.com smtp.mail=maurice@phorum.org; spf=fail; sender-id=fail Authentication-Results: pb1.pair.com header.from=maurice@phorum.org; sender-id=fail Received-SPF: fail (pb1.pair.com: domain phorum.org does not designate 217.149.192.18 as permitted sender) X-PHP-List-Original-Sender: maurice@phorum.org X-Host-Fingerprint: 217.149.192.18 smtp20.nijmegen.internl.net Solaris 10 (beta) Received: from [217.149.192.18] ([217.149.192.18:64474] helo=smtp20.nijmegen.internl.net) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id 42/A9-20961-21F23464 for ; Thu, 10 May 2007 10:41:25 -0400 Received: from [192.168.0.204] by smtp20.nijmegen.internl.net via waalbrug.nijmegen.internl.net [217.149.192.5] with ESMTP id l4AEfFCh010228 (8.13.8/2.04); Thu, 10 May 2007 16:41:16 +0200 (CEST) Message-ID: <46432F0B.8080506@phorum.org> Date: Thu, 10 May 2007 16:41:15 +0200 Reply-To: maurice@phorum.org Organization: Phorum.org User-Agent: Thunderbird 1.5.0.10 (X11/20070403) MIME-Version: 1.0 To: Derick Rethans CC: Michael Walter , RQuadling@googlemail.com, Brian Moon , internals@lists.php.net References: <4641D92C.4050208@dealnews.com> <10845a340705090743v6aba7896y45b9f7d60a4e77ba@mail.gmail.com> <4641E3DD.8040807@phorum.org> <877e9a170705090913i320359cag81b0a3bf203e2c86@mail.gmail.com> <464202D9.8080509@phorum.org> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [PHP-DEV] Tree sort in C From: maurice@phorum.org (Maurice Makaay) Hi, > That is very peculiar... it should never be slower than an > implementation in PHP - unless your algorithm isn't optimal. > The timing for large numbers of nodes got slower due to a linear lookup (as explained in a previous message too). I implemented a hash table lookup as a replacement. This still does not use a lot of memory and the speed does no longer decrease at large quantities of nodes. FYI, here are some benchmarks against the multisort routine: 10 nodes extension 8.39233398438E-05 / 1316 multisort 0.0001380443573 / 3808 100 nodes extension 0.00014591217041 / 10416 multisort 0.000678062438965 / 32160 1000 nodes extension 0.000765800476074 / 79868 multisort 0.00885391235352 / 298844 5000 nodes extension 0.00524711608887 / 284572 multisort 0.110008001328 / 1596844 10000 nodes extension 0.0113878250122 / 537368 multisort 0.136567831039 / 3252232 20000 nodes extension 0.0704438686371 / 1042796 multisort 0.370564937592 / 6567656 With kind regards, Maurice Makaay Phorum.org