用Go寫演算法：求最小可用自然數

演算法 Go語言 · 發表 2018-10-13 00:59:32

摘要：前言前一段時間在 reddit 上看到有人推廣一篇名為GopherCon 2018 - Demystifying Binary Search Tree Algorithms 的部落格，部落格中列舉了傳統大學裡學習演算法的種種弊端，並強調了用 Go 實...

前言

前一段時間在 reddit 上看到有人推廣一篇名為ofollow,noindex" target="_blank">GopherCon 2018 - Demystifying Binary Search Tree Algorithms 的部落格，

部落格中列舉了傳統大學裡學習演算法的種種弊端，並強調了用 Go 實現演算法是多麼簡單有趣，然後拿二叉樹舉了個例子。讀完這篇部落格以後，我不得不說，真心沒看出來 Go 寫演算法的優勢在哪裡。但是，配圖確實萌翻了，下面盜圖一副。

雖然不會畫畫，但是並不妨礙用 Go 做一些演算法實現的嘗試。這裡我從 "Pears of Functional Algorithms Design" 裡拿了一道題：給定一個無序自然數陣列 A，求出不在 A 中的最小自然數，約束條件如下：

A 中的元素個數是有限的，每個元素都是自然數，並且互不相同（自然數包含 0 和正整數）。
假設 A 中元素的大小在 [0, inf] 之間。

Note: 由於計算機本身的限制，我們這裡假設 inf = 2^31-1

舉幾個例子：

A = [1,2,9,4], output = 0
A = [0,1,2], output = 3
A = [0,1,16,8,4,2], output = 3
A = [], output = 0

首先我們宣告一個函式來表述這個問題：

func f(A []int) int

然後，我們思考如何解決這個問題。

此處建議思考兩分鐘，如果身邊有筆有紙，建議寫寫畫畫。

方案一

首先映入腦海的方法是：宣告一個 bool 陣列 B，將 A 中元素作為下標，將 B 對應的元素置為 true，遍歷 B，返回第一個 false 的下標。這個方法顯然不靠譜，在某些條件下，它會使用大量記憶體。為了更直觀，這裡把具體實現貼出來：

func f(A []int) int {
maxElem := max(A) // 函式 max 用於獲取陣列的最大值
B := make([]bool, maxElem+1, maxElem+1)
for _, elem := range A {
B[elem] = true
}
for idx, val := range B {
if !val {
return idx
}
}
}

在極限情況下，例如 A = [2^31-1]，上面程式碼中 B 會佔用 (2^31-1)/8 ≈ 2^28 byte = 256 Mbyte 記憶體，顯然很不合理。

方案二：引入排序函式

如果引入一個庫函式呢，比如sort 。先用sort 給 A 排序，然後從 0 開始遞增，找到第一個不在 A 中的元素。這個方法可以解決問題，假設 n=len(A)，排序時間 O(nlogn), 檢索效率 O(n)。我們看一下程式碼實現：

func f(A []int) int {
sort.Ints(A)
for idx, val := range A {
if idx != val {
return idx
}
}
return len(A)
}

這是一個很常規的方法。這裡的實現有兩個地方需要注意：

if idx != val
return len(A)

但是引入sort 的代價也很明顯：O(nlogn) 的時間複雜度比較高。有沒有時間複雜度為 O(n) 的方法呢？

我們再次思考這個問題本身。對於亂序狀態下的 A，對於 [0, inf] 的每一個自然數，搜尋的耗時都是 O(n)，最多搜尋 n 個自然數。要達到總體複雜度為 O(n)，一個方法是將搜每個自然數搜尋的耗時降低到 O(1)，另一個方法是只搜尋 O(1) 個自然數。後一個方法看起來有點難以實現，但是前一個方法只需要我們引入一個 hashmap。

而 Go 語言內建的 map 就是基於 hashmap。

方案三：引入 map

引入 map 以後，大致步驟是：

遍歷 A，填充 map。時間和空間複雜度都是 O(n)
遍歷 [0, inf]，找到第一個不在 map 中的元素

程式碼如下：

func f(A []int) int {
mapping := make(map[int]struct{}, len(A))
for _, val := range A {
mapping[val] = struct{}{}
}
for i := 0; ; i++ {
if _, ok := mapping[i]; !ok {
return i
}
}
}

該方法的時間和空間複雜度都達到了 O(n), 理論上達到了最優。但是從實踐的角度考慮，hashmap 對空間的利用略超出了 O(n)，超出的範圍取決於負載因子。嚴格來說，這個方法並不是最優 O(n) 解法。那麼有沒有更優的解法呢？答案是有，但是需要一些想象力，或者歸納能力。

方案四：拿出紙和筆，找規律

我們可以隨意舉出幾個例子，對陣列和結果進行分析。假設我們對陣列已經排序，會有以下幾種情況：

情況一：

A = [1,2,4,9], output = 0
A = [2,3,4,9], output = 0
A = 任意不包含 0 的陣列，output = 0

情況二：

A = [], output = 0
A = [0], output = 1
A = [0,1], output = 2
A = [0,1,2], output = 3
A = [0,1,2,...,n-1], output = n

情況三：

A = [0,2,3,...,n-1], output = 1
A = [0,1,2,100,...,n-1], output = 3

對於所有情況，我們會發現一個共性：output <= n 。為什麼會出現這種情況？我們不妨逆向思考一下。假設有一個連續的自然數陣列[0,1,2,3,...n-1] ：

不改變這個陣列，則返回值是 n；
要改變一個元素，則必須從中取出一個自然數 i，然後替換成一個大於 n-1 的自然數。改變後的陣列返回 i；
改變多個元素，上一條仍然成立；
交換任意兩個元素，不影響返回值。

我們回到剛才提到的共性output <= n ，基於這個共性，我們可以認為陣列 A 中所有大於 n 的數是無意義的。換句話說，我們只關心 A 中<= n 的數字。

所以，解決方法來了：我們可以建立一個長度為 n+1 的 bool 陣列 B，遍歷 A 中所有元素 i 作為下標，設定 B[i]=true；然後找出 B 中第一個 false 的下標。程式碼如下：

func f(A []int) int {
n := len(A)
B := make([]bool, n+1, n+1)
for _, elem := range A {
if elem <= n {
B[elem] = true
}
}
for idx, val := range B {
if !val {
return idx
}
}
}

理論上這個方法的時間和空間複雜度都是 O(n)，在實際執行時，都要略優於基於 map 的實現。

小結

有時候，一支筆，一張紙，可能比想破腦袋都好用（高智商人士當我沒說）。

開頭我們提到一篇部落格對 Go 寫演算法的讚美之詞。經過這波實踐，依舊沒有發現比 C++ 更簡潔、更優美（手動狗頭）。Go 簡潔的語法讓每一行都看起來那麼短，但強制的大括號增加了程式碼行數，綜合起來和C++寫出來的效果旗鼓相當吧。