c++ v.s. python: python的內建自定義排序函數竟比c++的還快速? - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

python程式, 648ms

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        points.sort(key=lambda p: p[0]*p[0]+p[1]*p[1])
        return points[:K]
這個結果十分新奇，難道c++的排序函數比python慢嗎?

於是我自己寫了程式來重現這個效果，

測試的平台都是用repl.it
c++排序程式:
#include <iostream>
#include <vector>
#include <algorithm> // sort()函數
#include <cstdlib> // 亂數相關函數
#include <ctime>   // 時間相關函數
using namespace std;
int main()
    srand( time(NULL) );  /* 設定亂數種子 */
    vector<vector<int>> arr(100000, vector<int>(2));
    for(int i=0; i<arr.size(); i++)
        arr[i][0] = rand();
        arr[i][1] = rand();
    clock_t start, end; // 儲存時間用的變數
    start = clock(); // 計算開始時間
    sort(arr.begin(), arr.end(), [](auto p1, auto p2)
        return (p1[0]*p1[0]+p1[1]*p1[1])< (p2[0]*p2[0]+p2[1]*p2[1]);
    end = clock(); // 計算結束時間
    double cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; // 計算實際花費時間
    cout << "程式執行時間:" << cpu_time_used <<endl;
    return 0;
python的排序程式:
import time
import random
L = [[random.randint(0, 1<<31-1), random.randint(0, 1<<31-1)] for i in range(100000)]
tStart = time.time() #計時開始
L.sort(key=lambda p: p[0]*p[0]+p[1]*p[1])
tEnd = time.time() #計時結束
print(f"程式執行時間= {tEnd - tStart:.4f}秒") #四捨五入到小數點後四位
一測試之後非常驚人，

同樣在陣列裡面放十萬個小陣列，

使用自定義排序的方式，

陣列p[0]*p[0]+p[1]*p[1]的值愈小，排序上愈前面，
c++ 完成排序的時間大約1.2秒
python 完成排序的時間大約0.2秒
c++的排序速度比python慢了數倍以上，

為什麼c++在各方面似乎都比python快，

在自定義的排序上感覺慢這麼多呢?
                        其實qsort可能沒有比c++的sort快哦，
根據geeksforfeeks- C qsort() vs C++ sort()上的資料( https://www.geeksforgeeks.org/c-qsort-vs-c-sort/ )，sort的速度甚至還比qsort來的快
                            看了  https://www.geeksforgeeks.org/c-qsort-vs-c-sort/

其實sort比較快這有盲點,不然不會很多的開源碼都用qsort而不用sort,

且看例中N為100萬, 取亂數時則同餘10萬,看到這樣的問題會有別的作法,

也就是邊排序邊將重複的數字用count的方式計數...

可以試試若是每新增一個數字就排序好數列,哪個會比較快?

而大多數實際的應用通常是維持一個排序好的表便於快搜,

所以一邊新增就要同時重新排序好,

這時新增的插入方式又會有不同作法,那麼效率又會大有不同

qsort傳指標,不會有傳參考還是傳值的誤用,

即便傳參考於不同的編譯方式下可能是傳址或複製結構的作法又會不同,

所以端看用甚麼角度來瞧這樣的一個癥結點吧!
                        看了  https://www.geeksforgeeks.org/c-qsort-vs-c-sort/
其實sort比較快這有盲點,不然不會很多的開源碼都用qsort而不用sort,
且看例中N為100萬, 取亂數時則同餘10萬,看到這樣的問題會有別的作法,
也就是邊排序邊將重複的數字用count的方式計數...
可以試試若是每新增一個數字就排序好數列,哪個會比較快?
而大多數實際的應用通常是維持一個排序好的表便於快搜,
所以一邊新增就要同時重新排序好,
這時新增的插入方式又會有不同作法,那麼效率又會大有不同
qsort傳指標,不會有傳參考還是傳值的誤用,
即便傳參考於不同的編譯方式下可能是傳址或複製結構的作法又會不同,
所以端看用甚麼角度來瞧這樣的一個癥結點吧!
bool compare(vector<int> &p1, vector<int> &p2)
    return (p1[0]*p1[0]+p1[1]*p1[1]) < (p2[0]*p2[0]+p2[1]*p2[1]);
int main()
    srand( time(NULL) );  /* 設定亂數種子 */
    vector<vector<int>> arr(100000, vector<int>(2));
    for(int i=0; i<arr.size(); i++)
        arr[i][0] = rand();
        arr[i][1] = rand();
    clock_t start, end; // 儲存時間用的變數
    start = clock(); // 計算開始時間
    sort(arr.begin(), arr.end(), compare);
    end = clock(); // 計算結束時間
    double cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; // 計算實際花費時間
    cout << "程式執行時間:" << cpu_time_used <<endl;
    return 0;
    static bool compare(vector<int> &p1, vector<int> &p2)
        return (p1[0]*p1[0]+p1[1]*p1[1]) < (p2[0]*p2[0]+p2[1]*p2[1]);
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        sort(points.begin(), points.end(), compare);
        return {points.begin(), points.begin()+K};
    static bool compare(vector<int> &p1, vector<int> &p2)
        return (p1[0]*p1[0]+p1[1]*p1[1]) < (p2[0]*p2[0]+p2[1]*p2[1]);
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        sort(points.begin(), points.end(), compare);
        return {points.begin(), points.begin()+K};
sort(arr.begin(), arr.end(), [](auto &p1, auto &p2)
    return (p1[0]*p1[0]+p1[1]*p1[1])< (p2[0]*p2[0]+p2[1]*p2[1]);
sort(arr.begin(), arr.end(), [](auto &p1, auto &p2)
    return (p1[0]*p1[0]+p1[1]*p1[1])< (p2[0]*p2[0]+p2[1]*p2[1]);
不太可能 Python 的優化和 C++ 差這麼多
如果真的是這樣 C++ 就要好好檢討了
![/images/emoticon/emoticon16.gif](/images/emoticon/emoticon16.gif)
跟演算法本身與lambda無關，
太感謝您了~
![/images/emoticon/emoticon32.gif](/images/emoticon/emoticon32.gif)
                        看了[一級屠豬士](/users/20050647)大大的 Timsort
我去 Google 了 C++ 的 [Introsort](https://en.wikipedia.org/wiki/Introsort)
bool compare(vector<int> &p1, vector<int> &p2)
    return (p1[0]*p1[0]+p1[1]*p1[1]) < (p2[0]*p2[0]+p2[1]*p2[1]);
int main()
    srand( time(NULL) );  /* 設定亂數種子 */
    vector<vector<int>> arr(100000, vector<int>(2));
    for(int i=0; i<arr.size(); i++)
        arr[i][0] = rand();
        arr[i][1] = rand();
    clock_t start, end; // 儲存時間用的變數
    start = clock(); // 計算開始時間
    sort(arr.begin(), arr.end(), compare);
    end = clock(); // 計算結束時間
    double cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; // 計算實際花費時間
    cout << "程式執行時間:" << cpu_time_used <<endl;
    return 0;
bool compare(vector<int> &p1, vector<int> &p2)
    return (p1[0]*p1[0]+p1[1]*p1[1]) < (p2[0]*p2[0]+p2[1]*p2[1]);
int main()
    srand( time(NULL) );  /* 設定亂數種子 */
    vector<vector<int>> arr(100000, vector<int>(2));
    for(int i=0; i<arr.size(); i++)
        arr[i][0] = rand();
        arr[i][1] = rand();
    clock_t start, end; // 儲存時間用的變數
    start = clock(); // 計算開始時間
    sort(arr.begin(), arr.end(), compare);
    end = clock(); // 計算結束時間
    double cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; // 計算實際花費時間
    cout << "程式執行時間:" << cpu_time_used <<endl;
    return 0;