關(guān)于“你們的”十一

關(guān)于你們的十一，反正我是睜一只眼閉一只眼，我沒(méi)看見(jiàn)好吧?？粗笥讶锏男』锇楦鞣N秀美食，秀美景，秀自己的狗有多蠢，特別是國(guó)內(nèi)的同學(xué)朋友，不管上不上班，反正這個(gè)假他們肯定是放的。而我卻在圖書館的角落默默地寫著算法作業(yè)。一個(gè)為期2周的小 project，看題目也知道了，就倆簡(jiǎn)單的算法，網(wǎng)上也有很多相關(guān)的教程，那我為什么還要寫這篇文章呢？

首先，我寫的是“裝甲”進(jìn)化版的 Dijkstra & Floyd。用的是 Swift（雖然教授不厭其煩的說(shuō) C 是最好的學(xué)算法的語(yǔ)言），我本科 CS 用的 C++，實(shí)在是不喜歡 C++。我先介紹一下教授的要求吧。

要求太長(zhǎng)了，想看一看的點(diǎn)這里，我簡(jiǎn)化一下：

• 2 個(gè)算法，Dijkstra 和 Floyd 最短路徑算法

• 3 種數(shù)據(jù)結(jié)構(gòu)，2D Array, 1D Array, Linked List
• 2 種 Test cases, 一種 Complete Graph, 一種 Sparse Graph
• 12 張圖，對(duì)應(yīng)上面的 2*3*2＝12 個(gè)程序的時(shí)間復(fù)雜度

我上課聽(tīng)到這個(gè)要求后的第一反應(yīng)是我要做一個(gè) iOS App。教授是要我們 plot 出 12 張圖，我如果不用 iOS 作圖，難道還要用 R 像我們上 Machine Learning 那樣做圖嗎？用大數(shù)據(jù)的軟件做這種圖，有點(diǎn)蠢的。

Paste_Image.png

BTW, 文章同步更新在我的博客，歡迎訪問(wèn)。

2 個(gè)算法，3 個(gè)數(shù)據(jù)結(jié)構(gòu)

關(guān)于這兩個(gè)算法的思路，與 2D array 和 Linked list 版本的教程，我強(qiáng)烈推薦 Geeksforgeeks，這是 2D array 版本的，這是 Linked List 版本的；Floyd 的呢，網(wǎng)上我只找到了 2D array 版本的。那 1D 和 Linked list 怎么辦呢？如果你也是喜歡 Swift, 想用學(xué)一些 Swift 的數(shù)據(jù)結(jié)構(gòu)和算法，我強(qiáng)烈推薦這兩個(gè)網(wǎng)站：Swift Algorithm Club，SwiftStructures。

我在這里就講一講上面提供的教程里沒(méi)有的幾個(gè)程序吧，1D 的 Dijkstra，1D 和 Linked list 的 Floyd。

1D Array

用 1D 的原因是因?yàn)橛袝r(shí)候我們的數(shù)據(jù)會(huì)非常大，如果只存?。僮饕话氲臄?shù)據(jù)，會(huì)節(jié)省很多的時(shí)間和空間。所以這里 1D 的主要思路就是如何將 2D 的數(shù)據(jù) map 到 1D 上面。

比如這么一個(gè) 2D array：

我們?nèi)∷纳习氩糠謥?lái)操作。在 2D 中 0 行 4 列的數(shù)是 6，那么在 1D 中 6 是第幾個(gè)？是第 3 個(gè)（所有 index 都從 0 開(kāi)始），就有 (0, 4) -> 3，再來(lái)一組，第 1 行 2 列的 3，在 1D 中是第 4 個(gè)，(1, 2) -> 4。如此計(jì)算出 (i, j) -> x，這個(gè) x 是多少？如果數(shù)組共有 n 行 n 列，那么 x = (2n - 1- i)*i/2 + j - i - 1。這是求解 1D array 的 Dijkstra 和 Floyd 的關(guān)鍵。我們這次用的是無(wú)向圖，所以對(duì)應(yīng)的還有 (2*n-1-j)*j/2+i-j-1，判斷條件就是 i < j 還是 i > j。

我用 Dijkstra 的代碼來(lái)說(shuō)明：

func dijkstra1D(_ graph: [Int], _ src: Int)
{
    let V = Int(sqrt(Double(2 * graph.count))) + 1
    var dist = Array(repeating: Int.max, count: V)
    var sptSet = Array(repeating: false, count: V)
    dist[src] = 0
    for _ in 0..<V-1
    {
        let u = minDistance(dist, sptSet, V)
        sptSet[u] = true
        for v in 0..<V {
            let index = (2*V - 1 - u)*u/2+v-u-1
            let temp = (2*V - 1 - v)*v/2+u-v-1
            if sptSet[v] == false && dist[u] != Int.max && dist[u] + graph[index] < dist[v] {
                if u > v {
                    if graph[temp] > 0 && dist[u] + graph[temp] < dist[v] {
                        dist[v] = dist[u] + graph[temp]
                    }
                } else if u < v {
                    if graph[index] > 0 {
                        dist[v] = dist[u] + graph[index]
                    }
                }
            }
        }
    }
//    print4(dist, V)
}

