Talk:Happy numbers: Difference between revisions
Content added Content deleted
(New page: ==On caching (and laziness)== It seemed prudent to put in simple caching of n in the Python solution, but not the full-length permutations of the digits of n as cache size grows very quick...) |
(→On caching (and laziness): No caching is needed (and I don't believe the described optimized cache saves much)) |
||
| Line 1: | Line 1: | ||
==On caching (and laziness)== |
==On caching (and laziness)== |
||
It seemed prudent to put in simple caching of n in the Python solution, but not the full-length permutations of the digits of n as cache size grows very quickly. I had thought of just putting in a 'normal form' of n into the cache which would be the digits in sorted order, but then you would have to calculate the normal form before every search of the cache, which would take more time. Time vs space, space vs time? I chose the lazy option and left them both out of the Python, but maybe I should add an example with the normal-form space optimised cache so an implementation is out there? --[[User:Paddy3118|Paddy3118]] 00:28, 7 May 2009 (UTC) |
It seemed prudent to put in simple caching of n in the Python solution, but not the full-length permutations of the digits of n as cache size grows very quickly. I had thought of just putting in a 'normal form' of n into the cache which would be the digits in sorted order, but then you would have to calculate the normal form before every search of the cache, which would take more time. Time vs space, space vs time? I chose the lazy option and left them both out of the Python, but maybe I should add an example with the normal-form space optimised cache so an implementation is out there? --[[User:Paddy3118|Paddy3118]] 00:28, 7 May 2009 (UTC) |
||
: You don't need ''any'' caching (see the alternative C++ version I've just added). Of course you'll do more calculations anyway, so this is still a time/space tradeof. |
|||
: Also note that your "normal form" is the first part of the iteration step. Of course your cache is more effective if you also add the second step (because, after all, numbers which have a different normal form may still have the same next number (e.g. both 1111 and 2 have 4 as next value). But that's the same as using the original cache, but not caching in the first iteration. So the savings with your optimized cache are probably negligible. --[[User:Ce|Ce]] 07:20, 7 May 2009 (UTC) |
|||
Revision as of 07:20, 7 May 2009
On caching (and laziness)
It seemed prudent to put in simple caching of n in the Python solution, but not the full-length permutations of the digits of n as cache size grows very quickly. I had thought of just putting in a 'normal form' of n into the cache which would be the digits in sorted order, but then you would have to calculate the normal form before every search of the cache, which would take more time. Time vs space, space vs time? I chose the lazy option and left them both out of the Python, but maybe I should add an example with the normal-form space optimised cache so an implementation is out there? --Paddy3118 00:28, 7 May 2009 (UTC)
- You don't need any caching (see the alternative C++ version I've just added). Of course you'll do more calculations anyway, so this is still a time/space tradeof.
- Also note that your "normal form" is the first part of the iteration step. Of course your cache is more effective if you also add the second step (because, after all, numbers which have a different normal form may still have the same next number (e.g. both 1111 and 2 have 4 as next value). But that's the same as using the original cache, but not caching in the first iteration. So the savings with your optimized cache are probably negligible. --Ce 07:20, 7 May 2009 (UTC)