Implementing memoization within a Collatz algorithm (Python)-CodePudding

I am trying to perform a Collatz algorithm on the following code. It works fine when I use a range of 1-10 etc... However, if the range is for example 1-500,000 it's too slow and won't ever show me the output of the longest sequence. So I was thinking about implementing memoization, however I am new to programming and find this really difficult and confusing.

I have looked at numerous posts and resources that I could use but couldn't really relate it to my code in a sense.

TL;DR Trying to use memoization to find the maximum length of a run for all possible values within a given range.

numberArray = []

s=int(1)
f=int(10)

def collatz(n):
    global count
    if n == 1:
        count  = 1
        numberArray.append(count)
        return True
    elif (n % 2) == 0:
        count  = 1
        collatz(n/2)
    else:
        count  = 1
        collatz(3*n 1)
        
for i in range (s, f 1):
  count = 0
  ourNumber = i
  collatz(i)

print(max(numberArray))

CodePudding user response：

Stef means something like this, which uses a dictionary to memorise the values that have already been counted:

s = 1
f = 10000000

def collatz(n):
    if n in collatz.calculatedData:
        return collatz.calculatedData[n]
    if (n % 2) == 0:
        count = collatz(n//2) 1
    else:
        count = collatz((3*n 1)//2) 2
    collatz.calculatedData[n] = count
    return count

collatz.calculatedData = {1:1}

s = s | 1 # must be odd

highest = max(collatz(i) for i in range(s, f 1, 2)) # faster with step 2
print(highest)
for k in collatz.calculatedData:
    if collatz.calculatedData[k]==highest:
        print(f"collatz({k}) is {highest}")

Output: 686 collatz(8400511) is 686

CodePudding user response：

Use lru_cache decorator. Its function to memorize (cache) the returned value of function called with specific argument.

Also read how to write clean code in python

The next code solves your problem

from functools import lru_cache

number_array = []

s = 1
f = 500000


@lru_cache
def collatz(n: int):
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1   collatz(n // 2)
    else:
        return 1   collatz(3 * n   1)


for i in range(s, f   1):
    number_array.append(collatz(i))

print(number_array)