1
\$\begingroup\$

I have been working through the euler project and I have created the following code for Problem 14, which asks which starting number, under 1 million, produces the longest Collatz Sequence chain.

It takes a good minute to process. Can I make it faster?

class Collatz:

    def __init__(self):
        self.c = 1

    def if_even(self, n):
        return int(n / 2)

    def if_odd(self, n):
        return int(n * 3 + 1)

    def decide(self, n):
        if (n & 1) == 0:
            return self.if_even(n)
        elif (n & 1) == 1:
            return self.if_odd(n)

    def iter_nums(self, n):
        if n == 1:
            return n
        self.c += 1
        n = self.decide(n)    
        self.iter_nums(n)

largest = 0

# col = Collatz()
# col.iter_nums(13)

# print(col.c)


for i in range(1000000, -1, -1):
    col = Collatz()
    col.iter_nums(i)
    if col.c > largest:
        largest = i

print(largest)
\$\endgroup\$

closed as off-topic by 200_success, yuri, hjpotter92, Ludisposed, Graipher Jul 22 '18 at 17:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – 200_success, yuri, hjpotter92, Ludisposed, Graipher
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ A few ideas: 1. don't create a new instance each time; 2. look into caching/memoization/dynamic programming; and 3. simplify the code to remove the redundant method calls, there's a lot of indirection that I don't think makes it easier to follow. \$\endgroup\$ – jonrsharpe Jul 20 '18 at 13:15
  • \$\begingroup\$ Did this code work for you ? First I had a RecursionError and then, after changing the recursion limit from 1000 to 100000, I had a segmentation fault :-( \$\endgroup\$ – SylvainD Jul 20 '18 at 15:00
  • 5
    \$\begingroup\$ Does the main loop even function properly? It is comparing the length of the collatz sequence with largest, but storing the index, not the sequence length, in largest. Apples and oranges. \$\endgroup\$ – AJNeufeld Jul 20 '18 at 15:35
3
\$\begingroup\$

This problem really lends itself to dynamic programming. How many times to you really need to re-calculate the sequence starting at 10, which never changes? Remember that value and reuse it.

I wrote this like:

from functools import lru_cache

@lru_cache(None)
def coll(num):
    if num == 1:
        return 1

    if num % 2:
        return 1 + coll(num * 3 + 1)

    return 1 + coll(num / 2)

longest = 0
for i in range(1, 1_000_001):
    this = coll(i)
    if this > longest:
        print(i, this)
        longest = this

Without taking any special steps to optimize this, just that memoization dropped the runtime to 2.8s on my laptop.

\$\endgroup\$
5
\$\begingroup\$

Useless calls to int

When n is an integer:

  • n * 3 + 1 is an integer as well, you don't need to call int

  • int(n / 2) can also be computed using the "floored quotient" with the // operator.

You don't need a class

I highly recommend watching Jack Diederich's talk called "Stop Writing Classes". Classes are a great tool but they are not always needed, sometimes the problem can be solved with simple tools like functions.

In your case, the whole class can be restricted to a simple function, shorter, clearer, more efficient, easier to use.

def get_collatz_length(n):
    if n == 1:
        return 1
    return 1 + get_collatz_length((3 * n + 1) if (n & 1) else n // 2)

You don't need recursion

Once again, recursion can be a great way to write a concise solution for a given problem. However, in Python, it is sometimes best to avoid it: there is no tail-recursion optimisation and the call stack has a fairly limited size.

You could write something like:

def get_collatz_length_loop(n):
    l = 1
    while n != 1:
        n = (3 * n + 1) if (n & 1) else n // 2
        l += 1
    return l

To be continued: memoization

Is bitwise optimisation relevant?

\$\endgroup\$
  • \$\begingroup\$ On my laptop, using n % 2 is 4 seconds faster than using n & 1, over the 1 million collatz sequences. YMMV. \$\endgroup\$ – AJNeufeld Jul 20 '18 at 15:23
  • 1
    \$\begingroup\$ Looking forward to the momoization option..... \$\endgroup\$ – rolfl Jul 20 '18 at 16:48
  • \$\begingroup\$ @rolfl Sorry for the disappointment, I tend to give up the review when I realize the code never worked in the first place but I can see this got handled nonetheless in other answers :) \$\endgroup\$ – SylvainD Jul 24 '18 at 7:54
1
\$\begingroup\$

A function which computes all the numbers in the Collatz sequence, and then returns just the length of the sequence, but not the actual numbers, seems like over optimization and/or specialization. If one then wants the numbers in the Collatz sequence, you need to write effectively the same function again.

Instead, one can create a generator for Collatz sequences:

def collatz(n):
    yield n
    while n > 1:
        n =  n * 3 + 1  if  n % 2  else  n // 2
        yield n

Then, if you want a collatz sequence, you can easily get it:

>>> print(list(collatz(13)))
[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

If you want the length of the sequence, you can quickly count the number of elements the generator emits without creating the actual list:

>>> sum(1 for _ in collatz(13))
10

Determining the length of the longest sequence for all starting numbers up to 1 million still takes under 30 seconds on my laptop, even with the overhead of the generator and yield statements.

>>> max(sum(1 for _ in collatz(i)) for i in range(1000001))
525

Determining the starting number for the sequence whose length is 525 is left as an exercise to the student.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.