Rolling median solution

I was implementing a rolling median solution and was not sure why my Python implementation was around 40 times slower than my C++ implementation.

Here are the complete implementations:
C++
#include
#include
#include
using namespace std;

int tree[17][65536];

void insert(int x) { for (int i=0; i temperatures;
temperatures.push_back( seed );
for (int i=1; i=K) erase(temperatures[i-K]);
if (i>=K-1) result += kThElement( (K+1)/2 );
}
return result;
}

// default input
// 47 5621 1 125000 1700
// output
// 4040137193

int main()
{
int seed,mul,add,N,K;
cin >> seed >> mul >> add >> N >> K;
cout
Python
def insert(tree,levels,n):
for i in xrange(levels):
tree[i][n] += 1
n /= 2
def delete(tree,levels,n):
for i in xrange(levels):
tree[i][n] -= 1
n /= 2

def kthElem(tree,levels,k):
a = 0
for b in reversed(xrange(levels)):
a *= 2
if tree[b][a] = K):
delete(tree,levels,temps[i-K])
if (i >= K-1):
result += kthElem(tree,levels,((K+1)/2))

print result

# default input
# 47 5621 1 125000 1700
# output
# 4040137193
main()
`

On the above mentioned input (in the comments of the code), the C++ code took around 0.06 seconds while Python took around 2.3 seconds.

Can some one suggest the possible problems with my Python code and how to improve to less than 10x performance hit?

I don't expect it to be anywhere near C++ implementation but to the order of 5-10x. I know I can optimize this by using libraries like NumPy (and/or SciPy). I am asking this question from the point of view of using Python for solving programming challenges. These libraries are usually not allowed in these challenges. I am just asking if it is even possible to beat th

Integer math in tight loops is an area where C++ will definitely run circles around Python. I think your expectations are too high. However, I'd like to point out a couple of things for you, even if they are not enough to reach your goal.

Avoid indexing when you can use direct iteration instead. For example, insert can be written like this and Python won't have to deal with i:

def insert(tree,n):
     for level in tree:
         level[n] += 1
         n /= 2

Python does not optimize constant subexpressions out of loops, so you'll want to compute (K+1)/2 before the main loop and store it in a variable.

StackExchange Code Review Q#35530, answer score: 7