Discussion on: Another Way to Find Max Partitions

[Christophe Riolo]

Awesome thinking! Thanks for the algorithm!
I'm on my phone so hard to time, so I'll let you try it, but a couple of ideas that might make the code a bit faster :

from math import ceil # no dynamic lookup of ceil

def optimal_summands(n):
    k = ceil(((1 + 8*n)**0.5 - 1) / 2)  # one affectation less
    the_sum = k * (k+1) // 2 # no casting, python will make an int
    diff = the_sum - n - 1 # outside the list comprehension to make sure it's computed only once
    return [i for i in range(1, k+1) if i != diff] # less code, more pythonic. If n is senior, diff is negative so nothing is filtered out.

[Saurabh Chaturvedi]

Amazing! Thanks for making the code more Pythonic! But, won't the if in the list comprehension be computed k times? In my version, it was computed just once, but then the del made O(k) shifts, so both seem nevertheless sort of balanced. I don't know precisely why, but after I benchmarked your code with mine, my code still ran in a quarter of time taken by your code.

[Christophe Riolo]

Yes indeed, I just got my hands on a computer and I tested everything out, you were faster than me :)
I have a very slight increase in performance with this version :

from math import ceil # no dynamic lookup of ceil

def summands_opt(n):
    k = ceil(((1 + 8*n)**0.5 - 1) / 2)  # one affectation less
    the_sum = k * (k+1) // 2 # no casting, python will make an int
    summands = list(range(1, k+1))
    del summands[the_sum-n-1]
    return summands

The del statement does not fail when there is nothing to delete.

[Saurabh Chaturvedi]

Awesome! Now this is some production-quality code! Thanks for adding readability to the code as well.

[Christophe Riolo]

Don't listen to this tired programmer who did too much Ocaml lately: the condition is necessary because of how python interprets negative indices.
I tried other versions, thinking that using more iterators should be faster, but surprisingly no. Here are all the codes and timings I did:

import math
from math import ceil # no dynamic lookup of ceil
from itertools import chain

def summands(n):
    k = ((1 + 8*n)**0.5 - 1) / 2
    k = math.ceil(k)
    summands = list(range(1, k+1))
    the_sum = int(k * (k+1) / 2)
    if the_sum - n > 0:  # If n is not senior.
        del summands[the_sum-n-1]
    return summands

def summands_opt(n):
    k = ceil(((1 + 8*n)**0.5 - 1) / 2)
    the_sum = k * (k+1) // 2
    summands = list(range(1, k+1))
    if the_sum - n > 0:  # If n is not senior.
        del summands[the_sum-n-1]
    return summands

def summands_iter(n):
    k = ceil(((1 + 8*n)**0.5 - 1) / 2)
    the_sum = k * (k+1) // 2
    pluck = max(0, the_sum - n)
    return list(chain(
        range(1, pluck),
        range(pluck+1, k+1)))

def summands_list(n):
    k = ceil(((1 + 8*n)**0.5 - 1) / 2)
    the_sum = k * (k+1) // 2
    pluck = max(0, the_sum - n)
    return list(range(1, pluck)) + list(range(pluck+1, k+1)

>>> from timeit import timeit
>>> timeit(setup='from partition import summands', stmt='summands(10000)', number=100000)
0.17959438299976682
>>> timeit(setup='from partition import summands_opt', stmt='summands_opt(10000)', number=100000)
0.15117240200015658
>>> timeit(setup='from partition import summands_iter', stmt='summands_iter(10000)', number=100000)
0.2742825210002593
>>> timeit(setup='from partition import summands_list', stmt='summands_list(10000)', number=100000)
0.23539557200001582

The last two surprised me a lot: how can the chaining of iterators be slower than concatenation of lists? But unsurprisingly the definition of a custom generator to chain was even slower…

def summands_gen(n):
    k = ceil(((1 + 8*n)**0.5 - 1) / 2)
    the_sum = k * (k+1) // 2
    pluck = max(0, the_sum - n)
    def gen():
        yield from range(1, pluck)
        yield from range(pluck+1, k+1)
    return list(gen())

[Christophe Riolo]

However, once removing the casting to list, summands_iter would be the only version that do not cause an overflow for very large numbers :

def summands_iter(n):
    k = ceil(((1 + 8*n)**0.5 - 1) / 2)
    the_sum = k * (k+1) // 2
    pluck = max(0, the_sum - n)
    return chain(
        range(1, pluck),
        range(pluck+1, k+1))

>>> summands_opt(2**60)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/christophe/python/partition.py", line 17, in summands_opt
    summands = list(range(1, k+1))
MemoryError
>>> for i in summands_iter(2**60): print(i)
# still printing !

[Saurabh Chaturvedi]

Whoa! That was some deep analysis!