loading...

re: Another Way to Find Max Partitions VIEW POST

TOP OF THREAD FULL DISCUSSION
re: Awesome! Now this is some production-quality code! Thanks for adding readability to the code as well.

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())

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 !

Whoa! That was some deep analysis!

Code of Conduct Report abuse