Albert Y. C. Lai wrote:

I try using WordSet = [String] (plus corresponding change in code) and get great speedup, actually way more than 3x. There was also a memory growth phenomenon using Set String, and replacement by [String] stops that too, now it's constant space (constant = 20M). It is possible to attribute part of the speedup to excellent rewrite rules in GHC regarding lists; however, I cannot explain the memory growth when using Set.

Now I see. The higher memory usage of the Set version is not growth or leak, just brutal. For each input word, a ton of derived words are generated, and an optimal one is chosen (by a criterion that's essentially a mapping from words to scores). There are two ways to do this. You could put the derived words into a lazy list and then traverse it, and therefore they're generated, examined, and thrown away on demand. At most two words are ever going to be stored (the best one so far and the next candidate), maybe plus a couple of cons cells if the compiler does not optimize. Or you could put all derived words into a set first (to avoid duplicates, but note that you still have to generate a ton, you only save by storing just half a ton), then traverse it. Storing a ton, or even just half a ton, of these words is going to clog up memory. The perceived growth is only because some input words cause fewer derived words and some other input words encountered later cause more derived words. So, plotting memory over time, once in a while we have more derived words than before, so the heap grows for that; they are still thrown away correctly in due course. If you input the same input word over and over gain, space usage is still constant.

Ketil Malde writes:

On Sun, 2007-04-22 at 00:25 -0400, Pete Kazmier wrote:

...

Pete Kazmier writes:

...

I'd love to see other Haskell implementations as well if anyone has a few moments to spare. Admittedly, it took me several hours to get my version working, but I'm a Haskell newbie. Unfortunately, I think it runs as slow as it took me to write it!

Hm - nobody suggested using ByteStrings yet? String is notoriously wasteful, and replacing it with ByteString normally gives a quite significant speedup.

I actually have a ByteString version but it runs much slower. This part of the code is where all of the time is spent in the ByteString version: type WordFreq = M.Map B.ByteString Int train:: [B.ByteString] -> WordFreq train words = frequencyMap where frequencyMap = foldr incWordCount M.empty words incWordCount w m = M.insertWith (+) w 1 m

Worse - and this is true for ByteStrings, too - String comparisons are O(n), which means lookups in Sets and Maps are expensive. A trie (i.e, a search tree where each internal node corresponds to a word prefix, and has one branch per letter in the alphabet) will give you lookup that scales with word size (and possibly alphabet size).

Right. My first version was just a direct translation of Norvig's code with an emphasis on trying to keep the complexity and size of code to a minimum.

Instead of generating the (huge) list of misspelled words, you could calculate edit distance to each correctly spelled word? With a bound on allowable mistakes, this is a linear time operation using the standard dynamic programming algorithm.

Could you provide additional information on this "standard dynamic programming algorithm?" I'm not familiar with dynamic programming. Thanks! Pete

On Sun, Apr 22, 2007 at 10:10:44PM +0200, Ketil Malde wrote:

On Sun, 2007-04-22 at 11:51 -0400, Pete Kazmier wrote:

...

type WordFreq = M.Map B.ByteString Int

train:: [B.ByteString] -> WordFreq train words = frequencyMap where frequencyMap = foldr incWordCount M.empty words incWordCount w m = M.insertWith (+) w 1 m

Isn't this going to build unevaluate thunks for the counts? This is what frequency counting looks like in some of my old code:

-- IM is Data.IntMap index ss = foldl' myupdate IM.empty ss where myupdate m k = let x = 1 + IM.findWithDefault 0 k m in x `seq` IM.insert k x m

(edited a bit, but hopefully correct)

I.e. use foldl', and look up previous value, succ and seq it, and put it back.

Generally, I only seem to want strict Maps. It seems so easy to build a lazy one if you need it (data Lazy a = Lazy a), so I wonder if strict should be the default?

...

...

Instead of generating the (huge) list of misspelled words, you could calculate edit distance to each correctly spelled word? With a bound on allowable mistakes, this is a linear time operation using the standard dynamic programming algorithm.

Could you provide additional information on this "standard dynamic programming algorithm?" I'm not familiar with dynamic programming.

Sorry! Dynamic programming just means using memoizing on a recursive function to reduce its run time complexity (although I don't think I've seen that definition anywhere?). A simple example is finding the n'th Fibonacci number by calculating (and referring to) the whole list.

For edit distance, you can do something like:

data Edit a = Repl a a | Delete a | Insert a

align (x:xs) (y:ys) = best [ Repl x y : align xs ys, Insert y : align (x:xs) ys, Delete x : align xs (y:ys)]

Where 'best' is some fitness function, selecting the best alignment.

Applying this directly gives an exponential algorithm, but since there are only n*m (n = lenght (x:xs), m = length (y:ys) possible ways to pick the remainders in the recursive calls throughout the execution, you might as well store them all in an n*m matrix - which only takes O(nm) time.

This is probably the worst explanation of DP so far this century, but if you Google for it, you'll find tons of information. Wikipedia has an entry as well.

Anyway: since the number of edits in this case is bounded (to four, since transposition can be modelled by an insertion and a deletion), you know the optimal solution will never stray further than two off the diagonal of the DP matrix, so you only need to caclulate a diagonal band (linear space/time), not the full matrix (quadratic).

You can almost always do DP with less space, and this is no exception: linear space for full Levenschtein, constant for the diagonal band. http://www.haskell.org/haskellwiki/Dynamic_programming_example#Optimization Stefan

On 4/22/07, Pete Kazmier wrote:

...

Worse - and this is true for ByteStrings, too - String comparisons are O(n), which means lookups in Sets and Maps are expensive. A trie (i.e, a search tree where each internal node corresponds to a word prefix, and has one branch per letter in the alphabet) will give you lookup that scales with word size (and possibly alphabet size).

Right. My first version was just a direct translation of Norvig's code with an emphasis on trying to keep the complexity and size of code to a minimum.

AFAIK, Python's dictionaries are implemented using hashtables, so lookups with them are much faster than with M.Map String Int. So should a direct translation use a Data.HashTable (despite its unpure interface)? But probably a trie should be better than both (just gambling ;-). Cheers, -- Felipe.

Bryan O'Sullivan writes:

After this switch, I found that spellchecking one word still took 4x as long in Haskell as Norvig's Python program. Since I was checking only one word in each case, essentially all of the runtime was taken up by building the word frequency map.

train = foldl' updateMap M.empty . map lower . mkWords where updateMap model word = M.insertWith' (+) word 1 model mkWords = filter (not . B.null) . X.splitWith isNotAlpha lower !s = X.map toLower s isNotAlpha !c = c < 0x41 || (c > 0x5a && c < 0x61) || c > 0x7a toLower !c | c >= 0x41 && c <= 0x5a = c + 0x20 | otherwise = c

After reading Bryan's post, I switched my right fold to a strict left fold and almost tripled my original speed. Could someone provide some guidelines on when to use each? I thought foldr should be used when building some large data structure such as the map I build. Bryan, out of curiosity, is a non bytestring version of your code faster? Thanks, Pete

Derek Elkins writes:

...

After reading Bryan's post, I switched my right fold to a strict left fold and almost tripled my original speed. Could someone provide some guidelines on when to use each? I thought foldr should be used when building some large data structure such as the map I build. Bryan, out of curiosity, is a non bytestring version of your code faster?

http://www.haskell.org/hawiki/StackOverflow

I read the article and understand it, but I am having a hard time applying that specifically to my use of foldr. Here is how I was using foldr: type WordFreq = M.Map B.ByteString Int train:: [B.ByteString] -> WordFreq train words = frequencyMap where frequencyMap = foldr incWordCount M.empty words incWordCount w m = M.insertWith (+) w 1 m So is 'incWordCount' strict in its second argument? I'm still not sure exactly what that means. According to the wiki page, if it is strict in the second argument, I should have used foldl' instead of foldr. Thanks, Pete

Pete Kazmier wrote:

train:: [B.ByteString] -> WordFreq train words = frequencyMap where frequencyMap = foldr incWordCount M.empty words incWordCount w m = M.insertWith (+) w 1 m

So is 'incWordCount' strict in its second argument? I'm still not sure exactly what that means.

Yes. incWordCount is strict in its second argument since incWordCount x undefined == undefined Of course you cannot see that from the definition of incWordCount alone, this depends on the behavior of M.insertWith.

According to the wiki page, if it is strict in the second argument, I should have used foldl' instead of foldr.

Remember that the difference between foldr and foldl is not one between left and right; both have to recurse from the left. But foldr is normal recursion, while foldl is accumulator recursion. You obviously wanted an accumulator, and it should usually be strictly evaluated. There is another bug of this sort in your code. Consider

incWordCount w m = M.insertWith (+) w 1 m

There is no reason to evaluate the sum inside the map, instead an unevaluated thunk is put in there. Unfortunately, you need to take the long way of using M.lookup and M.insert to build a strict replacement for M.insertWith. (A strict variant of Data.Map would be useful here, unfortunately, there is none.) -Udo -- Streitigkeiten dauerten nie lange, wenn nur eine Seite Unrecht hätte. -- de la Rochefoucauld

Bryan O'Sullivan wrote:

Udo Stenzel wrote:

...

There is another bug of this sort in your code. Consider

...

incWordCount w m = M.insertWith (+) w 1 m

There is no reason to evaluate the sum inside the map, instead an unevaluated thunk is put in there.

Would not Data.Map.insertWith' do the trick?

Oops, you're right, this is a fairly recent addition. -Udo -- Walk softly and carry a BFG-9000.

On Sun, 2007-04-22 at 12:55 -0400, Pete Kazmier wrote:

After reading Bryan's post, I switched my right fold to a strict left fold and almost tripled my original speed. Could someone provide some guidelines on when to use each? I thought foldr should be used when building some large data structure such as the map I build.

You are building a strict data structure, not a lazy one. You cannot use that map until every element has been inserted into it, there are no partial intermediate results you can use like say when you build a lazy list. Hence it's better to use a strict left fold. Rule of thumb: use a lazy fold to build lazy structures, use a strict fold to build strict ones. Duncan