Hi, On Sun, Oct 9, 2011 at 11:08 PM, Daniel Fischer < daniel.is.fischer@googlemail.com> wrote:
A few problems: 1) your input cleaning is not correct, running it over the source file, I get (among others)
Thanks, I'll fix it asap.
2) If you have a looong but rare word in the text, you will get too many spaces between the words and the markers, that's not good.
Thanks.
3) you calculate the number of '#'s using the total line length and then subtract the length of (word + spaces), skewing your output. You should calculate (spaceForHashes = lineWidth - maxLength - 1) and the use that to determine the number of hashes. [Although it should be more complicated really, maxLength should only include those words that are actually output.]
Fixed, thanks. Style is okay, although like Michael Xavier, I'm more of a where-guy.
A part from style, is there any reason why one should prefer "where" over "let..in"?
You build the map via fromListWith (+). That's bad if you have input with large counts. fromListWith (+) gives you thunks of the form (...(1+1)+1)...+1) as map-entries. That costs a lot of space and time. Better build the map using insertWith',
mp = foldl' ins empty words where ins m w = insertWith' (+) w 1 m
Please find the "strict" version here: https://github.com/lbolla/stanford-cs240h/blob/master/lab1/lab1.hs. Plot of times is now: https://github.com/lbolla/stanford-cs240h/blob/master/lab1/times.png Python is still slightly faster, but I'm getting there.
3. a Python version using defaultdict. sort is O(n*log n), map and python are O(n*log d), where n is the number of words and d the number of distinct words.
I believe Python's defaultdict have (optimistically) O(1) lookup and insert, because it is implemented as a hashmap. Thanks everybody for your tips. They are most welcome. L.