Python 3.3 vs. MSDOS Basic
Serhiy Storchaka
storchaka at gmail.com
Tue Feb 19 15:28:25 EST 2013
On 19.02.13 20:31, Ian Kelly wrote:
> On Tue, Feb 19, 2013 at 7:46 AM, Tim Daneliuk <tundra at tundraware.com> wrote:
>> Are you sure you wouldn't like to share with the class? I'd be interested
>> in seeing your approach...
>
> Very well:
>
> def collatz(n, memo):
> if n not in memo:
> if n % 2 == 0:
> next_n = n // 2
> else:
> next_n = 3 * n + 1
> memo[n] = collatz(next_n, memo) + 1
> return memo[n]
>
> def run_collatz(upper):
> table = {1: 0}
> max_n = max(range(1, upper), key=lambda n: collatz(n, table))
> return max_n, table[max_n]
>
>>>> run_collatz(1000000)
> (837799, 524)
>
> It could certainly be optimized further, but at about 4 seconds it's
> already fast enough for most purposes.
10-15% faster:
def f(M):
def g(n, cache = {1: 0}):
if n in cache:
return cache[n]
if n % 2:
m = 3 * n + 1
else:
m = n // 2
cache[n] = count = g(m) + 1
return count
num = max(range(2, M + 1), key=g)
return num, g(num)
print(*f(1000000))
More information about the Python-list
mailing list