iT邦幫忙

1

c++ v.s. python: python的內建自定義排序函數竟比c++的還快速? #保證給最佳解答

哈囉~ 大家好,
我發現iT邦幫忙的問答區非常多人是不給最佳解答的,
我覺得這樣並不是很好,
有些發問者回答的盡心盡力,
應該給予「最佳解答」表達基本的感謝與鼓勵

因此在發問前,
我先保證只要有人回答,
哪怕是回答隻字片語或提供想法,
我一周內一定會給出「最佳解答」

問題描述

一般來說,我們對於c++和python的印象是,
c++的程式執行速度較快,python的程式執行速度較慢,
小馬在leetcode上刷題百題以上,
也幾乎都是這樣的結論

但有一天,我在leetcode上刷到一題跟「排序」相關的問題
(973. K Closest Points to Origin)
同樣使用內建的排序函數,
做完之後卻發現c++比python還慢了2倍以上

補充: 附上我在leetcode上的解法

c++程式, 1476ms

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        sort(points.begin(), points.end(), [](auto p1, auto p2){
            return (p1[0]*p1[0]+p1[1]*p1[1])< (p2[0]*p2[0]+p2[1]*p2[1]);});
        return {points.begin(), points.begin()+K};
    }
};

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快,
在自定義的排序上感覺慢這麼多呢?
有人知道原因嗎?(或者可能我測試的方式不對?)

wwx iT邦好手 1 級 ‧ 2020-05-31 12:11:48 檢舉
不要用sort()/vectory改用qsort()/array
因為Python的排序是用c/c++的qsort寫的,
並不是python快, 而是如何使用c/c++的作法差異
其實qsort可能沒有比c++的sort快哦,
根據geeksforfeeks- C qsort() vs C++ sort()上的資料( https://www.geeksforgeeks.org/c-qsort-vs-c-sort/ ),sort的速度甚至還比qsort來的快
wwx iT邦好手 1 級 ‧ 2020-06-11 15:04:28 檢舉
看了 https://www.geeksforgeeks.org/c-qsort-vs-c-sort/
其實sort比較快這有盲點,不然不會很多的開源碼都用qsort而不用sort,
且看例中N為100萬, 取亂數時則同餘10萬,看到這樣的問題會有別的作法,
也就是邊排序邊將重複的數字用count的方式計數...
可以試試若是每新增一個數字就排序好數列,哪個會比較快?

而大多數實際的應用通常是維持一個排序好的表便於快搜,
所以一邊新增就要同時重新排序好,
這時新增的插入方式又會有不同作法,那麼效率又會大有不同

qsort傳指標,不會有傳參考還是傳值的誤用,
即便傳參考於不同的編譯方式下可能是傳址或複製結構的作法又會不同,
所以端看用甚麼角度來瞧這樣的一個癥結點吧!
3
小碼農米爾 Mir
iT邦研究生 1 級 ‧ 2020-05-31 13:29:18
最佳解答

看了一級屠豬士的 Timsort
和海綿寶寶的 Introsort
我去 Google 了時間複雜度
兩者最壞都是 O(n log n)
感覺起來應該是差不多的速度

我把 lambda 改成一般的函數
時間就和 python 差不多
可能 C++ 對 lambda 的優化沒有很好

#include <iostream>
#include <vector>
#include <algorithm> // sort()函數
#include <cstdlib> // 亂數相關函數
#include <ctime>   // 時間相關函數

using namespace std;

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;
}
看更多先前的回應...收起先前的回應...

謝謝解答,很實用~
我將leetcode上的解改為一般的函數,
而不直接用lambda,
速度就比python還快了,
修改後的解:

class Solution {
    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};
    }
};

我又測了一下
發現問題好像不是出在 lambda 身上
應該是 參數複製 的問題
我把 p1、p2 都改成傳址
速度就變快了

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 也是用 lambda
怎麼會沒有效能損耗
不太可能 Python 的優化和 C++ 差這麼多
如果真的是這樣 C++ 就要好好檢討了
/images/emoticon/emoticon16.gif

對耶~ 你說的非常好,
我忽略這個基礎的點了,
是call by reference(傳址)的問題,
跟演算法本身與lambda無關,
太感謝您了~
/images/emoticon/emoticon32.gif

/images/emoticon/emoticon41.gif

1
一級屠豬士
iT邦大師 1 級 ‧ 2020-05-30 22:08:09

https://en.wikipedia.org/wiki/Timsort

另外你C++應該用編譯的, 啟用最佳化參數.

這也不是解答,只是一些線索,希望你能多加探索.

看更多先前的回應...收起先前的回應...

看了一級屠豬士大大的 Timsort
我去 Google 了 C++ 的 Introsort

看了一級屠豬士的 Timsort
和海綿寶寶的 Introsort
我去 Google 了時間複雜度
兩者最壞都是 O(n log n)
感覺起來應該是差不多的速度

我把 lambda 改成一般的函數
時間就和 python 差不多
可能 C++ 對 lambda 的優化沒有很好

#include <iostream>
#include <vector>
#include <algorithm> // sort()函數
#include <cstdlib> // 亂數相關函數
#include <ctime>   // 時間相關函數

using namespace std;

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;
}
echochio iT邦高手 1 級 ‧ 2020-05-31 04:40:21 檢舉

我猜也是 lambda 的原因 .....

嗨~ fysh711426 邦友您好,感謝你的分享討論,我覺得你的意見蠻好的,歡迎可直接回答

1
小魚
iT邦大師 1 級 ‧ 2020-05-31 12:28:04

這句話是錯的

C++的程式執行速度較快 

正確的說法應該是

會寫C++的人, C++的程式執行速度較快

可惜的是99%寫C++的人都是不會寫C++的人,
包括我.

而且你用的函式是C++ 11的函式,
那已經是比較後期,
改得比較高階的C++了,
高階語言的特性就是 上手的容易度 > 程式的效率,
當然魚跟熊掌兩個都能兼得是最好,
但是常常是不能兼得的.

謝謝您的留言回答 ^^,
現在大概知道原因出在lambda了~

更正: 已發現是原本寫lambda函式沒有call by reference的問題,與lambda無關,目前已解決。
不論如何還是非常感謝小魚大大的回答 ^^

我要發表回答

立即登入回答