StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Firstly, although <code>factorcalc</code> is "ugly", you could add a wrapper function <code>factors' x = factorscalc x 2 []</code>, add a comment, and move on.</p> <p>If you want to make a 'beautiful' <code>factors</code> fast, you need to find out why it is slow. Looking at your two functions, <code>factors</code> walks the list about <em>n</em>/2 elements long, but <code>factorcalc</code> stops after around <code>sqrt n</code> iterations.</p> <p>Here is another <code>factors</code> that also stops after about <code>sqrt n</code> iterations, but uses a fold instead of explicit iteration. It also breaks the problem into three parts: finding the factors (<code>factor</code>); stopping at the square root of <em>x</em> (<code>small</code>) and then computing pairs of factors (<code>factorize</code>):</p> <pre> factors' :: (Integral a) => a -> [a] factors' x = sort (foldl factorize [] (takeWhile small (filter factor [2..]))) where factor z = x `mod` z == 0 small z = z <= (x `div` z) factorize acc z = z : (if z == y then acc else y : acc) where y = x `div` z </pre> <p>This is marginally faster than <code>factorscalc</code> on my machine. You can fuse <code>factor</code> and <code>factorize</code> and it is about twice as fast as <code>factorscalc</code>.</p> <p>The <a href="http://book.realworldhaskell.org/read/profiling-and-optimization.html" rel="nofollow noreferrer">Profiling and Optimization chapter of Real World Haskell</a> is a good guide to the GHC suite's performance tools for tackling tougher performance problems.</p> <p>By the way, I have a minor style nitpick with <code>factorscalc</code>: it is much more efficient to prepend single elements to the front of a list O(1) than it is to append to the end of a list of length <em>n</em> O(n). The lists of factors are typically small, so it is not such a big deal, but <code>factorcalc</code> should probably be something like:</p> <pre> factorcalc :: (Integral a) => a -> a -> [a] -> [a] factorcalc x y z | y `elem` z = sort z | x `mod` y == 0 = factorcalc x (y+1) (y : (x `div` y) : z) | otherwise = factorcalc x (y+1) z </pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload