電腦遊戲製作開發設計論壇 首頁 電腦遊戲製作開發設計論壇
任何可以在PC上跑的遊戲都可以討論，主要以遊戲之製作開發為主軸，希望讓台灣的遊戲人有個討論、交流、教學、經驗傳承的園地
 
 常見問題常見問題   搜尋搜尋   會員列表會員列表   會員群組會員群組   會員註冊會員註冊 
 個人資料個人資料   登入檢查您的私人訊息登入檢查您的私人訊息   登入登入 

Google
今天老師教的 shell sort ...

 
發表新主題   回覆主題    電腦遊戲製作開發設計論壇 首頁 -> 遊戲程式初級班：語法及基礎概念
上一篇主題 :: 下一篇主題  
發表人 內容
babu61509
散播福音的祭司


註冊時間: 2007-08-26
文章: 142

681.01 果凍幣
發表發表於: 2008-5-14, AM 11:34 星期三    文章主題: 今天老師教的 shell sort ... 引言回覆
代碼:

//謝耳排序！
#include <iostream>
#include<conio.h>
using namespace std;
int v[]={99,1,60,30,100,45,8};
int gap, i, j;
int n=sizeof(v)/sizeof(*v);
void show(){
  cout<<gap<<','<<i<<','<<j<<")\t";
  for(int z = 0; z<n; ++z)
    cout<<z[v]<<' ';
  cout<<endl;
}
void shellsort(int v[], int n){
  for(gap=n/2; gap>0; gap/=2)
    for(i=gap; i<n; i++)
      for(j=i-gap; j>=0 && v[j]>v[j+gap]; show(),j-=gap)
        v[j] ^= v[j+gap] ^= v[j] ^= v[j+gap];
  show();
}
void main(){
 // clrscr();
  gap=i=j=0;
  show();
  shellsort(v, n);
}


