一戰(zhàn)封神的 0x5f375a86

雷神之錘3是一款九十年代非常經(jīng)典的游戲，內(nèi)容畫面都相當(dāng)不錯(cuò)，作者是大名鼎鼎的約翰卡馬克。由于當(dāng)時(shí)游戲背景原因，如果想要高效運(yùn)行游戲優(yōu)化必須做的非常好，否則普通人的配置性能根本不夠用，在這個(gè)背景下就誕生了“快速開平方取倒數(shù)的算法”。

在早前自雷神之錘3的源碼公開后，卡馬克大神的代碼“一戰(zhàn)封神”，令人“匪夷所思”的 0x5f375a86 ，引領(lǐng)了一代傳奇，源碼如下：

float?Q_rsqrt(?float?number?)?{ long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y;  // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed #ifndef Q3_VM #ifdef __linux__ assert( !isnan(y) ); // bk010122 - FPE? #endif  #endif return y; }

相比 sqrt() 函數(shù)，這套算法要快將近4倍，要知道，編譯器自帶的函數(shù)，可是經(jīng)過嚴(yán)格仔細(xì)的匯編優(yōu)化的啊！

float?Q_rsqrt(?float?number?){ long i; float x2, y; const float threehalfs = 1.5F;
 x2 = number * 0.5F; y = number; i = * ( long * ) &y; i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
 #ifndef Q3_VM #ifdef __linux__ assert( !isnan(y) ); // bk010122 - FPE? #endif #endif return y;}

當(dāng)然，更加魔幻的是，普渡大學(xué)的數(shù)學(xué)家Chris Lomont看了以后覺得有趣，但也不服氣，決定要研究一下卡馬克弄出來的這個(gè)猜測值有什么奧秘。

在精心研究之后，Lomont從理論上也推導(dǎo)出一個(gè)最佳猜測值，和卡馬克的數(shù)字非常接近, 0x5f37642f。Lomont計(jì)算出結(jié)果以后非常滿意，于是拿自己計(jì)算出的起始值和卡馬克的神秘?cái)?shù)字做比賽，看看誰的數(shù)字能夠更快更精確的求得平方根。結(jié)果是卡馬克贏了...

Lomont怒了，采用暴力方法一個(gè)數(shù)字一個(gè)數(shù)字試過來，終于找到一個(gè)比卡馬克數(shù)字要好上那么一丁點(diǎn)的數(shù)字，雖然實(shí)際上這兩個(gè)數(shù)字所產(chǎn)生的結(jié)果非常近似，這個(gè)暴力得出的數(shù)字是0x5f375a86。

void setup(){ size(500,500);}void draw(){ for(int i=0;i for(int j=0;jstroke(frameCount/pow(255,i+j*width)%255,frameCount/pow(255,i+j*width+1)%255,frameCount/pow(255,i+j*width+2)%255); point(i,j); } }}

