Linear Function

「線性函數」。加權總和函數。

f(x₁, x₂, ..., xₙ) = w₁ x₁ + w₂ x₂ + ... + wₙ xₙ

線性函數是計算機科學經常使用的函數，熱門程度遠勝二元樹。現實世界相當複雜，經常出現難以計算的事物，此時工程師就會將事情簡化為線性函數。線性函數擁有強悍的數學性質和演算法，儘管艱深晦澀，但是質樸實用。

詳情請見本站文件「Linear Function」。

Stochastic Function

「隨機函數」。輸入是浮動數字。輸出顯然也是浮動數字。

f(X, Y, Z) = a X + Y Z     where X, Y, Z are random variable

古代數學家沒有仔細區分「浮動：有規矩」和「隨機：無規矩」的差別，把兩者都命名為隨機，混淆視聽。大家搞不清楚狀況的情況下，Stochastic Function跟Random Function被當作相同。

Random Function

「隨機函數」。輸入輸出隨機對應的函數。

隨機函數的輸入輸出，可以是連續數字、也可以是離散數字。

電腦做運算，數值皆離散。我們只能處理離散數字。

初次建立隨機函數，對應方式是隨機的；每次使用隨機函數，對應方式是固定的。

如果對應方式每次都是隨機的，那麼其實就是隨機數了。

// 產生隨機函數。輸入範圍[0,x)、輸出範圍[0,y)。 void make_random_function(int f[], int x, int y) { // 針對每一種輸入，產生[0,y)的隨機整數，作為輸出。 srand(time(0)); for (int i=0; i<x; ++i) f[i] = rand() % y; }

隨機函數是計算機科學的核心思想之一，經典程度堪比二元樹。例如稍後提到的Hash Function，其中一種變種就是均勻隨機函數，可以使用在伺服器負載平衡、網路資料庫存取。

Random Permutation

「隨機排列」。一對一隨機函數。

利用下個小節的演算法，來製造隨機排列。

// 產生隨機排列。輸入範圍[0,n)、輸出範圍[0,n)。 void make_random_permutation(int f[], int n) { for (int i=0; i<n; ++i) f[i] = i; random_permutation(f, n); // 請見下個小節 }

隨機排列是計算機科學的核心思想之一，經典程度堪比二元樹。隨機排列是加密演算法的基礎，加密演算法是網路傳輸的基礎，網路傳輸是上網閱讀文章、觀看影片的基礎。

Random Permutation（Random Shuffle）

方才是函數，此處是數列。

「隨機排列」或「隨機混洗」。兩種解讀方式：

一、所有排列挑出一種排列。機率都一樣。

二、一群數字不按順序排好、打亂順序。排序的相反。

隨機排列可以用於製造隨機輸入，用來測試程式是否穩健。隨機排列也可以用來製作視覺特效。

演算法是Fisher–Yates Shuffle：跟後方任意數字交換、或者不交換。時間複雜度O(N)。

可以直接使用C++標準函式庫的shuffle()。

// 產生[0,x)的隨機整數。注意到x不能大於RAND_MAX。 int rand(int x) { return rand() % x; } // 產生[x,y)的隨機整數。 int rand(int x, int y) { return x + rand(y - x); } void random_permutation(int a[], int N) { // 設定亂數表，之後才能使用rand()。 srand(time(0)); for (int i=0; i<N-1; i++) swap(a[i], a[ rand(i, N) ]); } void random_permutation(int a[], int N) { srand(time(0)); for (int i=N-1; i>0; i--) // 倒過來做，省略一個參數。 swap(a[i], a[ rand() % (i+1) ]); }

Random k-Combination（Simple Random Sampling）

「隨機k組合」或「簡單隨機抽樣」。兩種解讀方式：

一、所有組合挑出一種組合，其大小為k。機率都一樣。

二、一群數字打亂順序，然後挑出前k個數字。

演算法是Reservoir Sampling：依序讀取數字，取代當下組合的任意數字，或者不取代。online演算法，當下組合是當下答案。時間複雜度O(N)。

改良版本是Li's Algorithm：跳躍讀取數字，節省時間。背後原理是幾何分布。時間複雜度O(K + Klog(N/K))，到達理論下限。

可以直接使用C++標準函式庫的sample()。

vector<int> random_combination(int a[], int N, int K) { srand(time(0)); vector<int> comb(K); for (int i=0; i<K; i++) comb[i] = a[i]; for (int i=K; i<N; i++) { int j = rand() % i; if (j < K) comb[j] = a[i]; } return comb; } vector<int> random_combination(int a[], int N, int K) { default_random_engine g; uniform_int_distribution<int> rand(0, K-1); uniform_real_distribution<double> uniform(0, 1); vector<int> comb(K); for (int i=0; i<K; i++) comb[i] = a[i]; double W = exp(log(uniform(g))/K); for (int i=K; i<N; i++) { i += floor(log(uniform(g))/log(1-W)); if (i >= N) break; comb[rand(g)] = a[i]; W *= exp(log(uniform(g))/K); } return comb; }

Hash Function

「雜湊函數」。限制輸出範圍的函數。

雜湊函數有著形形色色的變種：限寬、均勻、保距、量化、混亂、單向、編碼。大家視情況需要，混用多個變種。

hash是一種菜式：肉、馬鈴薯、蔬菜，剁碎攪拌成為餡泥，然後烤炸。hash具有諸多意涵：均勻隨機、範圍壓縮、型態變化。

1. hash function

限寬。限制輸出範圍。簡易方式是mod運算。

用途是縮減數字範圍。

int hash(int n) { return n % 10; // 輸出範圍是整數[0,9]。 } // C++標準函式庫的hash // 印出數字100的雜湊值 hash<int> h; cout << h(100);

2. uniform hash function

均勻。輸出數字使用機率均等。簡易方式是mod最大公因數。

用途是均勻分散儲存。知名應用是hash table。

3. isometric mapping / locality-sensitive hashing

保距。所有數對，變換前的差異，大致等於變換後的差異。簡易方式是線性變換。

同樣道理，還可以發明保長、保角、保秩、保序等變種。

用途是以雜湊值估計相似度。

4. quantization / projection

量化。刪除數字的細節，降低精確度。簡易方式是floor運算。

用途是簡化數字。知名演算法是PCA、KNN。

int hash(int n) { return n / 10 * 10; // 刪除個位數 }

5. random hash function

混亂。輸出是固定的隨機數。簡易方式是以輸入數字生成隨機數、隨機排列。

// Linear Congruential Generator int hash(int n) { // 輸出是隨機數，位於[0, 2³¹-1]。 unsigned int hash = n; hash = hash * 1103515245U + 12345U; return int(hash % 2147483648U); }

6. one-way hash function

單向。難以從輸出推算輸入。簡易方式是餘數連乘、三角函數。

用途是密碼、摘要、簽章，讓外人難以偽造變換前的原始資料。知名演算法如SHA-2、MD5。

請見本站文件「Encryption」。

7. coding / indexing

編碼。輸入不是數字，而是其他元件，例如字串。簡易方式是先化作多項式、再化作數字。

用途是建立索引表，知名演算法如murmur、xxHash。

請見本站文件「String」。

// 印出浮點數0.123的雜湊值 cout << hash<float>{}(0.123f); // 印出字串abc的雜湊值 cout << hash<string>{}("abc");