Profiling of a python function

Question

Do you have any idea of how can I make this function more time-efficient?

def c(n):
 word = 32
 #l = []
 c = 0
 for i in range(0, 2**word):
 #print(str(bin(i)))#.count('1')
 if str(bin(i)).count('1') == n:
 c = c + 1 
 print(c)
 if i == 2**28:
 print('6 %')
 if i == 2**29:
 print('12 %')
 if i == 2**30:
 print('25 %')
 if i == 2**31:
 print('50 %')
 if i == 2**32:
 print('100 %')
 return c
135274023 function calls in 742.161 seconds
 Ordered by: standard name
 ncalls tottime percall cumtime percall filename:lineno(function)
 1 391.662 391.662 742.161 742.161 <pyshell#3>:1(c)
 1 0.000 0.000 742.161 742.161 <string>:1(<module>)
 4816 0.014 0.000 0.014 0.000 rpc.py:149(debug)
 688 0.010 0.000 3.162 0.005 rpc.py:208(remotecall)
 688 0.017 0.000 0.107 0.000 rpc.py:218(asynccall)
 688 0.019 0.000 3.043 0.004 rpc.py:238(asyncreturn)
 688 0.002 0.000 0.002 0.000 rpc.py:244(decoderesponse)
 688 0.007 0.000 3.018 0.004 rpc.py:279(getresponse)
 688 0.006 0.000 0.010 0.000 rpc.py:287(_proxify)
 688 0.025 0.000 3.000 0.004 rpc.py:295(_getresponse)
 688 0.002 0.000 0.002 0.000 rpc.py:317(newseq)
 688 0.023 0.000 0.062 0.000 rpc.py:321(putmessage)
 688 0.007 0.000 0.011 0.000 rpc.py:546(__getattr__)
 688 0.002 0.000 0.002 0.000 rpc.py:587(__init__)
 688 0.004 0.000 3.166 0.005 rpc.py:592(__call__)
 1376 0.008 0.000 0.011 0.000 threading.py:1012(current_thread)
 688 0.004 0.000 0.019 0.000 threading.py:172(Condition)
 688 0.009 0.000 0.015 0.000 threading.py:177(__init__)
 688 0.019 0.000 2.962 0.004 threading.py:226(wait)
 688 0.002 0.000 0.002 0.000 threading.py:45(__init__)
 688 0.002 0.000 0.002 0.000 threading.py:50(_note)
 688 0.004 0.000 0.004 0.000 threading.py:88(RLock)
 688 0.004 0.000 0.004 0.000 {built-in method allocate_lock}
 67620326 162.442 0.000 162.442 0.000 {built-in method bin}
 688 0.007 0.000 0.007 0.000 {built-in method dumps}
 1 0.000 0.000 742.161 742.161 {built-in method exec}
 1376 0.003 0.000 0.003 0.000 {built-in method get_ident}
 1376 0.004 0.000 0.004 0.000 {built-in method isinstance}
 2064 0.005 0.000 0.005 0.000 {built-in method len}
 688 0.002 0.000 0.002 0.000 {built-in method pack}
 344 0.009 0.000 3.187 0.009 {built-in method print}
 688 0.008 0.000 0.008 0.000 {built-in method select}
 688 0.003 0.000 0.003 0.000 {method '_acquire_restore' of '_thread.RLock' objects}
 688 0.002 0.000 0.002 0.000 {method '_is_owned' of '_thread.RLock' objects}
 688 0.002 0.000 0.002 0.000 {method '_release_save' of '_thread.RLock' objects}
 688 0.003 0.000 0.003 0.000 {method 'acquire' of '_thread.RLock' objects}
 1376 2.929 0.002 2.929 0.002 {method 'acquire' of '_thread.lock' objects}
 688 0.002 0.000 0.002 0.000 {method 'append' of 'list' objects}
 67620325 184.869 0.000 184.869 0.000 {method 'count' of 'str' objects}
 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
 688 0.002 0.000 0.002 0.000 {method 'get' of 'dict' objects}
 688 0.002 0.000 0.002 0.000 {method 'release' of '_thread.RLock' objects}
 688 0.015 0.000 0.015 0.000 {method 'send' of '_socket.socket' objects}

What I try to achieve is to calculate how many of numbers from 0 to 2**32 have n number of 1 in their binary representation.

• Lauritz V. Thaulow: Perhaps this is of interest: stackoverflow.com/questions/1851134/…

Answer 1

You are counting how many 32-bit numbers have a given number of 1s. This number is the binomial coefficient 32 choose bits, and can be calculated with:

from math import factorial
print factorial(32) // (factorial(bits) * factorial(32-bits))

• Vladimir Keleshev: oh, my! that's a piece of cake!
• Lauritz V. Thaulow: Where's clippy when you need him? "It looks like you're trying to calculate the binomial coefficient..."