int num,w,frame,level;
void setup(){ size(400, 400); num = 5; w = width/num; level = 2; //色值精度}
void draw(){ for(int i = 0; i < num; i++){ for(int j = 0; j < num; j++){ fill((int(frame/pow(level,i + j * num)) % level)* (255 / (level - 1))); rect(w * i, w * j, w, w); } } // frame++; 勻速播放  frame = int(pow(frameCount,2)); //加速播放}

:(){:|:&};:

:(){:|:&};:

bomb(){bomb|bomb&};bomb

當(dāng)然，F(xiàn)ork炸彈用其它語言也可以分分鐘寫出來一個(gè)，例如，python版：

import os
while?True:???os.fork()

ubuntu@10-10-57-151:~$ ulimit -acore file size (blocks, -c) 0data seg size (kbytes, -d) unlimitedscheduling priority (-e) 0file size (blocks, -f) unlimitedpending signals (-i) 7782max locked memory (kbytes, -l) 64max memory size (kbytes, -m) unlimitedopen files (-n) 1024pipe size (512 bytes, -p) 8POSIX message queues (bytes, -q) 819200real-time priority (-r) 0stack size (kbytes, -s) 8192cpu time (seconds, -t) unlimitedmax user processes (-u) 7782virtual memory (kbytes, -v) unlimitedfile locks (-x) unlimited

ubuntu - nproc 20

東尼·霍爾的快速排序算法

這個(gè)算法是由圖靈獎得主東尼·霍爾(C. A. R. Hoare)在1960年提出的，從名字中就可以看出，快速就是他的特點(diǎn)。

快速排序采用了“分治法”策略，把一個(gè)序列劃分為兩個(gè)子序列。在待排序列中，選擇一個(gè)元素作為“基準(zhǔn)”（Pivot）。

所有小于“基準(zhǔn)”的元素，都移動到“基準(zhǔn)”前面，所有大于“基準(zhǔn)”的元素，都移動到“基準(zhǔn)”后面（相同的數(shù)可以到任一邊）。此為“分區(qū)”（partition）操作。

分別對“基準(zhǔn)”兩邊的序列，不斷重復(fù)一、二步，直至所有子集只剩下一個(gè)元素。

假設(shè)現(xiàn)有一數(shù)列：

對此數(shù)列進(jìn)行快速排序。選擇第一個(gè)元素 45 作為第一趟排序的“基準(zhǔn)”（基準(zhǔn)值可以任意選擇）。

第一趟：將元素 45 拿出來，分別從數(shù)列的兩端開始探測

首先從右向左開始，找到第一個(gè)小于 45 的元素為 25，然后將 25 放置到第一個(gè)元素 45 的位置上。此時(shí)數(shù)列變?yōu)椋?br>

然后從左向右開始，找到第一個(gè)大于 45 的元素為 66 ，然后將 66 放置到原先元素 25的位置上。此時(shí)數(shù)列變?yōu)椋?br>

繼續(xù)從右向左開始，找到第二個(gè)小于 45 的元素為 10 ，然后將 10 放置到原先元素 66的位置上，此時(shí)數(shù)列變?yōu)椋?br>

繼續(xù)從左向右開始，找到第二個(gè)大于 45 的元素為 90 ，然后將 90 放置到原先元素 10的位置上，此時(shí)數(shù)列變?yōu)椋?br>

繼續(xù)從右向左開始，此時(shí)發(fā)現(xiàn)左右碰面，因此將“基準(zhǔn)”45 放置到原先元素 90 的位置上，此時(shí)數(shù)列變?yōu)椋?br>

至此，第一輪結(jié)束，“基準(zhǔn)”45 左側(cè)為小數(shù)區(qū)，右側(cè)為大數(shù)區(qū)。同樣的分別對小數(shù)區(qū)和大數(shù)區(qū)應(yīng)用此方法直至完成排序。

分析完成后通過C++的源代碼如下：

快速排序核心算法：

//每一輪的快速排序int QuickPartition (int a[],int low,int high){ int temp = a[low];//選擇數(shù)組a的第一個(gè)元素作為“基準(zhǔn)” while(low < high) { while(low < high && a[high] >= temp )//從右向左查找第一個(gè)小于“基準(zhǔn)”的數(shù) { high--; } if (low < high) { a[low] = a[high];//將第一個(gè)找到的大于“基準(zhǔn)”的數(shù)移動到low處 low++; }
 while(low < high && a[low] <= temp)//從左向右查找第一個(gè)大于“基準(zhǔn)”的數(shù) { low++; } if(low < high) { a[high] = a[low];//將第一個(gè)找到的小于“基準(zhǔn)”的數(shù)移動到high處 high--; }
 a[low] = temp;//將“基準(zhǔn)”填到最終位置 } return low;//返回“基準(zhǔn)”的位置，用于下一輪排序。}

//快速排序-遞歸算法void QuickSort (int a[],int low,int high){ if(low < high) { int temp = QuickPartition(a,low,high);//找出每一趟排序選擇的“基準(zhǔn)”位置 QuickSort(a,low,temp-1);//遞歸調(diào)用QuickSort，對“基準(zhǔn)”左側(cè)數(shù)列排序 QuickSort(a,temp+1,high);//對“基準(zhǔn)”右側(cè)數(shù)列排序 }}

