On 6/29/05, Duncan Coutts
Indeed I understand from a colleague who implemented an all-pairs shortest paths algorithm in Haskell over the weekend for a map of the Hyde Park area of Chicago (no real reason, really!), that it takes about 0.1 seconds to execute (if you compile with -O), which is well within the 5 second limit...
Well, that is about two times slower than c++ code :p ... I mean: it's way faster that what I would have expected :) Anyway, I am interested in how DP-like algorithms are implemented in Haskell (with the same complexities), not in this particular problem. A week ago I tried LCS, now the ICFP contest fed me with another algorithm that isn't trivial to implement in this language. For ICFPC you could use some other solution than Floyd-Warshall but, again, I am asking about _this_ particular algorithm.
I wonder why everyone is so interested in the distances between intersections in the Hyde Park area of Chicago all of a sudden...
You are right: I'll ask again in 2 weeks. So please don't answer to this post :) -- regards, radu http://rgrig.blogspot.com/