Re: [Caml-list] Priority queues

[Andrew <newsgroups.fr@gmail.com>]

Wojciech Meyer wrote:
> 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).
>

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
>
>