Re: [Caml-list] Priority queues

[Wojciech Meyer <wojciech.meyer@googlemail.com>]

Andrew <newsgroups.fr@gmail.com> 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