Linear Function(Under Construction!)

Linear Function

「線性函數」。加權平均函數。

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

Stochastic Function(Under Construction!)

Stochastic Function

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

Random Function(Under Construction!)

Random Function

「隨機函數」。隨機對應的函數。

Random Permutation

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

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

從所有排列取出一種排列。每種排列的出現機率都一樣。

隨機排列經常用於隨機演算法,避免輸入資料成為worst case,降低演算法的時間複雜度。隨機排列也經常用於製造隨機輸入,用來測試程式是否穩健。

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

可以直接使用STL的shuffle()。

隨機組合(定量版本)

從所有組合取出一種組合。每種組合的出現機率都一樣。

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

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

可以直接使用STL的sample()。

Hash Function

Hash Function

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

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

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. cryptographic hash function

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

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

請見本站文件「Encryption」。

7. coding

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

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

請見本站文件「String」。