Recently one of my favourite topics came up over dinner: the relative power of programming languages, in the guise of a programming challenge the person talked about as an interview question. I asked him to forward it on to me, and here it is:<\/p>\n
I wrote the following script in almost no time at all. This is the kind of task that the Unix shell really excels at, with much of the heavy lifting being done in the uniq routine. The sort | uniq -c<\/span><\/div>\n My next try was Python. This took a little longer to write, but appeared to run a bit faster. This is not surprising as the above code traverses each text file twice and contains four sorts. The Python code uses the really fast dictionary object to count the words, rather than using the sort and count approach in the shell code.<\/p>\n <\/p>\n The C++ version follows the same strategy as the Python program, using the C++ standard library equivalents of Python’s dictionaries and lists. I’ve left out the globbing, as the C++ STL doesn’t have functions for that. The typical use of this kind of commandline function would rely on the shell for globbing as I have here. Of course, if your shell is CMD.EXE you’re SOL. This program didn’t take that long to write, but it took ages to debug due to the heavy use of templates.<\/p>\n The guy had said that a typical Java program to do this was about 100 lines. Here is my attempt. Again, I have tried to keep the basic philosophy the same as with the Python program, using the Java standard library for maps and sorting rather than getting clever. Interestingly, this Java program is both the largest and the slowest of the lot. The Eclipse IDE cut a little of the time off writing this, and the Java generics are much easier to debug than C++ templates.<\/p>\n Note that this is my least fluent language, so this may be inelegant. Also, before you say it, I did have a version that used Linq. This was much more succinct, but it was really dog slow. I was really surprised that this program was the fastest of all the ones on this page, especially since I was running it on Mono.<\/p>\n <\/p>\n <\/div>\n For what it’s worth, here’s a table of metrics. I counted the non-comment non-blank lines, then ran the program through gzip to get an idea of the inherent token-complexity of the program (so that shorter variable names don’t make you win). I also ran the programs on the three files mentioned in the problem statement.<\/p>\n \u2020<\/sup> I have subtracted the lines occupied by braces on their own line. I would also like to comment on the idea that this is an unrealistic, non-real-world problem. I am a lecturer and have required similar programs several times when working with class lists. Questions routinely arise about which students have been in more than one class, or who needs to do a particular activity given the ones they have already done. Often the fastest way to get the answer us by a process similar to the word counting problem we have here. In fact, this is why I was able to bang out the shell solution so quickly.<\/p>\n Another aside: It has taken me longer to get the code properly input in this blog than it took me to write all the programs. And Blogger is supposed to be “easy to use”.<\/p><\/div>\n","protected":false},"excerpt":{"rendered":" Recently one of my favourite topics came up over dinner: the relative power of programming languages, in the guise of a programming challenge the person talked about as an interview question. I asked him to forward it on to me, and here it is: Pride and Prejudice, A Christmas Carol and A Tale of Two […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-45","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/sandrock.co.za\/carl\/wp-json\/wp\/v2\/posts\/45","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sandrock.co.za\/carl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sandrock.co.za\/carl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sandrock.co.za\/carl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sandrock.co.za\/carl\/wp-json\/wp\/v2\/comments?post=45"}],"version-history":[{"count":0,"href":"https:\/\/sandrock.co.za\/carl\/wp-json\/wp\/v2\/posts\/45\/revisions"}],"wp:attachment":[{"href":"https:\/\/sandrock.co.za\/carl\/wp-json\/wp\/v2\/media?parent=45"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sandrock.co.za\/carl\/wp-json\/wp\/v2\/categories?post=45"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sandrock.co.za\/carl\/wp-json\/wp\/v2\/tags?post=45"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}for f in pg*.txt; do\n echo $f\n echo \"Words: 1\"\n tr -s \"t \" \"n\" < $f | sort | uniq -c | sort -nr | head\n echo \"Words: 2\"\n tr -s \"t \" \"n\" < $f | awk 'NR>1 {print w\" \"$0} {w=$0}' | sort | uniq -c | sort -nr | head\ndone<\/pre>\n\nPython<\/h3>\n
import glob\nfrom collections import defaultdict\nfrom operator import itemgetter\n\ntopN = 10 # Display this number of elements in the report\n\nfor filename in glob.glob('pg*.txt'):\n # Parse\n previousword = None\n # Create a single-word and double-word counter\n counters = [defaultdict(int), defaultdict(int)]\n for word in open(filename, 'r').read().split():\n counters[0][word] += 1\n if previousword: counters[1][previousword + ' ' + word] += 1\n previousword = word\n\n # Report\n print \"File:\", filename\n for i, c in enumerate(counters):\n print \"Length\", i+1\n # Sort the counters by their counts, reverse order, take topN elements\n for item in sorted(c.items(), reverse=True, key=itemgetter(1))[:topN]:\n print \"%-20s%5i\" % item\n<\/pre>\n\nC++<\/h3>\n
#include <iostream>\n#include <map>\n#include <string>\n#include <cmath>\n#include <fstream>\n#include <iterator>\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nbool value(const pair<string, int>& a, const pair<string, int>& b)\n{ \n return a.second > b.second;\n}\n\n\nint main (int argc, char *argv[]) {\n for (int i=1; i<argc; i++) {\n ifstream infile(argv[i]);\n map<string, int> counter[2];\n\n cout << argv[i] << endl;\n\n \/\/ read file\n string word, previousword;\n bool firstword=true;\n\n while (infile >> word) {\n counter[0][word]++;\n if (!firstword) {\n counter[1][previousword + \" \" + word]++;\n previousword = word;\n } else {\n firstword = false;\n }\n }\n\n for (int c=0; c<2; c++) {\n cout << \"Words:\" << c+1 << endl;\n\n \/\/ sort\n vector<pair<string,int> > wordlist;\n copy(counter[c].begin(), counter[c].end(), \n back_inserter<vector<pair<string, int> > >(wordlist));\n sort(wordlist.begin(), wordlist.end(), &value);\n \n \/\/ write output\n for (int j=0; j < 10; j++) {\n cout << wordlist[j].first << \": \" << wordlist[j].second << endl;\n }\n }\n }\n}<\/pre>\n\nJava<\/h3>\n
import java.io.*;\nimport java.util.*;\n\npublic class ngrammer {\n\n public static void main(String[] args) throws FileNotFoundException {\n\n class WordCounter extends HashMap<String, Integer> {\n\n class ValueComparator implements Comparator<Map.Entry<String, Integer>> {\n \/\/ Comparator to allow sorting on the value of the HashMap elements\n @Override\n public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {\n return o2.getValue() - o1.getValue();\n }\n }\n\n void add(String word) {\n if (containsKey(word)) {\n put(word, get(word)+1);\n } else {\n put(word, 1);\n }\n }\n \n void printN(Integer N) {\n \/\/ Prints the top N elements of the counter\n \/\/ Make a list of the counter entries\n List<Map.Entry<String,Integer>> entries = new LinkedList<Map.Entry<String,Integer>>(entrySet());\n \/\/ Sort it on the value\n Collections.sort(entries, new ValueComparator());\n \/\/ Print out at most N items \n int i=N;\n for (Map.Entry<String,Integer> entry: entries) {\n System.out.println(entry.getKey() + \": \" + entry.getValue());\n if (--i == 0) break;\n }\n }\n }\n \n final int topN = 10;\n \n \/\/ Process each file in the input arguments\n for (int fi = 1; fi < args.length; fi++) {\n File file = new File(args[fi]);\n \/\/ Initialise new counters\n WordCounter[] counter = {new WordCounter(), new WordCounter()};\n String word, previousword=\"\";\n \/\/ Tokenise file\n Scanner scanner = new Scanner(file);\n while (scanner.hasNext()) {\n word = scanner.next();\n counter[0].add(word);\n if (!previousword.isEmpty()) \n counter[1].add(previousword + \" \" + word);\n previousword = word;\n }\n \/\/ Report\n System.out.println(\"Filename:\" + file.getAbsolutePath());\n for (int i = 0; i < counter.length; i++) {\n System.out.println(\"Words: \" + (i+1));\n counter[i].printN(topN);\n }\n }\n }\n}\n<\/pre>\n\nC#<\/h2>\n
using System;\nusing System.Collections.Generic;\nusing System.IO;\nusing System.Linq;\n\nclass MainClass\n{\n\n class WordCounter : Dictionary<string, int>\n {\n public void CountWord (string word)\n {\n if (ContainsKey (word)) {\n this [word]++;\n } else {\n this [word] = 1;\n }\n }\n\n public void Report (int N)\n {\n var list = this.ToList ();\n \n list.Sort ((a, b) => { return b.Value.CompareTo (a.Value); });\n foreach (var item in list.Take(N)) {\n Console.WriteLine(item.Key + \": \" + item.Value);\n }\n }\n }\n \n public static void Main (string[] args)\n {\n const int Ntop=10;\n\n foreach (string f in args) {\n WordCounter[] wordcounter = {new WordCounter(), new WordCounter()};\n\n string lastword = \"\";\n foreach (var word in File.ReadAllText(f).Split(' ')) {\n wordcounter[0].CountWord(word);\n if (lastword.Length > 0) {\n wordcounter[1].CountWord (lastword + \" \" + word);\n }\n lastword = word;\n }\n\n Console.WriteLine(f);\n for (int i=1; i<2; i++) {\n Console.WriteLine (\"Words: \" + (i+1));\n wordcounter[i].Report (Ntop);\n }\n }\n }\n}\n<\/pre>\n<\/div>\n<\/div>\n\nHaskell<\/h2>\n
module Main where\n\nimport System.Environment (getArgs)\nimport Data.List (sort, group)\n\ncountgroup xs = (length xs, head xs)\n\ntwowords (a, b) = a ++ \" \" ++ b\n\ncount = reverse . sort . map countgroup . group . sort \n\nformat (a, b) = b ++ \": \" ++ show a\n\nreport = mapM_ putStrLn . map format . take 10 . count\n\ncountfile f = do \n putStrLn f\n contents <- readFile f\n let thewords = words contents\n putStrLn \"Words: 1\"\n report $ thewords\n putStrLn \"Words: 2\"\n report . map twowords $ zip thewords (tail thewords)\n\nmain = getArgs >>= mapM_ countfile\n\n<\/pre>\n
\nClojure<\/h2>\n
(use '[clojure.string :only (split)])\n\n(defn twowords [words]\n (apply str (interpose \" \" words)))\n\n(defn bigrams [words]\n (map twowords (map list words (rest words))))\n\n(defn report [N, words]\n (take N (reverse (sort-by second (frequencies words)))))\n\n(defn dofile [N, filename]\n (let [words (split (slurp filename) #\"s+\")]\n (dorun (map println\n (concat [filename]\n [\"Words: 1\"]\n (report N words)\n [\"Words: 2\"]\n (report N (bigrams words)))))))\n\n(dorun (map (partial dofile 10) (rest *command-line-args*)))\n\n<\/pre>\n<\/div>\n
\nResults<\/h2>\n
\n\n
\n Language<\/th>\n Noncomment Lines<\/th>\n Gzipped bytes<\/th>\n Runtime \/ s<\/th>\n<\/tr>\n \n Shell<\/td>\n 7<\/i><\/td>\n 151<\/td>\n 0.88<\/td>\n<\/tr>\n \n Python<\/td>\n 16<\/td>\n 360<\/td>\n 0.48<\/td>\n<\/tr>\n \n C++<\/td>\n 40 – 7 = 23\u2020<\/sup><\/td>\n 484<\/td>\n 0.70<\/td>\n<\/tr>\n \n Java<\/td>\n 49 – 12 = 37\u2020<\/sup><\/td>\n 680<\/td>\n 1.92<\/td>\n<\/tr>\n \n C#<\/td>\n 46 – 21 = 25\u2020<\/sup><\/td>\n 548<\/td>\n 0.33<\/i><\/td>\n<\/tr>\n \n Haskell<\/td>\n 17<\/td>\n 308<\/td>\n 3.5<\/td>\n<\/tr>\n \n Clojure<\/td>\n 16<\/td>\n 287<\/td>\n 4.2\u2021<\/sup><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\n\u2021<\/sup> Includes compile time<\/p>\n