{"id":47,"date":"2007-11-09T13:31:30","date_gmt":"2007-11-09T11:31:30","guid":{"rendered":"http:\/\/ken.friislarsen.net\/blog\/2007\/11\/09\/decoding-morse-code-with-f-comprehensions\/"},"modified":"2016-03-31T18:55:37","modified_gmt":"2016-03-31T16:55:37","slug":"decoding-morse-code-with-f-comprehensions","status":"publish","type":"post","link":"http:\/\/ken.friislarsen.net\/blog\/2007\/11\/09\/decoding-morse-code-with-f-comprehensions\/","title":{"rendered":"Decoding Morse Code With F# Comprehensions"},"content":{"rendered":"

In my last post I showed how to decode morse code in Python using list comprehensions<\/a>. In this post I show how to do it in F#<\/a> instead.<\/p>\n

First using list comprehensions:<\/p>\n

let codes =\r\n    [(\"A\",\".-\");   (\"B\",\"-...\"); (\"C\",\"-.-.\"); (\"D\",\"-..\"); (\"E\",\".\");\r\n     (\"F\",\"..-.\"); (\"G\",\"--.\");  (\"H\",\"....\"); (\"I\",\"..\");  (\"J\",\".---\");\r\n     (\"K\",\"-.-\");  (\"L\",\".-..\"); (\"M\",\"--\");   (\"N\",\"-.\");  (\"O\",\"---\");\r\n     (\"P\",\".--.\"); (\"Q\",\"--.-\"); (\"R\",\".-.\");  (\"S\",\"...\"); (\"T\",\"-\");\r\n     (\"U\",\"..-\");  (\"V\",\"...-\"); (\"W\",\".--\");  (\"X\",\"-..-\");(\"Y\",\"-.--\");\r\n     (\"Z\",\"--..\")]<\/pre>\n
let rec decode input =\r\n    if input = \"\" then [\"\"]\r\n    else [ for c, code in codes when input.StartsWith(code)\r\n           for rest in decode(input.Substring(String.length code))\r\n           -> c + rest ]<\/pre>\n
As it can be seen the code is almost identical to the Python code. Incidentally, I could not find a function equivalent to Python’s startswith<\/code> method in the O’Caml standard library (without using regular expressions). Fortunately F# came with one from the .NET library.<\/p>\n
Much to my the surprise the compiled F# (running on Mono 1.2.4) is 4 times slower that the Python code. I then rewrote the program to use sequence comprehensions:<\/p>\n
let rec decode input =\r\n    if input = \"\" then { -> \"\" }\r\n    else { for c, code in codes when input.StartsWith(code)\r\n           for rest in decode(input.Substring(String.length code))\r\n           -> c + rest }<\/pre>\n
This version runs faster, and uses only a constant amount of memory. Still the Python version is three and half times faster.<\/p>\n
I then tried to run the programs on an other computer with Microsoft’s .NET implementation. This improved the F# running times a lot. However, they are still 40% to 80% slower than the Python version.<\/p>\n
\"Chart<\/p>\n
My current guess is that Python is much better at handling strings than .NET.<\/p>\n
The actual numbers:<\/p>\n\n\n\n\n\n\n\n
<\/th>\nLinux, Mono<\/th>\nVista, MS .NET<\/th>\n<\/tr>\n
Program<\/td>\nTime
\nsec<\/th>\n		Ratio<\/th>\nTime
\nsec<\/th>\n		Ratio<\/th>\n<\/tr>\n
morse.py<\/code><\/th>\n7.94 \u00b1 0.05<\/td>\n1<\/td>\n11.03 \u00b1 0.03<\/td>\n1<\/td>\n<\/tr>\n
morse.fs<\/code><\/th>\n33.07 \u00b1 0.19<\/td>\n4.17<\/td>\n19.65 \u00b1 0.33<\/td>\n1.78<\/td>\n<\/tr>\n
morse-seq.fs<\/code><\/th>\n28.1 \u00b1 0.59<\/td>\n3.54<\/td>\n16.12 \u00b1 0.36<\/td>\n1.46<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Update 2007-11-12 Added test files:<\/strong><\/p>\n