Hmm, is insertWith' new? If I remember right, I think the stack overflows were happening because Map.insertWith isn't strict enough. Otherwise I think the code is the same. But I would expect intTable to be faster, since it uses IntMap, and there's no
IntMap.insertWith' as of 6.6.1 (though it may be easy enough to add one).<br><br>Chad<br><br><div><span class="gmail_quote">On 10/17/07, <b class="gmail_sendername">Thomas Hartman</b> <<a href="mailto:thomas.hartman@db.com">
thomas.hartman@db.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br><font face="sans-serif" size="2">Since I'm interested in the stack overflow
issue, and getting acquainted with quickcheck, I thought I would take this
opportunity to compare your ordTable with some code Yitzchak Gale posted
earlier, against Ham's original problem.</font>
<br>
<br><font face="sans-serif" size="2">As far as I can tell, they're the same.
They work on lists up to 100000 element lists of strings, but on 10^6 size
lists I lose patience waiting for them to finish. </font>
<br>
<br><font face="sans-serif" size="2">Is there a more scientific way of figuring
out if one version is better than the other by using, say profiling tools?</font>
<br>
<br><font face="sans-serif" size="2">Or by reasoning about the code?</font>
<br>
<br><font face="sans-serif" size="2">t.</font>
<br>
<br><font face="sans-serif" size="2">****************************************</font>
<br>
<br><font face="Courier New" size="2">import Data.List</font>
<br><font face="Courier New" size="2">import qualified Data.Map as M</font>
<br><font face="Courier New" size="2">import Control.Arrow</font>
<br><font face="Courier New" size="2">import Test.QuickCheck</font>
<br><font face="Courier New" size="2">import Test.GenTestData</font>
<br><font face="Courier New" size="2">import System.Random</font>
<br>
<br><font face="Courier New" size="2">{-</font>
<br><font face="Courier New" size="2">Is there a library function to take
a list of Strings and return a list of</font>
<br><font face="Courier New" size="2">ints showing how many times each String
occurs in the list.</font>
<br>
<br><font face="Courier New" size="2">So for example:</font>
<br>
<br><font face="Courier New" size="2">["egg", "egg",
"cheese"] would return [2,1] </font>
<br><font face="Courier New" size="2">-}</font>
<br>
<br><font face="Courier New" size="2">testYitzGale n = do</font>
<br><font face="Courier New" size="2"> l <- rgenBndStrRow (10,10)
(10^n,10^n) -- 100000 strings, strings are 10 chars long, works.
craps out on 10^6.</font>
<br><font face="Courier New" size="2"> m <- return $ freqFold l
</font>
<br><font face="Courier New" size="2"> putStrLn $ "map items:
" ++ ( show $ M.size m )</font>
<br>
<br><font face="Courier New" size="2">testCScherer n = do</font>
<br><font face="Courier New" size="2"> l <- rgenBndStrRow (10,10)
(10^n,10^n) -- same limitations as yitz gale code.</font>
<br><font face="Courier New" size="2"> m <- return $ ordTable l
</font>
<br><font face="Courier New" size="2"> putStrLn $ "items: "
++ ( show $ length m )</font>
<br>
<br>
<br><font face="Courier New" size="2">-- slow for big lists</font>
<br><font face="Courier New" size="2">--freqArr = Prelude.map ( last &&&
length ) . group . sort</font>
<br>
<br><font face="Courier New" size="2">-- yitz gale code. same as chad scherer
code? it's simpler to understand, but is it as fast?</font>
<br><font face="Courier New" size="2">freqFold :: [[Char]] -> M.Map [Char]
Int</font>
<br><font face="Courier New" size="2">freqFold = foldl' g M.empty</font>
<br><font face="Courier New" size="2"> where g accum x = M.insertWith'
(+) x 1 accum</font>
<br><font face="Courier New" size="2">-- c scherer code. insists on ord.
far as I can tell, same speed as yitz.</font>
<br><font face="Courier New" size="2">ordTable :: (Ord a) => [a] ->
[(a,Int)]</font>
<br><font face="Courier New" size="2">ordTable xs = M.assocs $! foldl' f
M.empty xs</font>
<br><font face="Courier New" size="2"> where f m x = let m'
= M.insertWith (+) x 1 m</font>
<br><font face="Courier New" size="2">
Just v = M.lookup x m'</font>
<br><font face="Courier New" size="2">
in v `seq` m'</font>
<br>
<br>
<br><font face="Courier New" size="2">l = ["egg","egg","cheese"]</font>
<br>
<br><font face="Courier New" size="2">-- other quickcheck stuff</font>
<br><font face="Courier New" size="2">--prop_unchanged_by_reverse = \l ->
( freqArr (l :: [[Char]]) ) == ( freqArr $ reverse l )</font>
<br><font face="Courier New" size="2">--prop_freqArr_eq_freqFold = \l ->
( freqArr (l :: [[Char]]) == (freqFold l))</font>
<br><font face="Courier New" size="2">--test1 = quickCheck prop_unchanged_by_reverse</font>
<br><font face="Courier New" size="2">--test2 = quickCheck prop_freqArr_eq_freqFold</font>
<br>
<br><font face="Courier New" size="2">--------------- generate test data:
</font>
<br><font face="Courier New" size="2">genBndStrRow (minCols,maxCols) (minStrLen,
maxStrLen) = rgen ( genBndLoL (minStrLen, maxStrLen) (minCols,maxCols)
)</font>
<br>
<br><font face="Courier New" size="2">gen gen = do</font>
<br><font face="Courier New" size="2"> sg <- newStdGen</font>
<br><font face="Courier New" size="2"> return $ generate 10000 sg gen</font>
<br>
<br><font face="Courier New" size="2">-- generator for a list with length
between min and max</font>
<br><font face="Courier New" size="2">genBndList :: Arbitrary a => (Int,
Int) -> Gen [a]</font>
<br><font face="Courier New" size="2">genBndList (min,max) = do</font>
<br><font face="Courier New" size="2"> len <- choose (min,max)</font>
<br><font face="Courier New" size="2"> vector len</font>
<br>
<br>
<br><font face="Courier New" size="2">-- lists of lists</font>
<br><font face="Courier New" size="2">--genBndLoL :: (Int, Int) -> (Int,
Int) -> Gen [[a]]</font>
<br><font face="Courier New" size="2">genBndLoL (min1,max1) (min2,max2) =
do</font>
<br><font face="Courier New" size="2"> len1 <- choose (min1,max1)</font>
<br><font face="Courier New" size="2"> len2 <- choose (min2,max2)</font>
<br><font face="Courier New" size="2"> vec2 len1 len2</font>
<br>
<br><font face="Courier New" size="2">--vec2 :: Arbitrary a => Int ->
Int -> Gen [[a]]</font>
<br><font face="Courier New" size="2">vec2 n m = sequence [ vector m | i
<- [1..n] ]</font>
<br>
<br>
<br>
<br></blockquote></div>