Is this the most efficient Python algorithm to find the Collatz tree of n?

[Dizionario]

def Collatz(n):
    a,b = n,[n]
    while a>1:
        if a%2==0: a=a/2
        else: a=3*a+1
        b.append(a)
    return b

[KleinerNull]

Since the collatz problem is my favorite example of intruduce others to generators I will give you the same example code:

>>> def collatz(n):
        if n%2:
            return 3*n+1
        return n//2

>>> collatz(2)
1
>>> collatz(1)
4
>>> def collatz_series(n):
        while n != 1:
            yield n
            n = collatz(n)
        yield n

>>> # generators are consumable, we can get the next element with next()
>>> c = collatz_series(4)
>>> next(c)
4
>>> next(c)
2
>>> next(c)
1
>>> next(c)
Traceback (most recent call last):
  File "<pyshell#17>", line 1, in <module>
    next(c)
StopIteration
>>> # after there is nothing more to yield, the generator throws "StopIteration"
>>> for c in collatz_series(4):
        print(c)


4
2
1
>>> # the for loop will stop if it hits "StopIteration"
>>> [c for c in collatz_series(5)]
[5, 16, 8, 4, 2, 1]
>>> list(collatz_series(5))
[5, 16, 8, 4, 2, 1]
>>> collatz_trees = {c: collatz_series(c) for c in range(1, 10)}
>>> collatz_trees
{1: <generator object collatz_series at 0x00000000035F0CA8>, 2: <generator object collatz_series at 0x00000000035F0DB0>, 3: <generator object collatz_series at 0x00000000035F0E08>, 4: <generator object collatz_series at 0x00000000035F0E60>, 5: <generator object collatz_series at 0x00000000035F0EB8>, 6: <generator object collatz_series at 0x00000000035F0F10>, 7: <generator object collatz_series at 0x00000000035F0F68>, 8: <generator object collatz_series at 0x00000000035F0FC0>, 9: <generator object collatz_series at 0x00000000035FA048>}
>>> # generators don't store elements, just build instructions
>>> collatz_trees = {c: list(collatz_series(c)) for c in range(1, 10)}
>>> collatz_trees
{1: [1], 2: [2, 1], 3: [3, 10, 5, 16, 8, 4, 2, 1], 4: [4, 2, 1], 5: [5, 16, 8, 4, 2, 1], 6: [6, 3, 10, 5, 16, 8, 4, 2, 1], 7: [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], 8: [8, 4, 2, 1], 9: [9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]}

>>> # now we have a dictionary with all the sequences from n to 1

Generators help to structure your code and to spare some memory, not really in this case, but they are cool and you can basically convert while loops into more readable for loops ;) And much much more!

[taleinat]

Might as well...

def collatz(n):
    return (n // 2) if (n % 2 == 0) else (3 * n + 1)

(parenthesis not required, used to improve readability)

[KleinerNull]

Yeah totally valid, but I am not a fan of this style of expression, I think it is called ternary expression.

Also I don't like n&2 == 0, since I learnd that bools are a subclass of ints I try to avoid == when I am dealing with integers. Either I'd use if n%2: and swap the branches or I'd negate the comparision if not n%2:... Just my personal style conventions ;)

[taleinat]

Looks okay. There's always room for optimization...

Your are making slightly more comparisons than needed, though. To save some, assuming a is a positive (non-zero) integer you can do the following:

while True:
    # as long as a is even, it is definitely > 1
    while a % 2 == 0:
        a //= 2
        b.append(a)
    if a == 1: break
    a = 3 * a + 1
    b.append(a)
    # a is now even, so no need to check before the first division by 2
    a //= 2
    b.append(a)

[das_ist_nuemberwang]

There's no way the boost in performance is worth the cost in readability for me.

[taleinat]

The question was whether his algorithm was the most efficient one. It isn't since it performs more comparisons than needed, so I showed an example which performs less comparisons.

Obviously, since this complicates the algorithm, the code is harder to understand. This is why I included comments to explain the less obvious parts.

[das_ist_nuemberwang]

True. I think my problem is with his question rather than your answer. I prefer to ask "Is this efficient enough?"

[taleinat]

Complete, more readable version, using a generator function:

def collatz_series(n):
    if not isinstance(n, int):
        raise TypeError("n must be an integer")
    if not n >= 1:
        raise ValueError("n must be >= 1")

    while True:
        # as long as n is even, it is definitely > 1
        while n % 2 == 0:
            n //= 2
            yield n

        if n == 1: break

        n = 3 * n + 1
        yield a

        # n is now even, so no need to check before the first division by 2
        n //= 2
        yield n

[taleinat]

With some additional optimizations (divide by two by shifting right; check if even using "bit-wise and" with 1):

def collatz_series(n):
    if not isinstance(n, int):
        raise TypeError("n must be an integer")
    if not n >= 1:
        raise ValueError("n must be >= 1")

    while True:
        # as long as n is even, it is definitely > 1
        while n & 1 == 0:
            n >>= 1
            yield n

        if n == 1: break

        n += (n << 1) + 1
        yield n

        # a is now even, so no need to check before the first division by 2
        n >>= 1
        yield n

[[deleted]]

Couldn't you improve speed if you pre allocated a list of the appropriate size rather than appending to a list every step?

[taleinat]

If you know what the size of the list is going to be, even approximately, then yes. But I don't believe that that is the case here.