Why is Python sort faster than that of C++

Nathan Schmidt

Sorting a list of ints in python 3 seems to be faster than sorting an array of ints in C++. Below is the code for 1 python program and 2 C++ programs that I used for the test. Any reason why the C++ programs are slower? It doesn't make sense to me.

----- Program 1 - python 3.4 -----

from time import time

x = 10000
y = 1000

start = time()

for _ in range(y):
    a = list(range(x))
    a.reverse()
    a.sort()

print(round(time() - start, 2), 'seconds')

----- Program 2 - c++ using sort from algorithm ------

using namespace std;
#include <iostream>
#include <algorithm>

int main(){

    int x = 10000; 
    int y = 1000;
    int b[10000];

    cout << "start" << endl;

    for (int j = 0; j < y; j++){
        for (int i = 0; i < x; i++){
            b[i] = x - i;
        } // still slower than python with this clause taken out

        sort(b, b + x); // regular sort

    }

    cout << "done";
    system("pause");
}

----- Program 3 - c++ using hand written merge sort ------

using namespace std;
#include <iostream>

void merge(int * arr, int *temp, int first_start, int second_start, int      second_finish){

    int a1 = first_start, b1 = second_start, r = 0;

    while (a1 < second_start && b1 < second_finish){

        if (arr[a1] < arr[b1]){
            temp[r] = arr[a1];
            a1++; r++;
        }
        else {
            temp[r] = arr[b1];
            b1++; r++;
        }
    }
    if (a1 < second_start){

        while (a1 < second_start){
            temp[r] = arr[a1];
            a1++; r++;
        }
    }

    else {
        while (b1 < second_finish){
            temp[r] = arr[b1];
            b1++; r++;
        }
    }

    for (int i = first_start; i < second_finish; i++){
        arr[i] = temp[i - first_start];
    }
}

void merge_sort(int *a, int a_len, int *temp){
    int c = 1, start = 0;
    while (c < a_len){
        while (start + c * 2 < a_len){
            merge(a, temp, start, start + c, start + c * 2);
            start += c * 2;
        }
        if (start + c <= a_len){
            merge(a, temp, start, start + c, a_len);
        }
        c *= 2; start = 0;
    } 
}

int main(){

    int x = 10000; // size of array to be sorted
    int y = 1000; // number of times to sort it
    int b[10000], temp[10000]; 

    cout << "start" << endl;

    for (int j = 0; j < y; j++){

        for (int i = 0; i < x; i++){

            b[i] = x - i; // reverse sorted array (even with this assignment taken out still runs slower than python)

        }

        merge_sort(b, x, temp);

    }

    cout << "done";
    system("pause");
}
Alex Martelli

The core reason is no doubt timsort -- http://en.wikipedia.org/wiki/Timsort -- first conceived by Tim Peters for Python though now also in some Java VMs (for non-primitives only).

It's a truly amazing algorithm and you can find a C++ implementation at https://github.com/swenson/sort for example.

Lesson to retain: the proper architecture and algorithms can let you run circles around supposedly-faster languages if the latter are using less-perfect A & As!-) So, if you have really big problems to solve, deal with determining perfect architecture and algorithms first -- the language and optimizations within it are inevitably lower-priority issues.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

Why is Python faster than C++ in this case?

From Dev

Python lists: why is .sort() much faster than sorted()?

From Dev

Why is ''.join() faster than += in Python?

From Dev

Why is ''.join() faster than += in Python?

From Dev

Why is Insertion Sort faster than Bubble Sort and Heap Sort in practice?

From Dev

Why is my computation so much faster in C# than Python

From Dev

Why is C++ much faster than python with boost?

From Dev

Why is an inline if/else faster than a .get() in Python?

From Dev

in python why if rank: is faster than if rank != 0:

From Dev

Why is dict faster than if-else in python?

From Dev

Why is this simple loop faster in Go than in C?

From Dev

Why is my bitmap sort not infintely faster than my mergesort?

From Dev

Why is ArrayList's sort method faster than Arrays' in Java?

From Dev

opencv python is faster than c++?

From Java

Why is [] faster than list()?

From Dev

Why ReferenceEquals() is faster than ==

From Dev

Why is A* faster than Dijkstra

From Dev

why < is much faster than !=?

From Dev

Bucket sort faster than Quicksort

From Dev

Bucket sort faster than Quicksort

From Dev

Why is Insertion Sort faster than Quick Sort when the input size is small?

From Dev

Why is Insertion Sort faster than Quick Sort when the input size is small?

From Dev

Why my C# code is faster than my C code?

From Dev

Why is copying a file in C so much faster than C++?

From Dev

Why is this code so faster in java than in C++ and C#

From Dev

Why is C# running faster than C++?

From Dev

Why is coreutils sort slower than Python?

From Dev

Golang custom sort is faster than native sort

From Dev

Insertion sort much faster than shell sort

Related Related

HotTag

Archive