unusual speed difference between python and c++ programs

Question

I wrote same program in C++ and Python. In Python it takes unusual amount of time(Actually I did't get answer in it). Can anybody explain why is that?

C++ code:

#include<iostream>
using namespace std;
int main(){
    int n = 1000000;
    int *solutions = new int[n];
    for (int i = 1; i <= n; i++){
        solutions[i] = 0;
    }

    for (int v = 1; v <= n; v++){
        for (int u = 1; u*v <= n; u++){
             if ((3 * v>u) & (((u + v) % 4) == 0) & (((3 * v - u) % 4) == 0)){
                solutions[u*v]++;
            }
        }
    }
    int count = 0;
    for (int i = 1; i < n; i++){
        if ((solutions[i])==10)
        count += 1;
    }
    cout << count;
}

Python code:

n=1000000
l=[0 for x in range(n+1)]
for u in range(1,n+1):
    v=1
    while u*v<n+1:
         if (((u+v)%4)==0) and (((3*v-u)%4)==0) and (3*v>u):
            l[u*v]+=1
         v+=1

l.count(10)

Iterative code in python tends to be slow because of the interpreter. See: [Why Python is so slow for a simple loop](http://stackoverflow.com/q/8097408/1231929). You should try writing your algorithm using array operations with [numpy](http://www.numpy.org/), or try a JIT compiler like [numba](http://numba.pydata.org/). — jme, Dec 01 '14 at 17:55
In 2.x consider `xrange` rather than `range(1, n+1)`, and I would probably consider making `l` a `dict` (or `collections.Counter`) instead. — jonrsharpe, Dec 01 '14 at 17:56
You have undefined behaviour in the C++ code (make it new int[n+1];) — , Dec 01 '14 at 17:57
...or change the first for loop to `for (int i = 0; i < n; i++)` - right now you're missing the 0th index completely. — Conduit, Dec 01 '14 at 18:02
Also, you forgot to deallocate that int array in the C++ code. You should have `delete[] solutions` at the end of your function. That, or you could use a `std::vector`. — , Dec 01 '14 at 18:03
Try using xrange in your python code. range is not a good option for long lists. — Syed Mauze Rehan, Dec 01 '14 at 18:22
Tip: instead of zeroing loop, just write `int *solutions = new int[n+1]();`. But even better, write `vector solutions(n+1);`. — Cheers and hth. - Alf, Dec 02 '14 at 02:01

score 0 · Answer 1 · answered Dec 01 '14 at 18:11

You can try optimizing this loop, for example make it a single block with no ifs in it, or otherwise use a module in C. C++ compiler does optimalizations Python runtime can't, so with pure interpreter you will never get performance being anything close. And 1M interactions is a lot, I woulnt start with any interpreter in that range, you'd be better doing it in a browser and JavaScript.

unusual speed difference between python and c++ programs

1 Answers1