其實是剛剛教的 ( 毆

覺得這一段滿有趣的
代碼:

v[j] ^= v[j+gap] ^= v[j] ^= v[j+gap];


應該有人看的懂吧XD?

他的作用就是利用XOR的特性來交換變數值 (請用反白喔~)

個人覺得滿有趣的所以跟大家分享一下 . v.
而且應該滿多地方會用的. v.
_________________
已經畢業了!!
回頂端
檢視會員個人資料 發送私人訊息
happylin
略有貢獻的成員


註冊時間: 2007-07-26
文章: 70

127.34 果凍幣
發表發表於: 2008-5-15, AM 9:14 星期四    文章主題: 引言回覆
用XOR swap 不會比較好
compiler 後的程式碼可能還會比用暫時的變數多更多指令

且他只能用在整數型別. (當然所有的型別都能轉成整數)

請小心使用.
回頂端
檢視會員個人資料 發送私人訊息
lsk
喜歡上這裡的冒險者


註冊時間: 2007-06-20
文章: 93

20.59 果凍幣
發表發表於: 2008-5-15, AM 9:16 星期四    文章主題: Re: 今天老師教的 shell sort ... 引言回覆
babu61509 寫到:
代碼:

//謝耳排序！
#include <iostream>
#include<conio.h>
using namespace std;
int v[]={99,1,60,30,100,45,8};
int gap, i, j;
int n=sizeof(v)/sizeof(*v);
void show(){
  cout<<gap<<','<<i<<','<<j<<")\t";
  for(int z = 0; z<n; ++z)
    cout<<z[v]<<' ';
  cout<<endl;
}
void shellsort(int v[], int n){
  for(gap=n/2; gap>0; gap/=2)
    for(i=gap; i<n; i++)
      for(j=i-gap; j>=0 && v[j]>v[j+gap]; show(),j-=gap)
        v[j] ^= v[j+gap] ^= v[j] ^= v[j+gap];
  show();
}
void main(){
 // clrscr();
  gap=i=j=0;
  show();
  shellsort(v, n);
}


其實是剛剛教的 ( 毆

覺得這一段滿有趣的
代碼:

v[j] ^= v[j+gap] ^= v[j] ^= v[j+gap];


應該有人看的懂吧XD?

他的作用就是利用XOR的特性來交換變數值 (請用反白喔~)

個人覺得滿有趣的所以跟大家分享一下 . v.
而且應該滿多地方會用的. v.


很有趣~ 數學原理其實就是保待相同的位元、翻轉不同的位元。

如：A^=B^=A^=B;
可看成是：A^=(B^=(A^=B));
最裡面的()是算出AB之間哪些位元是不同的，第二層把B的不同位元翻轉，於是B的數位就跟A相同；然後最外層再把事實上數值已經等於A的B翻轉一次，於是A就有了B的原值了。

這方面可以省一個暫存變數，不過在當今這個compiler多半有做最佳化的時代，不知道會不會比C=B, B=A, A=C還要快？晚點來試試看...
回頂端
檢視會員個人資料 發送私人訊息
lsk
喜歡上這裡的冒險者


註冊時間: 2007-06-20
文章: 93

20.59 果凍幣
發表發表於: 2008-5-16, PM 12:34 星期五    文章主題: Re: 今天老師教的 shell sort ... 引言回覆
lsk 寫到:

很有趣~ 數學原理其實就是保待相同的位元、翻轉不同的位元。

如：A^=B^=A^=B;
可看成是：A^=(B^=(A^=B));
最裡面的()是算出AB之間哪些位元是不同的，第二層把B的不同位元翻轉，於是B的數位就跟A相同；然後最外層再把事實上數值已經等於A的B翻轉一次，於是A就有了B的原值了。

這方面可以省一個暫存變數，不過在當今這個compiler多半有做最佳化的時代，不知道會不會比C=B, B=A, A=C還要快？晚點來試試看...


用VS2008 express看：

代碼:
int c = a;
011E13E7  mov         eax,dword ptr [a]
011E13EA  mov         dword ptr [c],eax
a = b;
011E13ED  mov         eax,dword ptr [b]
011E13F0  mov         dword ptr [a],eax
b = c;
011E13F3  mov         eax,dword ptr [c]
011E13F6  mov         dword ptr [b],eax

a ^= b ^= a ^= b;
011E1416  mov         eax,dword ptr [a]
011E1419  xor         eax,dword ptr [b]
011E141C  mov         dword ptr [a],eax
011E141F  mov         ecx,dword ptr [b]
011E1422  xor         ecx,dword ptr [a]
011E1425  mov         dword ptr [b],ecx
011E1428  mov         edx,dword ptr [a]
011E142B  xor         edx,dword ptr [b]
011E142E  mov         dword ptr [a],edx


用後者要比前者多了三個指令，所以還是用一個暫存值的效果比較好。
回頂端
檢視會員個人資料 發送私人訊息
happylin
略有貢獻的成員


註冊時間: 2007-07-26
文章: 70

127.34 果凍幣
發表發表於: 2008-5-16, PM 6:37 星期五    文章主題: 引言回覆
用VC 6.0 最佳化那段 shell sort 的程式 用xor

代碼:

; 29   : void shellsort(int v[], int n){

   push   ebx

; 30   :    for(gap=n/2; gap>0; gap/=2)

   mov   ebx, DWORD PTR _n$[esp]
   mov   eax, ebx
   cdq
   sub   eax, edx
   sar   eax, 1
   test   eax, eax
   mov   DWORD PTR ?gap@@3HA, eax      ; gap
   jle   $L9190
   mov   ecx, DWORD PTR _v$[esp]
   push   esi
   push   edi
$L9188:

; 31   :       for(i=gap; i<n; i++)

   mov   esi, eax
   cmp   eax, ebx
   mov   DWORD PTR ?i@@3HA, esi         ; i
   jge   SHORT $L9189
$L9191:

; 32   :          for(j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap)

   sub   esi, eax
   mov   DWORD PTR ?j@@3HA, esi         ; j
   js   SHORT $L9192
$L9194:
   mov   edi, DWORD PTR [ecx+esi*4]
   lea   edx, DWORD PTR [esi+eax]
   mov   edx, DWORD PTR [ecx+edx*4]
   cmp   edi, edx
   jle   SHORT $L9192
;==================================交換開始
; 33   :             v[j] ^= v[j+gap] ^= v[j] ^= v[j+gap];

   xor   edx, edi
   mov   DWORD PTR [ecx+esi*4], edx
   mov   edx, DWORD PTR ?j@@3HA         ; j
   mov   eax, DWORD PTR ?gap@@3HA      ; gap
   add   eax, edx
   mov   edx, DWORD PTR [ecx+edx*4]
   mov   edi, DWORD PTR [ecx+eax*4]
   lea   eax, DWORD PTR [ecx+eax*4]
   xor   edi, edx
   mov   DWORD PTR [eax], edi
   mov   eax, DWORD PTR ?j@@3HA         ; j
   mov   edx, DWORD PTR ?gap@@3HA      ; gap
   mov   esi, DWORD PTR [ecx+eax*4]
   add   edx, eax
   mov   edx, DWORD PTR [ecx+edx*4]
   xor   esi, edx
   mov   DWORD PTR [ecx+eax*4], esi
   mov   esi, DWORD PTR ?j@@3HA         ; j
   mov   eax, DWORD PTR ?gap@@3HA      ; gap
   sub   esi, eax
   mov   DWORD PTR ?j@@3HA, esi         ; j
   jns   SHORT $L9194
$L9192:

; 31   :       for(i=gap; i<n; i++)

   mov   esi, DWORD PTR ?i@@3HA         ; i
   inc   esi
   cmp   esi, ebx
   mov   DWORD PTR ?i@@3HA, esi         ; i
   jl   SHORT $L9191
$L9189:

; 30   :    for(gap=n/2; gap>0; gap/=2)

   cdq
   sub   eax, edx
   sar   eax, 1
   test   eax, eax
   mov   DWORD PTR ?gap@@3HA, eax      ; gap
   jg   $L9188
   pop   edi
   pop   esi
$L9190:
   pop   ebx

; 34   :
; 35   : }

   ret   0



用 temp 變數
代碼:

PUBLIC   ?shellsortT@@YAXQAHH@Z            ; shellsortT
;   COMDAT ?shellsortT@@YAXQAHH@Z
_TEXT   SEGMENT
_v$ = 8
_n$ = 12
?shellsortT@@YAXQAHH@Z PROC NEAR         ; shellsortT, COMDAT

; 15   : {

   push   ebx

; 16   :    for(gap=n/2; gap>0; gap/=2)

   mov   ebx, DWORD PTR _n$[esp]
   mov   eax, ebx
   cdq
   sub   eax, edx
   sar   eax, 1
   test   eax, eax
   mov   DWORD PTR ?gap@@3HA, eax      ; gap
   jle   SHORT $L9176
   push   esi
   mov   esi, DWORD PTR _v$[esp+4]
   push   edi
$L9174:

; 17   :       for(i=gap; i<n; i++)

   mov   ecx, eax
   cmp   eax, ebx
   mov   DWORD PTR ?i@@3HA, ecx         ; i
   jge   SHORT $L9175
$L9177:

; 18   :          for(j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap)

   sub   ecx, eax
   mov   DWORD PTR ?j@@3HA, ecx         ; j
   js   SHORT $L9178
$L9180:
   mov   edx, DWORD PTR [esi+ecx*4]
   lea   edi, DWORD PTR [ecx+eax]
   mov   edi, DWORD PTR [esi+edi*4]
   cmp   edx, edi
   jle   SHORT $L9178
;==================================交換開始
; 19   :          {
; 20   :             int t=v[j];
; 21   :             v[j]=v[j+gap];

   mov   DWORD PTR [esi+ecx*4], edi

; 22   :             v[j+gap]=t;

   mov   eax, DWORD PTR ?gap@@3HA      ; gap
   mov   ecx, DWORD PTR ?j@@3HA         ; j
   add   ecx, eax
   mov   DWORD PTR [esi+ecx*4], edx
   mov   ecx, DWORD PTR ?j@@3HA         ; j
   mov   eax, DWORD PTR ?gap@@3HA      ; gap
   sub   ecx, eax
   mov   DWORD PTR ?j@@3HA, ecx         ; j
   jns   SHORT $L9180
$L9178:

; 17   :       for(i=gap; i<n; i++)

   mov   ecx, DWORD PTR ?i@@3HA         ; i
   inc   ecx
   cmp   ecx, ebx
   mov   DWORD PTR ?i@@3HA, ecx         ; i
   jl   SHORT $L9177
$L9175:

; 16   :    for(gap=n/2; gap>0; gap/=2)

   cdq
   sub   eax, edx
   sar   eax, 1
   test   eax, eax
   mov   DWORD PTR ?gap@@3HA, eax      ; gap
   jg   SHORT $L9174
   pop   edi
   pop   esi
$L9176:
   pop   ebx

; 23   :          }
; 24   :
; 25   :    
; 26   : }

   ret   0


兩者的程式碼差更多 @@
回頂端
檢視會員個人資料 發送私人訊息
從之前的文章開始顯示:   
發表新主題   回覆主題    電腦遊戲製作開發設計論壇 首頁 -> 遊戲程式初級班：語法及基礎概念 所有的時間均為 台灣時間 (GMT + 8 小時)
第1頁(共1頁)

 
前往:  
您 無法 在這個版面發表文章
您 無法 在這個版面回覆文章
您 無法 在這個版面編輯文章
您 無法 在這個版面刪除文章
您 無法 在這個版面進行投票
您 可以 在這個版面附加檔案
您 可以 在這個版面下載檔案


Powered by phpBB © 2001, 2005 phpBB Group
正體中文語系由 phpbb-tw 維護製作