From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p5UHBR0r019123
	for <caml-list@sympa-roc.inria.fr>; Thu, 30 Jun 2011 19:11:27 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AmcDANKsDE5KfVI0imdsb2JhbAA8AQMSmGaOaAgUAQEBCgkNBxIGIYh6omGMIIJLhDs5iGgCAwaGKwSSL4R2gRyGCjyDWA
X-IronPort-AV: E=Sophos;i="4.65,453,1304287200"; 
   d="scan'208";a="112275338"
Received: from mail-ww0-f52.google.com ([74.125.82.52])
  by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 30 Jun 2011 19:11:22 +0200
Received: by wwf10 with SMTP id 10so2977906wwf.9
        for <caml-list@inria.fr>; Thu, 30 Jun 2011 10:11:21 -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:subject:references
         :in-reply-to:content-type:content-transfer-encoding;
        bh=wMfWLYveMJBVCODiGt42hsXJcni8DABqooyoZKw0ymI=;
        b=pqXSvhHVANSUsspOy18TaU6nSl+hsINfKDdBps0d8873jOCyXG7RjI4EkVwmoYA2kX
         iSeLxQdJruJ3ZEu1C3hqnR2xSplN7feRcEhBzHayr99qheowmR0Oq9oLsaz7D/Dy6aq8
         9F2abiXnkPZojYd7n16Fcdr00ldISR+ft6GWQ=
Received: by 10.227.2.199 with SMTP id 7mr2064656wbk.88.1309453881831;
        Thu, 30 Jun 2011 10:11:21 -0700 (PDT)
Received: from [192.168.1.186] (106.165.7.93.rev.sfr.net [93.7.165.106])
        by mx.google.com with ESMTPS id et5sm1768103wbb.50.2011.06.30.10.11.20
        (version=SSLv3 cipher=OTHER);
        Thu, 30 Jun 2011 10:11:21 -0700 (PDT)
Message-ID: <4E0CAE39.9000002@gmail.com>
Date: Thu, 30 Jun 2011 19:11:21 +0200
From: Andrew <newsgroups.fr@gmail.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:5.0) Gecko/20110624 Thunderbird/5.0
MIME-Version: 1.0
To: caml-list@inria.fr
References: <4E0C5E67.9010606@gmail.com> <4E0C6D2E.8070206@lri.fr> <4E0C77EF.6030408@elehack.net> <BANLkTin0Z9psTfYm8aDqqXFX3q-6jL_Mmw@mail.gmail.com> <4E0C8697.8070805@ens-lyon.org> <BANLkTimGSE1zQT-kEs835axyFFad_0Tb=w@mail.gmail.com>
In-Reply-To: <BANLkTimGSE1zQT-kEs835axyFFad_0Tb=w@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [Caml-list] Priority queues

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.

The Set option covers some cases (and it does work in the case of Dijkstra) ; but in other cases it won't work :/