Andrew <[email protected]> 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 -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
