Why does this algorithm work so much faster in python than in C++? -

i reading "algorithms in c++" robert sedgewick , given exercise: rewrite weigted quick-union path compression halving algorithm in programming language.

the algorithm used check if 2 objects connected, example entry 1 - 2, 2 - 3 , 1 - 3 first 2 entries create new connections whereas in third entry 1 , 3 connected because 3 can reached 1: 1 - 2 - 3, third entry not require creating new connection.

sorry if algorithm description not understandable, english not mother's tongue.

so here algorithm itself:

#include <iostream> #include <ctime>  using namespace std;  static const int n {100000};  int main() {     srand(time(null));      int i;      int j;       int id[n];       int sz[n]; // stores tree sizes      int ncount{}; // counts numbeer of new connections      int mcount{}; // counts number of attempted connections      (i = 0; < n; i++)     {         id[i] = i;         sz[i] = 1;     }      while (ncount < n - 1)     {         = rand() % n;         j = rand() % n;          (; != id[i]; = id[i])             id[i] = id[id[i]];          (; j != id[j]; j = id[j])             id[j] = id[id[j]];          mcount++;          if (i == j) // checks if , j connected              continue;          if (sz[i] < sz[j]) // smaller tree                             // connected bigger 1          {             id[i] = j;             sz[j] += sz[i];         }         else         {             id[j] = i;             sz[i] += sz[j];         }          ncount++;     }      cout << "mcount: " << mcount << endl;     cout << "ncount: " << ncount << endl;      return 0; } 

i know tiny bit of python chose exercise. got:

import random  n = 100000  idlist = list(range(0, n)) sz = [1] * n  ncount = 0 mcount = 0  while ncount < n - 1:      = random.randrange(0, n)     j = random.randrange(0, n)      while not idlist[i]:         idlist[i] = idlist[idlist[i]]         = idlist[i]      while j not idlist[j]:         idlist[j] = idlist[idlist[j]]         j = idlist[j]      mcount += 1      if j:         continue      if sz[i] < sz[j]:         idlist[i] = j         sz[j] += sz[i]     else:         idlist[j] =         sz[i] += sz[j]      ncount += 1  print("mcount: ", mcount) print("ncount: ", ncount)   

but stumbled upon interesting nuance: when set n 100000 or more c++ version version appears lot slower python 1 - took 10 seconds complete task algorithm in python whereas c++ version doing slow had shut down.

so question is: cause of that? happen because of difference in rand() % n , random.randrange(0, n)? or have done wrong?

i'd grateful if explain me, in advance!

those codes different things.

you have compare numbers in python ==.

>>> x=100000 >>> y=100000 >>> x y false 

there might other problems, haven't checked. have compared results of apps?