Who can tell, please, how read string :: Integer is implemented in ghc-7.4.1 ? Is it linked from the GMP (Gnu Multi-Precision) library? It is suspiciosely fast :-) In my test on 10^5 strings of length l = 5, 20 it shows the cost order in l less than 1, as if it was O(log(l)), or O(squareRoot(l). This is even despite that the very forming of the string list by concat and by take l0Exp (strs l) seems to have large overhead. The impression is that I am missing something. Regards, ------ Sergei mechvel@botik.ru ------------------------------------------------------------------------- main = putStr (shows resSum "\n") where m = 1 :: Int -- edit this multiplicity: 1, 4 ... digits = (if m == 1 then id else reverse) ['0' .. '9'] :: [Char] l0 = 5 :: Int -- first length l0Exp = (10 :: Int)^l0 l = l0 * m -- second length strs :: Int -> [String] -- all digit strings of length n strs n = if n == 0 then [""] else concat [map (d :) (strs (pred n)) | d <- digits] strings = strs l segm = if m == 1 then strings else take l0Exp strings -- length segm is always 10^l0 resSum = sum [read str :: Integer | str <- segm] -- testPairs = [(str, read str :: Int) | str <- strings] -- correctness testing ------------------------------------------------------------------------
ghc -O2 --make Main time ./Main
You can see the source code for Read and its basic instances at
http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-Rea...
Search for readNumber to find the instances that parses numbers.
Nothing very much magical happens, lexP reads in a token (using
Text.Parsercombinators.readP_to_S and the small lexer in
Text.Read.Lex(http://hackage.haskell.org/packages/archive/base/latest/doc/html/Text-Read-L...,
click on the source link to see source)). If that token is a number of
the kind we were looking for (convertInt accepts only integers,
convertFrac can handle fractional and integer), return it, otherwise
fail.
Hoogle is a great resource for exploring the libraries . It's at
http://www.haskell.org/hoogle/ . That and the source links in the
documentation makes it easy to follow what happens all the way down.
-- Niklas
Den 12 februari 2012 13:50 skrev Serge D. Mechveliani
Who can tell, please, how read string :: Integer is implemented in ghc-7.4.1 ? Is it linked from the GMP (Gnu Multi-Precision) library?
It is suspiciosely fast :-) In my test on 10^5 strings of length l = 5, 20 it shows the cost order in l less than 1, as if it was O(log(l)), or O(squareRoot(l).
This is even despite that the very forming of the string list by concat and by take l0Exp (strs l) seems to have large overhead.
The impression is that I am missing something.
Regards,
------ Sergei mechvel@botik.ru
------------------------------------------------------------------------- main = putStr (shows resSum "\n") where m = 1 :: Int -- edit this multiplicity: 1, 4 ...
digits = (if m == 1 then id else reverse) ['0' .. '9'] :: [Char] l0 = 5 :: Int -- first length l0Exp = (10 :: Int)^l0 l = l0 * m -- second length
strs :: Int -> [String] -- all digit strings of length n strs n = if n == 0 then [""] else concat [map (d :) (strs (pred n)) | d <- digits]
strings = strs l segm = if m == 1 then strings else take l0Exp strings -- length segm is always 10^l0
resSum = sum [read str :: Integer | str <- segm]
-- testPairs = [(str, read str :: Int) | str <- strings] -- correctness testing ------------------------------------------------------------------------
> ghc -O2 --make Main > time ./Main
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Serge D. Mechveliani wrote:
Who can tell, please, how read string :: Integer is implemented in ghc-7.4.1 ? Is it linked from the GMP (Gnu Multi-Precision) library?
I believe your numbers simply were not large enough. I changed strs n to be strs n = if n == 0 then [""] else [d : ds | ds <- strs (pred n), d <- digits] (which changes the answer but avoids holding on to tons of memory) and ran the program for m = powers of 2 up to 128: 1 real 0m0.392s 2 real 0m0.447s 4 real 0m0.575s 8 real 0m0.995s 16 real 0m1.885s 32 real 0m3.695s 64 real 0m7.826s 128 real 0m17.344s (best run out of 9 each time) This looks super-linear already; in the end it should be quadratic. Bertram
participants (3)
-
Bertram Felgenhauer -
Niklas Larsson -
Serge D. Mechveliani