Linear Function

Linear Function

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

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

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

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

Stochastic Function

Stochastic Function

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

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

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

Random Function

Random Function

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

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

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

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

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

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

Random Permutation

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

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

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

Random Permutation(Random Shuffle)

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

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

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

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

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

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

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

Random k-Combination(Simple Random Sampling)

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

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

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

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

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

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

Hash Function

Hash Function

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

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

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

1. hash function

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

用途是縮減數字範圍。

2. uniform hash function

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

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

3. isometric mapping / locality-sensitive hashing

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

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

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

4. quantization / projection

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

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

5. random hash function

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

6. one-way hash function

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

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

請見本站文件「Encryption」。

7. coding / indexing

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

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

請見本站文件「String」。