User talk:WillNess: Difference between revisions

← Older edit

User talk:WillNess (view source)

Revision as of 07:43, 27 December 2016

412 bytes added , 7 years ago

done!

WillNess

751

edits

Revision as of 17:05, 22 August 2016 (view source) WillNess (talk \| contribs) (→‎Space complexity improvement -- Hamming numbers: something strange) ← Older edit		Latest revision as of 07:43, 27 December 2016 (view source) WillNess (talk \| contribs) (done!)
(4 intermediate revisions by 3 users not shown)
Line 79: ::::::: BTW the really short version of it is just <code>(Sum c,b) = mconcat [ ( Sum (i+1), ...</code>. Here it could be argued that it '''''ought''''' to be compiled efficiently, as the whole premise of Monoids is that associativity enables re-parenthesization ''(<code>a:b:c:... = [a]++([b]++([c]++...)) = ([a]++[b])++([c]++...)</code>)'', which is the basis for the efficiency of the strict left fold. Yet it is more than twice worse than the <code>prod</code> code, both in time and space. ::::::: Something strange is going on with this at Ideone. I've always assumed that the memory usage reported by Ideone follows the ''"total memory in use"'' reported by <code>+RTS -s</code>, with some constant overhead. It looks '''''as if''''' some optimization kicks in for the lower ''n''s, and the near-zero memory operation ''is'' being achieved there <sup>()</sup>; and for the larger values this optimization does not kick in and the execution reverts to what we both seen locally, i.e. the growing memory usage. BTW, I got 1B:0.45s-269MB and 10B:1.75s-1343MB, which suggests 1T:38s-'''28.8GB''' ''"total memory in use"''. The fold-based version indeed did good at 1T:11.2s-'''10MB'''. I use the signature <code>Int -> (Double, (Int,Int,Int))</code> which produced the fastest code in my tests (simple -O2). -- [[User:WillNess\|WillNess]] ([[User talk:WillNess\|talk]]) 17:13, 22 August 2016 (UTC) :::::::: Looks good; it's still about three times slower and uses more memory than 1T:3.75s:3MB "total memory in use" (from local) as for my version on IdeOne but it is good as referents will have a choice. I went back to using Word64 as the fastest (just a slightly higher range than Int) even for 32-bit code as it is faster, since it then uses the same type for the internal count. it looks like for all the Monoid stuff to work as you would like to see it there will have to be all kinds of specializations that haven't been added - complex stuff, and doing "concat" efficiently has always been a headache. --[[User:GordonBGood\|GordonBGood]] ([[User talk:GordonBGood\|talk]]) 00:50, 23 August 2016 (UTC) ::::::: --- <sup>()</sup> this is also supported by the '''very fast execution times for the 10B <code>prod</code>-based version'''. Usually Ideone is about 3.5x slower than my box, but this ran 1.25x '''faster''' (!!??). But, comparing it with the 10B timing for the local '''<code>foldl'</code>-based version''', it indeed ran 3.85x slower. -- [[User:WillNess\|WillNess]] ([[User talk:WillNess\|talk]]) 17:05, 22 August 2016 (UTC) == Factors of an integer == The current algorithms factors_co and factors_o seem to give the wrong result. For example, factors_co 120 is missing the number 12 in its result. --[[User:Helge\|Helge]] ([[User talk:Helge\|talk]]) 13:15, 26 December 2016 (UTC) : Good catch, thanks! Will fix. -- [[User:WillNess\|WillNess]] ([[User talk:WillNess\|talk]]) 21:06, 26 December 2016 (UTC) : Done! Thanks again for spotting this. An added bonus was, the code simplified a bit, too. -- [[User:WillNess\|WillNess]] ([[User talk:WillNess\|talk]]) 07:43, 27 December 2016 (UTC)