User talk:WillNess: Difference between revisions
→Space complexity improvement -- Hamming numbers: Haskell: why "out of memory"...
mNo edit summary |
GordonBGood (talk | contribs) (→Space complexity improvement -- Hamming numbers: Haskell: why "out of memory"...) |
||
Line 70:
::::: Yes, I saw that error for above 10--20B; I decided to not care about it here, and to go with the shorter code to express the algorithm clearly. The "out of memory" bit comes from Ideone and I'm not entirely sure why, when it's still reporting the exact same memory consumption for all the cases below 10B. ''Real'' space leaks are usually seen on Ideone as reported memory climbing up into the 100s MBs, not so here. Any case, it's a compiler issue. And, we have your version on the page now for the optimized code. :) -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 06:50, 22 August 2016 (UTC)
:::::: Just for completeness, the "out of memory" error isn't just IdeOne but also with Windows GHC version 8.0.1 for values approaching a trillion on my machine (which has a lot of memory; I haven't tried to determine the exact limit); the < 20 billion limit on IdeOne is due to the amount of memory assigned. I suspect it isn't flagged as a "real" space leak because there is not a fixed pointer to the unevaluated zipped list; there is just the unevaluated list comprehensions. When the "sum" operation is run, it forces the partial evaluation of every list element to the first part of the tuple '''but not the evaluation of the predicate on whether a given element gets including in the concatenated list or not'''; this last doesn't get evaluated until the determined values get sorted, at which point the unused values get dumped (and garbage collected). So, during the course of calculation to a trillion, something like 100's of Gigabytes would be consumed (my machine doesn't have that many and thus fails). Thus, during the execution of the program the memory use goes from zero to very high but is back to very low again by the time the program ends. Although the expression of the algorithm is beautiful, the memory use profile is not! And yes, my version shows what can be done, including that if IdeOne were 64-bit, 10 billion should take less than 150 milliseconds, not about a half second for the "foldl'" version, not about 1.5 seconds for this version, and that maximum memory residency (as determined by "+RTS -s") is almost zero not many many megabytes. --[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 08:28, 22 August 2016 (UTC)
| |||