From mboxrd@z Thu Jan 1 00:00:00 1970 X-Sympa-To: caml-list@inria.fr 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 p5UMpSD9029842 for ; Fri, 1 Jul 2011 00:51:29 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArkBAJH8DE5KfVI0imdsb2JhbAAxCxanVggUAQEBCgkNBxIGIYh4AqJ9jmsBjUcFhjGSM4lFglc8g1c X-IronPort-AV: E=Sophos;i="4.65,455,1304287200"; d="scan'208";a="97760460" Received: from mail-ww0-f52.google.com ([74.125.82.52]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 01 Jul 2011 00:51:23 +0200 Received: by wwf10 with SMTP id 10so3297197wwf.9 for ; Thu, 30 Jun 2011 15:51:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type; bh=9ZvuvRabfA6cp70ox+EpRSa8cDZJ1+LUoZURvUSj3+o=; b=GKP5Ep9og2YLTc2U0Umop9J5ZRU8PHCg1usOf+sUThJhwaBxfLIEgHwIX67oEWvTyg PyAY0NQrKQPSYBlLGc12W5DB8kk3GAiJGtGU+NA1a63sObwwGYN6KNI4mFTmiA/Omn0Y KNJ2cke5aeKSn4YyBig5Xr+q1+gIJHYTOPRJk= Received: by 10.227.162.200 with SMTP id w8mr2267677wbx.114.1309474281462; Thu, 30 Jun 2011 15:51:21 -0700 (PDT) Received: from spec-desktop.danmey.org (cpc1-cmbg12-0-0-cust201.5-4.cable.virginmedia.com [86.9.116.202]) by mx.google.com with ESMTPS id c17sm1944007wbh.29.2011.06.30.15.51.19 (version=TLSv1/SSLv3 cipher=OTHER); Thu, 30 Jun 2011 15:51:20 -0700 (PDT) From: Wojciech Meyer To: Andrew 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> Date: Thu, 30 Jun 2011 23:51:18 +0100 In-Reply-To: <4E0CAE39.9000002@gmail.com> (Andrew's message of "Thu, 30 Jun 2011 19:11:21 +0200") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Validation-by: wojciech.meyer@googlemail.com Subject: Re: [Caml-list] Priority queues 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). > > 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