Почему Python сортируется быстрее, чем у C++

Question

Сортировка списка int в python 3, по-видимому, быстрее, чем сортировка массива int в C++. Ниже приведен код для 1 программы python и 2 C++-программ, которые я использовал для теста. Любая причина, по которой программы на C++ медленнее? Это не имеет смысла для меня.

----- Программа 1 - питон 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') 

----- Программа 2 - C++ с использованием своего рода из алгоритма ------

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"); 
} 

----- Программа 3 - C++ с использованием рукописной сортировки слияния ------

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"); 
} 

Answer 1

основной причиной нет сомнений timsort - http://en.wikipedia.org/wiki/Timsort - впервые задуман Тимом Петерсом для Python, хотя теперь также на некоторых виртуальных машинах Java (только для не примитивов).

Это поистине удивительный алгоритм, и вы можете найти реализацию на C++, например, в https://github.com/swenson/sort.

Урок сохранить: правильный архитектуры и алгоритмы могут позволить вам работать круги вокруг якобы-быстрее языков если последний используется менее совершеннее & As -) Так что, если у вас есть действительно большой! проблемы, которые необходимо решить, прежде всего, решать вопросы определения совершенной архитектуры и алгоритмов - язык и оптимизация внутри него неизбежно являются проблемами с более низким приоритетом.