From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p6DIxFJG022344 for ; Wed, 13 Jul 2011 20:59:15 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjEEAJHqHU7Unwcjimdsb2JhbABTmEiOdRQBAQEKCQ0HEgYhiHzDIIY6BJdgi04 X-IronPort-AV: E=Sophos;i="4.65,526,1304287200"; d="scan'208";a="98501423" Received: from relay.ptn-ipout01.plus.net ([212.159.7.35]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 13 Jul 2011 20:59:10 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AigIAOrpHU5UXebr/2dsb2JhbABTmEiOdXeIfMMahjoEl2CLTg Received: from outmx07.plus.net ([84.93.230.235]) by relay.ptn-ipout01.plus.net with ESMTP; 13 Jul 2011 19:59:09 +0100 Received: from [46.208.70.40] (helo=WinEight) by outmx07.plus.net with esmtp (Exim) id 1Qh4eK-0001aS-S0; Wed, 13 Jul 2011 19:59:09 +0100 From: "Jon Harrop" To: Cc: References: In-Reply-To: Date: Wed, 13 Jul 2011 19:58:33 +0100 Message-ID: <005301cc418e$dde4c2a0$99ae47e0$@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Outlook 14.0 Thread-Index: AQIQikgs4S2Hl0S0SjQSNwKuz0QmN5RiBEgw Content-Language: en-gb Subject: RE: RE: [Caml-list] Priority queues, reloaded Radu Grigore wrote: > Another comparison appears in SGB, file miles_span.w, in the context of > computing minimum spanning trees. It turns out that Fibonacci heaps are not > only a theoretical curiosity! That's interesting. I was under the impression Fibonacci heaps had a really bad constant prefactor. If this is the right file: http://ftp.sunet.se/pub/text-processing/TeX/support/graphbase/miles_span.w Then they say: "We will try out four basic algorithms that have received prominent attention in the literature. Graham and Hell's Algorithm~1 is represented by the |krusk| procedure, which uses Kruskal's algorithm after the edges have been sorted by length with a radix sort. Their Algorithm~2 is represented by the |jar_pr| procedure, which incorporates a priority queue structure that we implement in two ways, either as a simple binary heap or as a Fibonacci heap. And their Algorithm~3 is represented by the |cher_tar_kar| procedure, which implements a method similar to Bor{\accent23u}vka's that was independently discovered by Cheriton and Tarjan and later simplified by Karp and Tarjan. " So they're only comparing binary and Fibonacci heaps (not skew, leftist, pairing, binomial etc). Moreover, do you actually need a heap in the MST algorithm? You cannot add the shortest edge first without traversing all edges so you must consider all edges. I suppose a heap could win out over a sort if the MST only requires a small proportion of all the edges, i.e. finding the 1..k shortest edges, but I'm not sure how valuable that is in practice. Regardless, I'm sure the first step in optimizing such algorithms is to sacrifice purity. :-) Cheers, Jon.