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 p6157Vd8016876 for ; Fri, 1 Jul 2011 07:07:31 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqIBAK1VDU5KfVK2kGdsb2JhbAA8AQMSp1UIFAEBAQEJCQ0HFAQhiHujYYwkgkuEMDmIaAIDBoYsBJIwhHaBHIM0glg8g1g X-IronPort-AV: E=Sophos;i="4.65,456,1304287200"; d="scan'208";a="97770368" Received: from mail-wy0-f182.google.com ([74.125.82.182]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 01 Jul 2011 07:06:57 +0200 Received: by wyg24 with SMTP id 24so3593524wyg.27 for ; Thu, 30 Jun 2011 22:06:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=6J9und0mWD4LEqcrWNN+TZbNzol+g/2N1RnAsV2OZgA=; b=WTegeDnzDQ0M8XBY6E3mNvYMgki+w6kqUJDNWkQhBOj4fAGi0gqOHrKF9C8qgmuDdR NuPwa0ItCUZdJRzbVFTlTuA/R4INlZPERTawS8fdVUsSE9xE9xGsEX1ia/ZvP5PRBuvw Nq303uGVhzGtUT7YsYAsH4kJxWrv8NVBKexa0= Received: by 10.216.220.212 with SMTP id o62mr714545wep.75.1309496816039; Thu, 30 Jun 2011 22:06:56 -0700 (PDT) Received: from [192.168.1.187] (106.165.7.93.rev.sfr.net [93.7.165.106]) by mx.google.com with ESMTPS id ej7sm2083928wbb.19.2011.06.30.22.06.54 (version=SSLv3 cipher=OTHER); Thu, 30 Jun 2011 22:06:55 -0700 (PDT) Message-ID: <4E0D55F2.3050800@gmail.com> Date: Fri, 01 Jul 2011 07:06:58 +0200 From: Andrew User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:5.0) Gecko/20110624 Thunderbird/5.0 MIME-Version: 1.0 To: Wojciech Meyer CC: caml-list@inria.fr References: <4E0C5E67.9010606@gmail.com> <4E0C6D2E.8070206@lri.fr> <4E0C77EF.6030408@elehack.net> <4E0C8697.8070805@ens-lyon.org> <4E0CAE39.9000002@gmail.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Caml-list] Priority queues Wojciech Meyer wrote: > Andrew writes: > >> Wojciech Meyer wrote: >>> And if one does not need performance but understanding what's the purpose of the priority queue is, >>> what is the interface, and how it should behave, than implementation as a list is sufficient. Please note >>> it is for exam and major pressure is put on Dijkstra not on implementation or performance (as far as I >>> understood) of the priority queue. (which can be changed later easily) >> >> Not really. This is a practical exam. 3h and a half facing a computer, >> with a set of problems to solve, with huge inputs. Hence the need for >> performance. >> >> Here, Dijkstra's algorithm is only going to be a step in the process >> of solving a more elaborate problem. Not having a priority queue >> readily available means that I am going to have to waste some time >> reimplementing an efficient structure. > > Yes, then you'd need a real priority queue. > > I would suggest using Batteries (some people might disagree and saying > it's an overkill in this case). It all depends on the rules, if you can > use any of code taken from home, or any external libraries for instance, > or you would need to have them written down only on a piece of paper, or > bringing some reference like book is feasible, etc. If it's all about > high level problem solving, then they are ready algorithms for Dijkstra > as well (e.g. excellent graph library: OCamlGraph). > I cannot import any code *at all* :/ >> >> The Set option covers some cases (and it does work in the case of Dijkstra) ; but in other cases it won't work :/ > > Yet it will work for Dijkstra, alternatively you could take some code > out of standard OCaml library (Set, Map) and change it to your needs. > (but I think that Redblack trees are easy enough to implement). > > Regarding your choice, I don't think you will regret OCaml even if it > does not have the priority queue as a part of the standard library :) > Like in the previous post, I also think it has some very nice features > and also some ugly design features of C++ are not present in OCaml. I > use to do a lot of C++ in past, and just feel much better now. (and > features like fast GC, performance, pattern matching and many others > just make programming so pleasant) It's worth investing time in O'Caml > and certainly it's a perfect choice for this type of exam, (and really > for any type of programming, I think). > > Mine two cents, > > Thanks, > Wojciech > >