Working on Project Euler problem #158 (http://projecteuler.net/ index.php?section=problems&id=158), and ran across list/string permutation on another maillist (http://www.mail-archive.com/ hask...@haskell.org/msg19032.html) that used list compression to form the permutations:
The functions `selections` and `splits` are extensionally equivalent, and I thought `selections` would have a faster execution time (as it does no O(n) delete, as it already "knows" both which item was deleted and the elements of the sublist), but profiling `chooseBy` ...
> chooseBy :: (Ord a, Eq a) => ([a] -> [(a, [a])]) -> Int -> [a] -> [[a]] > chooseBy f n list = permsoflen n list [] > where permsoflen n lst accum | n == 0 = [accum] > | otherwise = do (a,b) <- f lst > permsoflen (pred n) b (a:accum)
I'm running GHC 6.8.2. Is there a strong prejudice toward using arrows or point-free notation for that compiler? Does variable allocation via the standard lambda abstraction (ya know, standard, "point-full", function definitions) incur a heavy penalty in execution time? Is it that iteration with >>= is very much faster than the recursive call of `selections` in the list compression? Do calls within list compression not benefit from TCO/LCO (tail/last call optimisation)?
If not, what makes the arrow-based, point-free `splits` so much faster than `selections`?
It's not really anything special about arrows. splits trivially reduces to
splits l = map (\ x -> (x, delete x l)) l
FWIW, GHC seems to fire some map related rewrite rules. And it inlines splits, too.
Also, both splits and selections are in O(n^2) worst-case time. splits, of course, runs delete on the list for every element of the list. And selections has to cons onto the front of every result list (up to n of them) at each step (n of them) of recursion.
Other speculation: splits lets you share a lot of list structure in memory, while selections force you to create entirely new list structure for each element of the result. Not sure if this is relevant.
daucl...@gmail.com wrote: > Working on Project Euler problem #158 (http://projecteuler.net/ > index.php?section=problems&id=158), and ran across list/string > permutation on another maillist (http://www.mail-archive.com/ > hask...@haskell.org/msg19032.html) that used list compression to form > the permutations:
Hint: For this problem, you're much better off if you don't calculate the permutations explicitely (unless you want concrete numbers for small problem sizes to check your formulas). Instead, try to find a recurrence formula for the result (with memoization), or even an explicit formula.
I can get the answer nearly instantanously on the toplevel, without any compilation, even on my old computer.
> Is there a strong prejudice toward using arrows or point-free > notation for that compiler?
In general, arrows or point-free notation are often potentially slower, because the compiler has to inline those functions. (There may be rare cases when optimizations may work better with combinators, when the compiler has optimization rules that match the particular situation).
But the speed differences you get this way are nothing compared to the speed differences you get by changing your approach, and using a different algorithm.
> length $ chooseBy selections 5 ['a'..'z'] => 7893600 in 95.462925s > length $ chooseBy splits 5 ['a'..'z'] => 7893600 in > 24.045515s --- 4x faster! > If not, what makes the arrow-based, point-free `splits` so much faster > than `selections`?
I don't know -- optimizing Haskell for speed can be a black art :-) If you really want to find out, look at the intermediate code GHC produces.
But as I said, you get a much better speedup if you change your approach, instead of trying low-level optimizations. Many Project Euler problems are very good examples for this kind of attitude :-)
On Jun 21, 1:42 am, Matthew Danish <m...@cs.cmu.edu> wrote:
> It's not really anything special about arrows. splits trivially > reduces to
> splits l = map (\ x -> (x, delete x l)) l
Okay, then, but if we rewrite your fn to:
> matthew l = map (\x -> (x, delete x l)) l
and mine to
> doug list = list >>= return . (id &&& flip delete list)
the profiling of these two functions still shows a difference:
*Problem158> run (length $ chooseBy matthew 5 alf) "7893600" 24.842459s *Problem158> run (length $ chooseBy doug 5 alf) "7893600" 23.781618s
of almost a second, so even a rewrite of the point-free-arrow to point- full, ehrm, non-arrow fn still incurs a cost. Diving into more detail. If we divide the function into four equivalent functions: 1. pt-free-arrows, 2. pt-full-arrows, 3. pt-free-non-arrows, 4. mapped (pt-full-non-arrows), then we have the following definitions:
> arrowsplits, splits, mapSplits, ptSplits :: Eq a => [a] -> [(a, [a])] > arrowsplits list = list >>= return . ((\x -> x) &&& \y -> delete y list) > ptSplits list = list >>= return . (join (flip (,) . flip delete list)) > mapSplits list = map (\x -> (x, delete x list)) list > splits list = list >>= return . (id &&& flip delete list)
(yes, I came up with ptSplits on my own -- "Combinators, they're not just for breakfast anymore (TM)")
Then the profiling results are the following:
*Problem158> run (length $ chooseBy splits 5 alf) "7893600" 23.884974s *Problem158> run (length $ chooseBy arrowsplits 5 alf) "7893600" 24.130228s *Problem158> run (length $ chooseBy ptSplits 5 alf) "7893600" 25.082024s *Problem158> run (length $ chooseBy mapSplits 5 alf) "7893600" 24.822053s
which seems to indicate that the pt-free-arrowed function is fastest, but egregious use of pt-free slows one down the most. In general, the arrowed versions are faster than their non-arrowed counterparts, but strangely, pt-free has different results ... hm, let's see how pt-free with map stacks up against pt-full map:
> mapArrowFreeSplits list = map (id &&& flip delete list) list > mapFreeSplits list = map (join (flip (,) . flip delete list)) list
*Problem158> run (length $ chooseBy mapSplits 5 alf) "7893600" 24.678785s *Problem158> run (length $ chooseBy mapArrowFreeSplits 5 alf) "7893600" 23.076796s *Problem158> run (length $ chooseBy splits 5 alf) "7893600" 23.893799s *Problem158> run (length $ chooseBy mapFreeSplits 5 alf) "7893600" 23.832586s
Hm, it seems to like map (with pt-free and arrow notation) wins over
>>= . return.
Given all these data, it seems that there is a preference for (moderate) pt-free notation combined with arrows, or, generally, arrows over non-arrows. So, can it then be deduced:
"I feel the need ... the need for SPEED! [Copyright (c) 1986, Top Gun" "Well, then, use Arrows, it's GOOD for you(TM)"
or are there other, or no, conclusions to be drawn from the above?
On Jun 21, 3:29 am, Dirk Thierbach <dthierb...@usenet.arcornews.de> wrote:
> daucl...@gmail.com wrote: > > Working on Project Euler problem #158 [...] > Hint: For this problem, you're much better off if you don't calculate > the permutations explicitely (unless you want concrete numbers for > small problem sizes to check your formulas). Instead, try to find > a recurrence formula for the result (with memoization), or even > an explicit formula.
> I can get the answer nearly instantanously on the toplevel, > without any compilation, even on my old computer.
Actually, I did get the answer right away, if one were to read the problem literally, ignoring the example case, they say n <= 26, for letters take n (permute ['a' .. 'z']) for a string length n. This, of course, is 67108837, from A000295, see http://www.research.att.com/~njas/sequences/A000295. N.B. they use the same exact n to describe number of different characters allowed from the alphabet as they do to bind the length of the string. A string of length 5, therefore, has ONLY 5 allowable different characters in its alphabet to choose from.
But, no, no matter what the specification is as written, Project Euler seems to wish us to use 26 characters for the alphabet, no matter how the length of the string is constrained, because it does not accept any number in the A000295 sequence as the answer.
I'm not happy about this turn of events, but I suppose someday after I get the other "correct" answer (meaning, "the wrong answer to the problem as stated, but the 'right' answer to what they wanted the problem to mean, but weren't precise or careful enough to write correctly"), I'll grow into a transcendent state of acceptance about it.
Or, someday, I'll just chill out enough not to allow it to bother me anymore.
... but I doubt it.
> I don't know -- optimizing Haskell for speed can be a black art :-) > If you really want to find out, look at the intermediate code GHC > produces.
ick. No thanks (that's what compilers are for, right?). At any rate, in general, GHC is blazingly fast, comparable to low-level C code, and the benefit is one can write Haskell, qua Haskell, and oftentimes come out with a fast-enough solution. So, if I need fast code, I don't need to resort to writing things in C (or assembler, as I seen done on some projects).
Who can I shake hands with in thanks for this gift?
The same can be said for other programming languages, ML, Lisp, Scheme, Dylan, Prolog, Mercury, Clean, Erlang. All fast, all declarative. To all, thanks!
> But as I said, you get a much better speedup if you change your > approach, instead of trying low-level optimizations. Many Project > Euler problems are very good examples for this kind of attitude :-)
Yes, despite my spiteful rant above about the wording of problem 158, I like these problems because there's very little hand-holding involved, so it sends the investigator on a mathematical journey of discovery. Nice. There are some problems that currently befuddle me completely, which makes me yearn for a hints link of some sort, but that's just weakness on my part, because real-world problems usually don't come with a whispering muse or guru ...
Your post reminds me of a "fastest programming language" contest that went on in some mail list a few years ago -- "How many hands does 3 kings beat in a game of poker?" Of course, most everyone set up 5 loops and compared hands to hands to come up with an answer, so all results were in the more-than-one-minute category. One Smalltalker used Pascal's triangle to solve the problem in sub-second time. He never crowed "Smalltalk wins", nor even entered the contest (it was all, "C++ is better" "No, Java is better", etc), but he made mention of it on the Smalltalk mail list as an aside, showing that good mathematics handily beats the brute force approach.
I based my translation on the following simple facts about Monads, Functors, and Arrows:
(1) Relationship between fmap and bind: x >>= (return . f) = fmap f x
(2) fmap = map -- when used on Lists
(3) f &&& g = \ x -> (f x, g x) -- on the Function Arrow a.k.a. the (-
>) Arrow
I think you have missed an important point with (1): that if you find yourself writing ">>= return" then you should think about using fmap instead. The other two points serve to show that your arrow code was a simple map. [1]
I would also like to correct your definition of "point-free:" none of the functions you wrote are point-free. This is the point-free version of splits:
splits :: Eq a => [a] -> [(a, [a])] splits = join (map . (ap (,) . flip delete)) -- or splits = (ap (,) . flip delete) >>= map
but note that this use of join or >>= is in the ((->) a) Monad, not the list one. It's essentially just making sure that the input is duplicated and supplied to both map and delete.
There is no explicit variable binding, unlike your examples which always bind 'list'. Also note that the type signature here is mandatory, or else you run into the monomorphism restriction because "splits =" is, at face value, syntactically a constant and constants are not allowed to have type-class polymorphic types inferred.
Also, I'm not suggesting you USE this point-free version, just demonstrating it. As you have probably already discovered to some extent, point-free code is not always the most readable code.
Finally, I wouldn't count the differences in performance that you displayed as significant without further investigation. A difference of one second within 24 seconds could be within the margin of error. Did you run it multiple times and get very similar results? In the overall scheme of things, one second here or there in a long-running program is not something I would sacrifice readability to gain. It could easily be due to peculiarities in the GHC optimizer or even the low-level architecture which favor certain orderings of instructions, memory hits, or whatnot. That can change from version to version, or hardware to hardware.
In summary, I'd say the last bit of advice is simply a longer version of "premature optimization is the root of all evil."
[1] In fact, (&&&) doesn't appear like that in GHC, it is derived from other Arrow operators -- but presumably those are folded by the compiler.
On Jun 21, 4:35 pm, Matthew Danish <m...@cs.cmu.edu> wrote:
> Finally, I wouldn't count the differences in performance that you > displayed as significant without further investigation. A difference > of one second within 24 seconds could be within the margin of error. > Did you run it multiple times and get very similar results?
Yes, these are over (many) multiple runs.
> In the > overall scheme of things, one second here or there in a long-running > program is not something I would sacrifice readability to gain.
I agree.
> It > could easily be due to peculiarities in the GHC optimizer or even the > low-level architecture which favor certain orderings of instructions, > memory hits, or whatnot. That can change from version to version, or > hardware to hardware.
So you are then saying that GHC favors (semi) pt-free-arrowed code over other styles? I'm running the code on a Mac, if you have a PC, would you try running the system and seeing if the fallout is the same? If so, that's a stronger case that its a GHC preference.
> In summary, I'd say the last bit of advice is simply a longer version > of "premature optimization is the root of all evil."
Heh. Well said, sir:
|Optimization can reduce readability and add code that is used only to improve the performance. |This may complicate programs or systems, making them harder to maintain and debug. As a result, |optimization or performance tuning is often performed at the end of the development stage. | |Donald Knuth said | | * "We should forget about small efficiencies, say about 97% of the time: premature |optimization is the root of all evil." (Knuth, Donald. Structured Programming with go to |Statements, ACM Journal Computing Surveys, Vol 6, No. 4, Dec. 1974. p.268.)
to be just as readable (more readable, to my mind) as the others, and in my preferred style (I visualize the data flow better with >>= than with map, I was aware of the >>=/fmap relation when Monad m => m a is also a Functor), so, in this case, Knuth's admonishment does not apply.
daucl...@gmail.com wrote: > Dirk Thierbach <dthierb...@usenet.arcornews.de> wrote: > N.B. they use the same exact n to describe number of different > characters allowed from the alphabet as they do to bind the length > of the string. A string of length 5, therefore, has ONLY 5 > allowable different characters in its alphabet to choose from.
No. They say "We now consider strings of n <= 26 different characters from the alphabet." In other words, you look at a string consisting of n different characters (which then of course has length n), and you're guaranteed that the "interesting" n are always less than 26 (because that's the number of characters you can choose from).
Yes, the wording isn't particularly clear, which really shouldn't happen.
> But, no, no matter what the specification is as written, Project Euler > seems to wish us to use 26 characters for the alphabet, no matter how > the length of the string is constrained, because it does not accept > any number in the A000295 sequence as the answer.
Yes. Otherwise the answer would be too easy. :-)
>> I don't know -- optimizing Haskell for speed can be a black art :-) >> If you really want to find out, look at the intermediate code GHC >> produces. > ick. No thanks (that's what compilers are for, right?).
Yes. But that's the only way you'll really understand what's going on. *If* you are interested (I am usually not :-).
> Yes, despite my spiteful rant above about the wording of problem 158, > I like these problems because there's very little hand-holding > involved, so it sends the investigator on a mathematical journey of > discovery.
Though sometimes brute force solves it, and then you can read afterwards in the forum how you should have really done it. That's really a pity, there should be some way to put you on the right track without that.
And for some problems even the really smart people there find no solution other than essentially brute force (though with some programming tricks).
> Your post reminds me of a "fastest programming language" contest that > went on in some mail list a few years ago -- "How many hands does 3 > kings beat in a game of poker?"
Hadn't heard of this :-)
> showing that good mathematics handily beats the brute force > approach.
