討論區快速選單
知識庫快速選單
程式設計俱樂部Facebook粉絲團 掌握Salesforce雲端管理秘訣
[ 回上頁 ] [ 討論區發言規則 ]
排序法 時間複雜度 速度問題
更改我的閱讀文章字型大小
作者 : x890311x(腦殘)
[ 貼文 5 | 人氣 0 | 評價 0 | 評價/貼文 0 | 送出評價 2 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/6 上午 12:22:43
最近學到快速排序法
時間複雜度是 n log n
但是我很好奇為啥 快速排序法裡有用到 遞迴 還會比其他 n_2 的排序法快 (以平均來講

有用到遞迴的程式 數據量大的時候不是比較慢嗎?
作者 : ice_emissary(燃燒的大地) 貼文超過200則
[ 貼文 386 | 人氣 0 | 評價 1770 | 評價/貼文 4.59 | 送出評價 17 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/6 上午 08:41:02
遞迴,慢是慢在程式呼叫,而不是使用它的演算法本身。
遞迴,數據量大不大無關緊要,通常是呼叫的「層深」會導致問題;
慢還不是最嚴重的,嚴重的是會讓堆疊爆掉!

快速排序法裡面使用了遞迴來描述,是因為使用遞迴描述比較能夠簡單清晰的說明演算法本身,畢竟這也是遞迴的主要用處之一。
但這不表示你在演算法實做的時候也必須要用遞迴,事實上絕大部分的遞迴算法可以被改寫為迴圈形式。
寫成迴圈後程式碼可能會變繁雜一些,不過單一演算法的實做本來就極度追求最佳化嘛!

最後簡單說明一些遞迴造成問題的原因關鍵字,讓你有興趣可以去搜尋更多內容。
遞迴會慢,是因為每一次的函式呼叫本身都有開銷,如暫存器狀態備份、參數推堆疊、程式跳轉與跳回等等。
每一次遞迴都是函式戶叫,當呼叫層數多了,能不慢嗎?
每一次函式呼叫都必須要把一些資訊推到堆疊裡保存,直到函式執行完畢返回時才把它銷毀。
而遞迴呼叫的函式就是一層又一層的呼叫下去,以致堆疊內會累積大量資料,全部要等到最深的那一層返回時才能釋放,
那你說當呼叫層深夠多的時候,堆疊會爆一點都不易外對吧!
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/6 下午 03:13:32
這裡補充 燃燒的大地 所說的遞廻和廻圈這一部份

因遞廻會有爆掉堆疊的危險,所以若有可能盡可能用廻圈,但是不是可以用廻圈取決於關鍵變數,在一個廻圈後是不是須要保留其值,若不須要則可以重設其值,進行下一個廻圈的運行

以下用快速排序法做進一步的說明,先說它的改良法是青衫教的,我一直銘記在心

因快速排序法運行一個回合後會由定位點分割成左右兩部份,若要重設關鍵變數再處理左邊部份,右邊就失去關鍵變數沒法處理,反過來做亦相同,因此就讓較短的那邊用遞廻,長的那邊用廻圈

先看正常版的快速排序法長這樣:

template <typename T>
void QuickSort(vector<T> &Arr, size_t Left, size_t Right)
{
 if (Left < Right)
 {
  size_t i = Left, j = Right + 1;
  while (true)
  {
   while (i < j && Arr[++i] < Arr[Left]);
   while (Left < j && Arr[--j] >= Arr[Left]);
   if (i >= j)
    break;
   Swap(Arr, i, j);
  }
  Swap(Arr, Left, j);
  QuickSort(Arr, Left, j);
  QuickSort(Arr, j+1, Right);
 }
}

以下為改良版:

template <typename T>
void QuickSort2(vector<T> &Arr, size_t Left, size_t Right)
{
 while (Left < Right)
 {
  size_t i = Left, j = Right + 1;
  while (true)
  {
   while (i < j && Arr[++i] < Arr[Left]);
   while (Left < j && Arr[--j] >= Arr[Left]);
   if (i >= j)
    break;
   Swap(Arr, i, j);
  }

  Swap(Arr, Left, j);

  if (j > (Left + Right) / 2)
  {
   QuickSort(Arr, j + 1, Right);
   Right = j;
  }
  else
  {
   QuickSort(Arr, Left, j);
   Left = j + 1;
  } 
 }
}

這樣可以保證遞廻的堆疊使用量不超過 log2(n),不會爆掉堆疊,因資料量會先爆掉

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/6 下午 03:18:07
測試碼

#include <iostream>
#include <vector>

using namespace std;


template <typename T>
void Swap(vector<T> &Arr, size_t i, size_t j)
{
 T tmp = Arr[i];
 Arr[i] = Arr[j];
 Arr[j] = tmp;
}

template <typename T>
void Show(vector<T> &Arr)
{
 size_t Size = Arr.size();
 size_t i = 0;
 while (i < Size)
  cout << Arr[i++] << " ";
 cout << endl;
}

int main()
{
 vector<int> v{ 74,15,97,24,67,30,92,94,14,55,74 };

 Show(v);
 QuickSort2(v, 0, v.size() - 1);
 Show(v);

 return 0;
}

作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/6 下午 06:58:14
Arr... 遞迴 不過就是 用懶散方式寫 for loop 或是 while loop 而已. 沒有只能用遞迴 而不能用for loop或while loop再現 的程序的. 別傻了.
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/6 下午 08:08:19

>Arr... 遞迴 不過就是 用懶散方式寫 for loop 或是 while loop 而已. 沒有只能用遞迴 而不能用for loop或while loop再現 的程序的. 別傻了.

有一個變種的方法,就是做個資料堆疊,可以推入推出關鍵變數,不過這和遞廻的意思一樣,還不如直接用遞廻意思容易明瞭
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/6 下午 09:47:56
>
>>Arr... 遞迴 不過就是 用懶散方式寫 for loop 或是 while loop 而已. 沒有只能用遞迴 而不能用for loop或while loop再現 的程序的. 別傻了.
>
>有一個變種的方法,就是做個資料堆疊,可以推入推出關鍵變數,不過這和遞廻的意思一樣,還不如直接用遞廻意思容易明瞭
>

@@? 你是否在說 "你所述的應用, 只能用遞迴去寫, 而不能用for loop或while loop再現"?
如果有這麼一個應用, 真的要指教一下, 讓我長一下見識.
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/6 下午 09:58:30
^o^y--~~ocC, 準確地說一次吧, 遞迴的機制, 只是個歷史包袱. 它還存在的句法裡的意義, 只單純為了兼容古代遺留下來的原碼而已.

遞迴 不過就是 用懶散方式寫 for loop 或是 while loop 而已. 如此... 這般... 總之, 遞迴的問題大多, 是萬萬不能用.
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/6 下午 11:42:06

你有辦法讓 QuickSort 不用保存關鍵變數我就服了你
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/7 上午 06:48:02
#include <stdio.h>

#include <vector>
using namespace std;

template <typename T> inline void g_swap( T &a, T &b ){ T c; c = a; a = b; b = c; }

template <typename T>
int* my_quicksort( const T *val, int n, bool ascending=true )
{
  if( n<=0 )
    return NULL;
  vector<int> gs;
  int low, high, l, h, *idx;
  T sv;

  idx = (int*) malloc( n*sizeof(int) );
  for( l=0; l<n; l++ )
    idx[l] = l;

  gs.push_back(0);
  gs.push_back(n-1);
  while( gs.size() )
  {
    high=gs.back(); gs.pop_back();
    low =gs.back(); gs.pop_back();
    sv = val[idx[high]];

    if(ascending)
    {
     for( l=low, h=low; h<high; h++ )
     if( val[idx[h]]<sv || (val[idx[h]]==sv && idx[h]<idx[high]) )
     g_swap( idx[l++], idx[h] );
    }else
{
     for( l=low, h=low; h<high; h++ )
     if( val[idx[h]]>sv || (val[idx[h]]==sv && idx[h]<idx[high]) )
     g_swap( idx[l++], idx[h] );
    }
    g_swap(idx[l],idx[h]);
    
    if( low < l-1 )
    {
     gs.push_back(low);
     gs.push_back(l-1);
    }
    if( l+1 < high )
    {
     gs.push_back(l+1);
     gs.push_back(high);
    }
  }
  return idx;
}

void main()
{
  int dat[] = {74,15,97,24,67,30,92,94,14,55,74};
  int *idx = my_quicksort( dat, sizeof(dat)/sizeof(dat[0]) );
  int i;
  for( i=0; i<sizeof(dat)/sizeof(dat[0]); i++ )
    printf( "%i ", dat[idx[i]] );
  printf( "\n" );
  free(idx);
}
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/7 上午 07:09:39
>
>你有辦法讓 QuickSort 不用保存關鍵變數我就服了你

上面的quicksort, 是我很久以前隨手編的剩餘物資, 這沒用遞迴呀. @@? 有何不可?

不知道你說的 "關鍵變數" 是在指啥, 不過, 不用解釋了, 前提是在討論遞迴呢...

說不定... 你還想再從理論角度, 把遞迴的定義擴充到包括我貼的原碼.
預先答一下吧, C++裡的遞迴, 是實作的遞迴, 不是廣義的遞迴.
這裡是C++討論區, 我們討論實作吧. 另外, 就算是從理論角度討論,
遞迴 也不見得是 quicksort的唯一表達描述方式.
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/7 上午 09:02:39

>>
>>你有辦法讓 QuickSort 不用保存關鍵變數我就服了你
>
>上面的quicksort, 是我很久以前隨手編的剩餘物資, 這沒用遞迴呀. @@? 有何不可?
>
>不知道你說的 '關鍵變數' 是在指啥, 不過, 不用解釋了, 前提是在討論遞迴呢...
>
>說不定... 你還想再從理論角度, 把遞迴的定義擴充到包括我貼的原碼.
>預先答一下吧, C++裡的遞迴, 是實作的遞迴, 不是廣義的遞迴.
>這裡是C++討論區, 我們討論實作吧. 另外, 就算是從理論角度討論,
>遞迴 也不見得是 quicksort的唯一表達描述方式.

有沒有發現你程式中的 vector<int> gs 就是在保存關鍵變數值,遞廻做的就是和 vector<int> gs 一樣,若你擔心遞廻會爆掉堆疊,gs 也有可能會爆掉,若你擔心遞廻會拖慢速度,gs 的推入推出也須要花時間的,還不如優化演算法,減少關鍵變數的保存動作,就像以上那個改良版的 QuickSort2(),沒仔細看你的程式碼,不使用遞廻演算法會變得更繁雜,要改良也更不容易



作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/7 下午 03:10:11
遞迴 會給你 stack overflow,
vector 不會。遞迴由編譯器代你管理, 過程編程人員是被完全屏蔽,難以除錯;vector 是 dynamic array,除錯容易。對vector進行記憶體管理,就單純是查一下數目,遞迴不能。... 總之呢... 遞迴不可用,vector可以。還有,vector 並不是遞迴,vector 是 template class,原碼查一下表頭檔就有。還是妄想vector用了遞迴的話,自己查一下呀 。



作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/7 下午 11:31:02
我不相信 vector 是無底洞塞不滿,就以它會被塞滿為前提,你有辦法優化你的程式碼讓它絕對不會被塞滿嗎?就像我提供的 QuickSort2() 一樣
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/8 上午 12:54:22
>我不相信 vector 是無底洞塞不滿,就以它會被塞滿為前提,你有辦法優化你的程式碼讓它絕對不會被塞滿嗎?就像我提供的 QuickSort2() 一樣

Arr... 錯得這麼乾脆啊, 害我連吐糟也有點於心不忍了.

vector 是 dynamic array, 它能處理的資料大小上限, 取決於主記憶體大小. 現在的PC, 主記憶體少說也有 8GB 到 16GB, 沒犯大錯的話, 處理 幾個GB 只是小事一件. 再糟再糟, 也不會好像 call stack 一樣, 幾MB 就完旦的.

另外, 用編譯器提供的遞迴, 程式會跑得超慢的 (相比起自己去做管理的話). 這是常識吧.

用編譯器提供的遞迴, 是 除錯難 速度慢 記憶體用量不必要地多 + stack overflow 迫在眉睫. @@" 這麼多壞處啊... 難道就沒有好處嗎? 這... 沒有的 (就連遞迴的靈活簡潔也是壞處; 編程式 除錯容易優先, 除錯難是大忌); 所以我一開始就在說 不要用遞迴 呀.

你幹啥呀? 你東併西湊 含辛茹苦, 也要堅持去用破爛啊. 你... 你... 你這又是何苦呢? 嗚呼... 哀哉...
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/8 下午 12:45:43

QuickSort2() 的堆疊使用深度是以 log2(n) 計算,所以若有 1T 個資料元素給它處理,最多不超過 40 層的遞廻

QuickSort2 的宣告長這樣

   QuickSort2(vector<T> &Arr, size_t Left, size_t Right)

若真如你說的 vector 它能處理的資料大小上限, 取決於主記憶體大小,就當 Arr 含有所有可用的記憶體大小好了,對 QuickSort2 來說只是小菜一碟,但若給你的程式處理,才邁開第一步就爆了,因沒有記憶體可以給你的 gs 使用了

遞廻不過就是函數的呼叫,據我所知 CPU 對函數的呼叫是有支援的,所以也花不了多少時間。但若真如你所說 vector 是 dynamic array,你認為誰比較花時間


>用編譯器提供的遞迴, 是 除錯難 速度慢 記憶體用量不必要地多 + stack overflow 迫在眉睫. @@' 這麼多壞處啊... 難道就沒有好處嗎? 這... 沒有的 (就連遞迴的靈活簡潔也是壞處; 編程式 除錯容易優先, 除錯難是大忌); 所以我一開始就在說 不要用遞迴 呀.

引用最近看到的佳言 "你想象力太好了,就喜歡看看不懂的"

>
>你幹啥呀? 你東併西湊 含辛茹苦, 也要堅持去用破爛啊. 你... 你... 你這又是何苦呢? 嗚呼... 哀哉...

借花獻佛,全數奉還
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/8 下午 02:32:22

>
>QuickSort2() 的堆疊使用深度是以 log2(n) 計算,所以若有 1T 個資料元素給它處理,最多不超過 40 層的遞廻
>
>QuickSort2 的宣告長這樣
>
> QuickSort2(vector<T> &Arr, size_t Left, size_t Right)
>
>若真如你說的 vector 它能處理的資料大小上限, 取決於主記憶體大小,就當 Arr 含有所有可用的記憶體大小好了,對 QuickSort2 來說只是小菜一碟,但若給你的程式處理,才邁開第一步就爆了,因沒有記憶體可以給你的 gs 使用了
>
>遞廻不過就是函數的呼叫,據我所知 CPU 對函數的呼叫是有支援的,所以也花不了多少時間。但若真如你所說 vector 是 dynamic array,你認為誰比較花時間
>
>
>>用編譯器提供的遞迴, 是 除錯難 速度慢 記憶體用量不必要地多 + stack overflow 迫在眉睫. @@' 這麼多壞處啊... 難道就沒有好處嗎? 這... 沒有的 (就連遞迴的靈活簡潔也是壞處; 編程式 除錯容易優先, 除錯難是大忌); 所以我一開始就在說 不要用遞迴 呀.
>
>引用最近看到的佳言 '你想象力太好了,就喜歡看看不懂的'
>
>>
>>你幹啥呀? 你東併西湊 含辛茹苦, 也要堅持去用破爛啊. 你... 你... 你這又是何苦呢? 嗚呼... 哀哉...
>
>借花獻佛,全數奉還

教而不善的孩子呀,只嘴上呈強,意義何在?互聯網這麼方便,Google 一下就可引證我說的呀。連Google一也不做,然後躲在小坑裡稱王啊。唉... 我沒興趣教孩子,編程無關的,就不再回覆你了。
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/8 下午 09:43:51

修改一下
須要保存的關鍵變數只有 j,
但參數 Arr Left Right 也會被保存,這算是遞廻的副作用

template <typename T>
void QuickSort2(vector<T> &Arr, size_t Left, size_t Right)
{
 while (Left < Right)
 {
  size_t j = Right + 1;

  {
   // 把 i 放著,是因不是關鍵變數,不須保存
   size_t i = Left;
   while (true)
   {
    while (i < j && Arr[++i] < Arr[Left]);
    while (Left < j && Arr[--j] >= Arr[Left]);
    if (i >= j)
     break;
    Swap(Arr, i, j);
   }
  }

  Swap(Arr, Left, j);

  if (j > (Left + Right) / 2)
  {
   QuickSort2(Arr, j + 1, Right);
   Right = j;
  }
  else
  {
   QuickSort2(Arr, Left, j);
   Left = j + 1;
  } 
 }
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/9 上午 11:48:19
>須要保存的關鍵變數只有 j,
>但參數 Arr Left Right 也會被保存,這算是遞廻的副作用

後來想想,Left Right 也是不可或缺,Arr 倒是可以不用一直作遞廻參數,所以改成以下 class 會比較好

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
class QuickSort
{
 vector<T> &m_Arr;

 void Swap(size_t i, size_t j)
 {
  T tmp = m_Arr[i];
  m_Arr[i] = m_Arr[j];
  m_Arr[j] = tmp;
 }

 void SortRecursive(size_t Left, size_t Right)
 {
  while (Left < Right)
  {
   size_t j = Right + 1;
   {
    size_t i = Left;
    while (true)
    {
     while (i < j && m_Arr[++i] < m_Arr[Left]);
     while (Left < j && m_Arr[--j] >= m_Arr[Left]);
     if (i >= j)
      break;
     Swap(i, j);
    }
   }

   Swap(Left, j);

   if (j >(Left + Right) / 2)
   {
    SortRecursive(j + 1, Right);
    Right = j;
   }
   else
   {
    SortRecursive(Left, j);
    Left = j + 1;
   }
  }
 }

 // Constructor
 QuickSort(vector<T> &Arr)
  :m_Arr(Arr)
 {

 }

public:

 static void Sort(vector<T> &Arr, size_t Left, size_t Right)
 {
  QuickSort QS(Arr);
  QS.SortRecursive(Left, Right);
 }
};

template <typename T>
void Show(vector<T> &Arr)
{
 size_t Size = Arr.size();
 size_t i = 0;
 while (i < Size)
  cout << Arr[i++] << " ";
 cout << endl;
}

int main()
{
 vector<int> v{ 74,15,97,24,67,30,92,94,14,55,74 };

 Show(v);
 QuickSort<int>::Sort(v, 0, v.size() - 1);
 Show(v);
 QuickSort<int>::Sort(v, 0, v.size() - 1);
 Show(v);

 return 0;
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/13 上午 11:52:24
另一種選擇是採用平行處理,比如 OpenMP,不過這一部份我不熟悉,以下採用 CxxlMan2 程式庫中的 ThreadLimit 來實現。

CxxlMan2 程式庫可到 https://1drv.ms/u/s!Ap_vSwKlDD2gtWEi1iqeunjOLiqq 下載,解壓後只要把 Src\cxxlcommon\include 加入 include 搜尋路徑即可

ThreadLimit 的實作方法是把要要執行的單元先放入由 std::list 的佇列中,再由各 thread 從中取出執行,由於 std::list 還是有爆掉的危險,所以採用改良版堆疊模式相同的做法,所以 std::list 的用量也是以 log2(n) 計算(實際上因不像堆疊那樣層數累積,所以還要更少),所以算是為白老鼠的 gs 解套了,但是所花費的時間遠比堆疊版高出許多。

也許有人會說這不是平行處理的做法嗎,所以會高速執行,但由於演算法設計上的緣故,要等一個執行單元完成後才會再進行下一個,而不是下兩個或三個,所以沒有平行處理的發生,也因此 std::list 的使用量也只會一層。

所以整體分析後還是用遞廻才是王道

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/13 上午 11:56:27
#include <iostream>
#include <vector>
#include <THREADMGR.HPP> // CxxlMan2::ThreadLimit

using namespace std;
using namespace CxxlMan2;


template <typename T>
void Show(vector<T> &Arr)
{
 size_t Size = Arr.size();
 size_t i = 0;
 while (i < Size)
  cout << Arr[i++] << " ";
 cout << endl;
}

template <typename T>
class QuickSort
{ 
 vector<T> &m_Arr;
 ThreadLimit &m_TL;

 void Swap(size_t i, size_t j)
 {
  T tmp = m_Arr[i];
  m_Arr[i] = m_Arr[j];
  m_Arr[j] = tmp;
 }

 void SortRecursive(size_t Left, size_t Right)
 {
  while (Left < Right)
  {
   size_t j = Right + 1;
   {
    size_t i = Left;
    while (true)
    {
     while (i < j && m_Arr[++i] < m_Arr[Left]);
     while (Left < j && m_Arr[--j] >= m_Arr[Left]);
     if (i >= j)
      break;
     Swap(i, j);
    }
   }

   Swap(Left, j);

   if (j >(Left + Right) / 2)
   {
    m_TL.Thread([=, this] {this->SortRecursive(j + 1, Right); });
    Right = j;
   }
   else
   {
    m_TL.Thread([=, this] {this->SortRecursive(Left, j); });
    Left = j + 1;
   }
  }
 }

 // Constructor
 QuickSort(vector<T> &Arr, ThreadLimit &TL)
  :m_Arr(Arr),m_TL(TL)
 {

 }

public:

 static void Sort(vector<T> &Arr, size_t Left, size_t Right)
 {
  ThreadLimit TL((std::thread::hardware_concurrency() == 0) ?
   8 : std::thread::hardware_concurrency());

  QuickSort QS(Arr,TL);

  TL.Thread([=, &QS] {QS.SortRecursive(Left, Right); });
 }
};


int main()
{
 vector<int> v{ 74,15,97,24,67,30,92,94,14,55,74 };

 Show(v);
 QuickSort<int>::Sort(v, 0, v.size() - 1);
 Show(v);
 QuickSort<int>::Sort(v, 0, v.size() - 1);
 Show(v);

 return 0;
}

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/13 下午 01:09:48

>ThreadLimit 的實作方法是把要要執行的單元先放入由 std::list 的佇列中,再由各 thread 從中取出執行,由於 std::list 還是有爆掉的危險,所以採用改良版堆疊模式相同的做法,所以 std::list 的用量也是以 log2(n) 計算(實際上因不像堆疊那樣層數累積,所以還要更少),所以算是為白老鼠的 gs 解套了,但是所花費的時間遠比堆疊版高出許多。


哎,分析有誤,我只分析遞廻這邊,沒分析廻圈這邊,廻圈這邊還是會有遞廻,這樣一來 std::list 還是有可能會爆掉,白老鼠的 gs 還是沒能解套,目前遞廻還是唯一解


作者 : ice_emissary(燃燒的大地) 貼文超過200則
[ 貼文 386 | 人氣 0 | 評價 1770 | 評價/貼文 4.59 | 送出評價 17 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/13 下午 03:26:26
的確,快速排序法、以及其他很多別的演算法都需要暫存很多階段的資料,在演算一段落後回來取出使用。
說起來,這可以歸類為層級組織的一種形式,若要寬鬆解釋為遞迴的一種表現型態的話,在某些概念上也非不可!

像白老鼠一樣使用陣列來暫存狀態資料,或是使用遞迴呼叫來暫存狀態資料,就概念來說都是一樣的;
但是差在哪裡?差在實做層面,就是編譯器的實做面上!
沒錯,就我認為,如果我們考慮一個完美的執行環境的話,用陣列還是用遞迴其實沒有差別,因為他們在使用概念上是一樣的;
唯一的差別就是在編譯器的實做上而已!
回想大家建議不要使用遞迴的原因都是什麼?慢?爆堆疊?這些全都是實做細節造成的,而不是概念上的問題。

既然與概念無關,那就來討論實做上的區別細節,白老鼠的使用陣列儲存狀態的寫法和使用遞迴的寫法有什麼重大不同?

*速度*

遞迴的每一次記錄、與還原狀態都牽涉到函式呼叫和返回;而陣列就是查資料和放資料而已!

*堆疊空間限制*

使用堆疊儲存計算狀態,相比於使用陣列做同樣的事情,限制比較多,不小心就容易遇到空間不敷使用的狀況,這有數個原因:

1. 堆疊不是只存你要的資料而已。
它還存了很多別的東西,比如說返回位址、暫存器資料、函式參數與區域變數等等,使得在同樣暫存「一層」狀態資料的狀況下,堆疊會需要推送比我們使用陣列還要多的資料。

2. 堆疊空間極其有限。
如果只是因為第一點原因,在現代PC記憶體空間規格下問題也還好。
但是一般程式的堆疊空間其實並不是很大,通常約在數十K到數M之間,這就讓堆疊的使用比較拮据。
而且還要注意,堆疊不是只有你在用,還有你程式的其他函式也要用,這會讓實際可用的堆疊數量更小(註1)。
而用陣列的話,我們陣列的大小限制可比堆疊大得多,若是使用動態分配的空間,容量甚至可達單行程的記憶體限額!
然而實際上不會用這麼多,在通常的演算法裡,暫存資料的需求大小約在原始輸入資料的不到一倍,就算是暫存比較誇張的演算法,也約在原始資料的數倍大左右而已。
也就是說,若你要把 2G 陣列堆到爆的話,你的原始資料應該也有 2G 的大小!

最後討論一下你的程式碼,你的程式碼會慢是很合理的,光看到你用 vector 來存資料就不覺得它會快了!
然後你又用了執行緒,這又讓你的程式更慢了!
別忘執行緒本身也要開銷,執行緒的建立、銷毀、和切換都要消耗時間空間,在單一計算分工沒有很複雜的情況下,用過量的執行緒只會更慢而已,這是常識!

註1:
這是我從前實際遇過的 bug,
我們在嵌入式系統上遇到爆堆疊的問題,最後的爆點是在 X 函式裡(一開始沒發現真正原因,以為是函式寫錯)。
但是把 X 函式單獨拿出來測卻又沒問題,可是放回系統裡就會爆!
最後終於發現是堆疊的問題,這又讓我更納悶,因為 X 函式堆疊並沒有用多少!
原來是系統裡呼叫好多層子函式後,在某個子功能下才呼叫這個 X,而此時堆疊已沒剩多少!
(我們系統的其他部份超浪費堆疊,尤其是字串…我想做嵌入式的人懂的)
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/13 下午 07:42:49
所以還是先解決白老鼠 gs 的爆柞問題再說,雖然遞廻改良版很好用,但各種情況很難預料,也許堆積版也有用到的時候
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/13 下午 07:46:03
> ... 在單一計算分工沒有很複雜的情況下,用過量的執行緒只會更慢而已,這是常識!

燃燒的大地兄是真努力呢,一點一點地苦口婆心地解說啊... 除了上列一句,說得真到位。

多工 配 多核計算器,能提供較高的效能的情況,除了 多個沒交雜的複雜程序 同步處理 之外,還有另一情況,就是 把大量相同的簡易程序 同步處理。^^" , 當然,這是意指 SSE 和 GPU 上的多工,前提和你在說的 有少許不同了。
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/13 下午 09:50:03
平行處理技術會用於未來的量子電腦,不能小看它
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/14 上午 07:53:35
小朋友吵著嚷著 說編譯器提供的遞迴 是如何如何謎一般的好 (是個謎, 因為他一方面意識到 program stack 很小, 隨時會overflow; 但另一方面, 他又覺得他能在記憶體已用盡的前提下, 用遞迴暫存更多資料; @@?... 謎... 算了, 太詭異的邏輯, 實在是多想無益; 如果一個不小心 能理解這些太詭異的邏輯的話, 可真不好了.).

我也真夠無聊了, 我呢... 竟然為此跑去編程式 看看C++編譯器提供的遞迴 何時會出現 stack overflow.
下面的就是測試程式. program stack size 用編譯器預設的 1 MB, 編譯出 x64程式 的話,
recursive_sum() 這函數 遞迴16106次, 就會剛好出現 stack overflow.

假設 program stack 的 1 MB, 全都分給了這函數, 就可以換算出, 每次呼叫這函數的記憶體需求.
這函數每次呼叫需要用 65 Byte. 強調是這函數的, 是因為函數的參數和內容有變, 記憶體需求會更大.


#include <stdio.h>

double recursive_sum(double n)
{
  if(n>0)
    return n + recursive_sum(n-1);
    return 0;
}

void main()
{
  printf( "%lf\n", recursive_sum(16106) ); // x64, 這樣就會 stack overflow
  printf( "%lf\n", recursive_sum(64687) ); // x86, 這樣就會 stack overflow
}

-_-y--~~ocC , 編譯器提供的遞迴 明著就是無用之物, 我幹啥特地跑去看看它有多沒用呢?
我實在是無聊到呢...
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/14 上午 10:00:49
是你沒進入狀況吧,現在討論的是,在堆疊、堆積會爆掉的前提下,如何不讓它爆
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/14 上午 10:43:44

>是你沒進入狀況吧,現在討論的是,在堆疊、堆積會爆掉的前提下,如何不讓它爆

這簡單呀,不用編譯器提供的遞迴 不就好了嗎?幹啥要花工夫去補救沒做到位的東東?
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/14 上午 10:50:07
就算不用遞迴也有同樣的問題
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/14 下午 12:14:59

>就算不用遞迴也有同樣的問題

什麼問題?program stack 用量超過 1MB之類 的嗎?還是 總記憶體用量超過 少說也有好幾GB的 主記憶體總量 嗎?前者,不用遞迴 而出現的可能情是微乎其微。後者的話,可以系統會自行用 virtual memory 方式,以硬碟權充記憶體。

如果連硬碟也不敷應用的話,沒價值去救的了,升級硬體 或是 再把程序分拆成小份處理吧。

資料還不夠嗎?還要再提證據嗎?
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/14 下午 02:04:42

麻煩你從頭看一遍,堆疊部份已解決,現只剩你的 gs 堆積部份
作者 : ma_hty(白老鼠(Gary))討論區板主 OpenGL卓越專家DirectX優秀好手C++頂尖高手貼文超過2000則人氣指數超過70000點
[ 貼文 2170 | 人氣 89850 | 評價 10100 | 評價/貼文 4.65 | 送出評價 79 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/14 下午 03:32:37
>麻煩你從頭看一遍,堆疊部份已解決,現只剩你的 gs 堆積部份

算,不吐糟了。我錯,是我不該多管閒事的。也罷。
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/14 下午 04:26:21
好了,解決了使用堆積保存關鍵變數的方式,先保存較長的那邊並先處理短的那邊,保存的最長深度一樣以 log2(n) 計算

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
class QuickSort
{
 struct Rec_t
 {
  size_t Left;
  size_t Right;
 };

 vector<Rec_t> m_gs;
 vector<T> &m_Arr;

 void Swap(size_t i, size_t j)
 {
  T tmp = m_Arr[i];
  m_Arr[i] = m_Arr[j];
  m_Arr[j] = tmp;
 }

 void SortLoop(size_t Left, size_t Right)
 {
  m_gs.push_back({ Left,Right });
  while (m_gs.size() > 0)
  {
   Rec_t Rec = m_gs.back();
   m_gs.pop_back();
   if (Rec.Left < Rec.Right)
   {
    size_t i = Rec.Left;
    size_t j = Rec.Right + 1;
    while(true)
    {
     while (i < j && m_Arr[++i] < m_Arr[Rec.Left]);
     while (Rec.Left < j && m_Arr[--j] >= m_Arr[Rec.Left]);
     if (i >= j)
      break;
     Swap(i, j);
    }
    Swap(Rec.Left, j);

    if (j > (Rec.Left + Rec.Right) / 2)
    {
     m_gs.push_back({ Rec.Left,j });
     m_gs.push_back({ j + 1, Rec.Right });
    }
    else
    {
     m_gs.push_back({ j + 1,Rec.Right });
     m_gs.push_back({ Left, j });
    }
   }
  }
 }

 // Constructor
 QuickSort(vector<T> &Arr)
  :m_Arr(Arr)
 {

 }

public:

 static void Sort(vector<T> &Arr, size_t Left, size_t Right)
 {
  QuickSort QS(Arr);
  QS.SortLoop(Left, Right);
 }
};

template <typename T>
void Show(vector<T> &Arr)
{
 size_t Size = Arr.size();
 size_t i = 0;
 while (i < Size)
  cout << Arr[i++] << " ";
 cout << endl;
}

int main()
{
 vector<int> v{ 74,15,97,24,67,30,92,94,14,55,74 };

 Show(v);
 QuickSort<int>::Sort(v, 0, v.size() - 1);
 Show(v);
 QuickSort<int>::Sort(v, 0, v.size() - 1);
 Show(v);

 return 0;
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1034 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2018/7/14 下午 07:48:00

>
>    if (j > (Rec.Left + Rec.Right) / 2)
>    {
>     m_gs.push_back({ Rec.Left,j });
>     m_gs.push_back({ j + 1, Rec.Right });
>    }
>    else
>    {
>     m_gs.push_back({ j + 1,Rec.Right });
>     m_gs.push_back({ Left, j });
這裡要改
     m_gs.push_back({ Rec.Left, j });
 板主 : simula
 > C++ - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - C++ - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
C++
1 Raymond 13050 
2 青衫 4760 
3 simula 4690 
4 coco 4030 
5 白老鼠(Gary) 3670 
6 ozzy 2540 
7 Ben 2250 
8 Anderson 1960 
9 windblown 1650 
10 Kenny 1560 
C++
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2018 程式設計俱樂部 http://www.programmer-club.com.tw/
0.28125