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:
importmathfrommathimportceil# no dynamic lookup of ceilfromitertoolsimportchaindefsummands(n):k=((1+8*n)**0.5-1)/2k=math.ceil(k)summands=list(range(1,k+1))the_sum=int(k*(k+1)/2)ifthe_sum-n>0:# If n is not senior.delsummands[the_sum-n-1]returnsummandsdefsummands_opt(n):k=ceil(((1+8*n)**0.5-1)/2)the_sum=k*(k+1)//2summands=list(range(1,k+1))ifthe_sum-n>0:# If n is not senior.delsummands[the_sum-n-1]returnsummandsdefsummands_iter(n):k=ceil(((1+8*n)**0.5-1)/2)the_sum=k*(k+1)//2pluck=max(0,the_sum-n)returnlist(chain(range(1,pluck),range(pluck+1,k+1)))defsummands_list(n):k=ceil(((1+8*n)**0.5-1)/2)the_sum=k*(k+1)//2pluck=max(0,the_sum-n)returnlist(range(1,pluck))+list(range(pluck+1,k+1)
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…
However, once removing the casting to list, summands_iter would be the only version that do not cause an overflow for very large numbers :
defsummands_iter(n):k=ceil(((1+8*n)**0.5-1)/2)the_sum=k*(k+1)//2pluck=max(0,the_sum-n)returnchain(range(1,pluck),range(pluck+1,k+1))>>>summands_opt(2**60)Traceback(mostrecentcalllast):File"<stdin>",line1,in<module>File"/home/christophe/python/partition.py",line17,insummands_optsummands=list(range(1,k+1))MemoryError>>>foriinsummands_iter(2**60):print(i)# still printing !
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:
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…
However, once removing the casting to list,
summands_iter
would be the only version that do not cause an overflow for very large numbers :Whoa! That was some deep analysis!