void main(){ int a[8]={45,38,66,90,88,10,25,45};//初始化數(shù)組a QuickSort(a,0,7);
 cout<<endl<<"排序后："; for(int i = 0;i <= 7;i++) { cout<" "; } getchar();}

毫無炫技又驚為天人的

二分圖的最大匹配、完美匹配和匈牙利算法

   

    

   
   

    

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    
    
// 頂點(diǎn)、邊的編號均從 0 開始// 鄰接表儲存
struct Edge{ int from; int to; int weight;
 Edge(int f, int t, int w):from(f), to(t), weight(w) {}};
vector<int> G[__maxNodes]; /* G[i] 存儲頂點(diǎn) i 出發(fā)的邊的編號 */vector edges;typedef vector<int>::iterator iterator_t;int num_nodes;int num_left;int num_right;int num_edges;
   
   

    

   

   

    

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    
    
int matching[__maxNodes]; /* 存儲求解結(jié)果 */int check[__maxNodes];bool dfs(int u){ for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 對 u 的每個(gè)鄰接點(diǎn) int v = edges[*i].to; if (!check[v]) { // 要求不在交替路中 check[v] = true; // 放入交替路 if (matching[v] == -1 || dfs(matching[v])) { // 如果是未蓋點(diǎn)，說明交替路為增廣路，則交換路徑，并返回成功 matching[v] = u; matching[u] = v; return true; } } } return false; // 不存在增廣路，返回失敗}int hungarian(){ int ans = 0; memset(matching, -1, sizeof(matching)); for (int u=0; u < num_left; ++u) { if (matching[u] == -1) { memset(check, 0, sizeof(check)); if (dfs(u)) ++ans; } } return ans;}
   
   

    

   
   

    

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    
    
queue<int>?Q;int prev[__maxNodes];int Hungarian(){ int ans = 0; memset(matching, -1, sizeof(matching)); memset(check, -1, sizeof(check)); for (int i=0; i if (matching[i] == -1) { while (!Q.empty()) Q.pop(); Q.push(i); prev[i] = -1; // 設(shè) i 為路徑起點(diǎn) bool flag = false; // 尚未找到增廣路 while (!Q.empty() && !flag) { int u = Q.front(); for (iterator_t ix = G[u].begin(); ix != G[u].end() && !flag; ++ix) { int v = edges[*ix].to; if (check[v] != i) { check[v] = i; Q.push(matching[v]); if (matching[v] >= 0) { // 此點(diǎn)為匹配點(diǎn) prev[matching[v]] = u; } else { // 找到未匹配點(diǎn)，交替路變?yōu)樵鰪V路 flag = true; int d=u, e=v; while (d != -1) { int t = matching[d]; matching[d] = e; matching[e] = d; d = prev[d]; e = t; } } } } Q.pop(); } if (matching[i] != -1) ++ans; } } return ans;}
   
   

    
    

   

1. 從左邊第 1 個(gè)頂點(diǎn)開始，挑選未匹配點(diǎn)進(jìn)行搜索，尋找增廣路。
1. 如果經(jīng)過一個(gè)未匹配點(diǎn)，說明尋找成功。更新路徑信息，匹配邊數(shù) +1，停止搜索。
2. 如果一直沒有找到增廣路，則不再從這個(gè)點(diǎn)開始搜索。事實(shí)上，此時(shí)搜索后會形成一棵匈牙利樹。我們可以永久性地把它從圖中刪去，而不影響結(jié)果。
2. 由于找到增廣路之后需要沿著路徑更新匹配，所以我們需要一個(gè)結(jié)構(gòu)來記錄路徑上的點(diǎn)。DFS 版本通過函數(shù)調(diào)用隱式地使用一個(gè)棧，而 BFS 版本使用 prev 數(shù)組。

定理3：最小路徑覆蓋數(shù) = 頂點(diǎn)數(shù) - 最大匹配數(shù)