中間的 if u > v 和 else if u < v 里面的就是我上面說(shuō)到的關(guān)鍵部分了。

Linked List

Dijkstra 的 Linked List 版本上面已經(jīng)提供了教程了，應(yīng)該沒(méi)人比 geeksforgeeks 寫的更好了。。我這里稍微講一下 Floyd 版本的。因?yàn)?Floyd 的算法思路還是比較簡(jiǎn)單的，關(guān)鍵是要遍歷很多次整個(gè)圖，因?yàn)?2D 里面它就有 3 個(gè)循環(huán)。我是弄了個(gè)數(shù)組，把鏈表轉(zhuǎn)成了 2D 的來(lái)解決了，好像這樣不太好，因?yàn)檫@樣的話鏈表的存儲(chǔ)優(yōu)勢(shì)就完全沒(méi)了，到最后還是轉(zhuǎn)成了 2D 來(lái)做。但用我們教授的話來(lái)說(shuō)就是，每個(gè)程序的實(shí)現(xiàn)都要按照要求來(lái)做，要求不同，實(shí)現(xiàn)也會(huì)有不同。。。這里我們教授的 input 輸入沒(méi)有很復(fù)雜，所以專成 2D 完全可以 ?? 下面就是代碼的主要部分。

var dist = Array(repeating: Array(repeatElement(Int(Int32.max), count: V)), count: V)
    var mark = Array(repeating: false, count: V)
    var u = 0, v = 0
    for i in 0..<V {
        var cur = graph.array[i].head
        u = i
        mark[u] = true
        while cur != nil {
            v = cur!.dest
            if mark[v] == false {
                dist[u][v] = cur!.weight
                dist[v][u] = cur!.weight
            }
            cur = cur?.next
        }
    }

2 種類型的圖

Complete Graph 用教授的話定義就是:

a graph with a link between every pair of nodes

而 Sparse 呢：

a graph with exactly n-1 links

生成這兩種圖的時(shí)候，我們需要生成對(duì)應(yīng)于 2D, 1D 和 linked list 版本的，所以會(huì)有 6 個(gè) function。程序有點(diǎn)長(zhǎng)，就不放上來(lái)了。講幾個(gè)注意點(diǎn)，因?yàn)槭菬o(wú)向圖，所以都要注意兩邊的三角區(qū)域都要賦值，比如這個(gè) complete graph 的：

completeGraph[i][j] = rand
completeGraph[j][i] = rand

生成 sparse graph 的時(shí)候，我們畫一下圖就可以知道，從 0 開(kāi)始，隨機(jī)選出下一個(gè)點(diǎn)，假如是 4*4 的表格，下個(gè)點(diǎn)是 3，那么我們?cè)龠x下個(gè)點(diǎn)的時(shí)候，需要從 1 和 2 中選，這里我們需要一個(gè)類似于 chosenNodes 的標(biāo)記，如果隨機(jī)到的是已經(jīng)選過(guò)的，我們有兩種方法，一種是在隨即一遍，還有一種是取模，很明顯取模會(huì)快很多，特別是剩下的數(shù)不多的時(shí)候。下面是生成 sparse graph 的函數(shù)：

func sparse(_ n: Int) -> [[Int]]
    {
        var sparseGraph = Array(repeating: Array(repeatElement(0, count: n)), count:n)
        var chosenNodes = Array(repeating: false, count: n)
        var i = 0
        while chosenNodes.contains(false) {
            chosenNodes[i] = true
            if chosenNodes.contains(false) {
                var pickJ = Int(arc4random_uniform(UInt32(n)))
                if chosenNodes[pickJ] == true {
                    while chosenNodes[pickJ] == true {
                        pickJ = (pickJ + 1)%(n)
                    }
                }
                let j = pickJ
                let rand = Int(arc4random_uniform(UInt32(n))) + 1
                sparseGraph[i][j] = rand
                sparseGraph[j][i] = rand
                i = j
            }
        }
        return sparseGraph
    }

基于鏈表的圖的生成很簡(jiǎn)單，只要根據(jù)循環(huán)用幾次 addEdge() 就可以了。

使用 Charts 作圖

關(guān)于如何使用 Charts，這里有一篇很好的教程，因?yàn)樗窃?swift 3 之前寫的，所以語(yǔ)法有點(diǎn)小錯(cuò)誤，有疑問(wèn)的可以看看我的 project，當(dāng)然最權(quán)威的還是官方的 github。

如您在上面所看到的，我做的是 Complete graph 和 Sparse graph 兩種分開(kāi)的折線圖，比較各算法在同樣的圖上的速度。我本來(lái)想過(guò)很多種分類作圖的方式，感覺(jué)還是這樣比較直觀。gif 試了好幾遍沒(méi)放上來(lái)，只好放圖了，下面放一張 sparse 的高清圖：

Paste_Image.png

如果喜歡我的分享，請(qǐng)點(diǎn)贊??和關(guān)注，也可以 tip 一波安撫一下國(guó)慶敲代碼的心。