An answer to “real world haskell” Graham-scan exercice that actually works

In the previous article I mentioned how I found very hard to find a solution to the Graham Scan problem of “Real world Haskell” chapter 3. You will find a solution attached that actually seems to work. So, without further ado, here is my solution. It is really crude, and could probably be written in a much cleaner way. When compiled, it expects to get a list of points, one per line, represented as tab separated coordinates.

My solution is really crude, and could use a lot of polish. It should also be noted that it is very slow. However, here is how it performs compared “the Internet solution” :

 

Striking !
Comparison of the two implementations

For a a million points, here is the performance of the scan :

$ time ./mysolution < points.dat > solution1.dat
real    10m32.346s
user    10m28.670s
sys     0m2.320s

This is really bad, and it doesn’t behave at all like O(n log n), which was to be expected due to the fact  that I don’t know how to backtrack properly. But what’s even more funny is that the Internet solution behaves way worse, which means I did not analyze its complexity properly.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s