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 p5UHU178020172 for ; Thu, 30 Jun 2011 19:30:01 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AlsCAImxDE7UGyoFkWdsb2JhbABSG4QnlCSOcBQBAQEBCQsLBxQDIoh4Aq5ZkGuFJYEMBI1OiXSLHQ X-IronPort-AV: E=Sophos;i="4.65,453,1304287200"; d="asc'?vcf'?scan'208,217";a="97748476" Received: from smtp5-g21.free.fr ([212.27.42.5]) by mail2-smtp-roc.national.inria.fr with ESMTP; 30 Jun 2011 19:29:55 +0200 Received: from Tocksi.local (unknown [78.240.16.62]) by smtp5-g21.free.fr (Postfix) with ESMTP id 59BEBD480A3 for ; Thu, 30 Jun 2011 19:29:49 +0200 (CEST) Message-ID: <4E0CB288.1080302@univ-savoie.fr> Date: Thu, 30 Jun 2011 19:29:44 +0200 From: Christophe Raffalli User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; fr; rv:1.9.2.18) Gecko/20110616 Thunderbird/3.1.11 MIME-Version: 1.0 To: caml-list@inria.fr References: <4E0C5E67.9010606@gmail.com> <4E0C60A1.7030103@gmail.com> <4E0C6463.2070708@gmail.com> <4E0C6D42.3010102@gmail.com> In-Reply-To: X-Enigmail-Version: 1.1.1 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enig90AB18DDD0361E9742AAF204" X-Validation-by: christophe.raffalli@univ-savoie.fr Subject: Re: [Caml-list] Priority queues This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig90AB18DDD0361E9742AAF204 Content-Type: multipart/mixed; boundary="------------010808050208030506060006" This is a multi-part message in MIME format. --------------010808050208030506060006 Content-Type: multipart/alternative; boundary="------------080900080802020803080101" --------------080900080802020803080101 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Hello, > > > > Yes it does: > > > > http://caml.inria.fr/pub/docs/manual-ocaml/libref/Set.Make.html > > > > Please see min_elt function. > > > > This is not an actual priority queue though: it doesn't allow for > multiple copies of the same element to be added :/ > > > Yes but you could simulate it with a list and map. Or a set of tuple (p, id) where p is the priority and id the process number (=3D arrival time). Then you sort lexicographicaly first by increasing priority and second decreasing id to have FIFO for equal priority. And I think a less than 10 lines O(N ln(N)) re-implemantation or priority queues would give you good result at your competitive exam ! =20 My two cents, Christophe > > Cheers; > Wojciech > --=20 Christophe Raffalli Universite de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tel: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution=20 can check this signature. The public key is stored on www.keyserver.net --------------------------------------------- --------------080900080802020803080101 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Hello,

> Yes it does:
>
> http://caml.inria.fr/pub/docs/manual-ocaml/= libref/Set.Make.html
>
> Please see min_elt function.
>

This is not an actual priority queue though: it doesn't allow for multiple copies of the same element to be added :/

Yes but you could simulate it with a list and map.

Or a set of tuple (p, id) where p is the priority and id the process number (=3D arrival time).
Then you sort lexicographicaly first by increasing priority and second decreasing id to have FIFO for equal priority.

And I think a less than 10 lines O(N ln(N)) re-implemantation or priority queues would
give you good result at your competitive exam !

My two cents,
Christophe

Cheers;
Wojciech

--=20
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution=20
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------

--------------080900080802020803080101-- --------------010808050208030506060006 Content-Type: text/x-vcard; charset=utf-8; name="Christophe_Raffalli.vcf" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="Christophe_Raffalli.vcf" begin:vcard fn:Christophe Raffalli n:Raffalli;Christophe org:LAMA (UMR 5127) email;internet:christophe.raffalli@univ-savoie.fr title;quoted-printable:Ma=3DC3=3DAEtre de conf=3DC3=3DA9rences tel;work:+33 4 79 75 81 03 note:http://www.lama.univ-savoie.fr/~raffalli x-mozilla-html:TRUE version:2.1 end:vcard --------------010808050208030506060006-- --------------enig90AB18DDD0361E9742AAF204 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.7 (Darwin) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iD8DBQFODLKMi9jr/RgYAS4RAsZJAKDCq4hjNvqdXkcp67Ulwsj/t6MT9ACbBhTX fA2RqvK+Mgn8PZoulhfkkho= =m6Rc -----END PGP SIGNATURE----- --------------enig90AB18DDD0361E9742AAF204--