hello大家好呀，我是小樓。

上周參加了一個(gè)區(qū)的程序員技能比賽的初賽，其實(shí)就是算法比賽，雖然最后結(jié)果是過(guò)了初賽，但過(guò)程真是一言難盡啊。

這次的算法比賽和ACM非常類似，雖然我大學(xué)是數(shù)學(xué)專業(yè)，雖然大學(xué)也修過(guò)ACM這門課，但是我的算法是真的不行，很菜很菜的那種。

好在這次比賽是組（抱大腿）隊(duì)模式，3人一組，3個(gè)小時(shí)時(shí)間，一共7道算法題，1入門，2簡(jiǎn)單，2中等，2困難。

10分鐘寫出入門題，但...

由于我知道我比較菜，所以比賽一開(kāi)始，我就挑了一個(gè)看起來(lái)最簡(jiǎn)單的題目做，難題交給隊(duì)友。

結(jié)果是3個(gè)小時(shí)過(guò)去，這個(gè)看起來(lái)最簡(jiǎn)單的題目，愣是沒(méi)有做出來(lái)，下面就結(jié)合這道題講講我的心路歷程。

這道題的描述是這樣的：

看起來(lái)文字很多，其實(shí)要表達(dá)的很簡(jiǎn)單，就是輸入一些成績(jī)，每個(gè)成績(jī)輸進(jìn)去時(shí)，如果超過(guò)全班最好成績(jī)則輸出prefect，如果超過(guò)自己的最好成績(jī)則輸出great，如果沒(méi)超過(guò)自己最好成績(jī)則輸出bad。

是不是很簡(jiǎn)單？用一個(gè)max變量保存全班最好成績(jī)，用一個(gè)map保存每個(gè)人的最好成績(jī)，不就解決了嗎？

不過(guò)這是我第一次用這個(gè)oj系統(tǒng)，連用戶都是剛注冊(cè)的，所以我還特地看了一會(huì)輸入輸出的demo，這次比賽只能使用ACM的輸入輸出模式，例如如果用的是Go語(yǔ)言，輸入輸出應(yīng)該是這樣：

學(xué)會(huì)了輸入輸出之后，一口氣寫入如下的解法：

package main

import (
    "fmt"
)

func main() {
    var n int
    var name string
    var x float32
    var max float32
    scores := make(map[string]float32, n)

    fmt.Scan(&n)
    for i := 0; i < n; i++ {
        fmt.Scan(&name, &x)

        if x > max || i == 0 {
            fmt.Println("perfect")
            max = x
            scores[name] = x
        } else {
            if s, ok := scores[name]; ok {
                if x > s {
                    fmt.Println("great")
                    scores[name] = x
                } else {
                    fmt.Println("bad")
                }
            } else {
                fmt.Println("great")
                scores[name] = x
            }
        }
    }
}

在我正得意，覺(jué)得這題10分鐘就能解決的時(shí)候，提交上去的代碼竟然超時(shí)了，在比賽時(shí)沒(méi)有截圖，提交后顯示有少數(shù)用例超過(guò)了2秒，oj的判定原理是準(zhǔn)備一堆測(cè)試用例，如果全部通過(guò)則判定為通過(guò)，當(dāng)然這批測(cè)試用例肯定不是那么好通過(guò)的，設(shè)計(jì)者會(huì)出各種極端的case。

優(yōu)化map性能

調(diào)轉(zhuǎn)頭去仔細(xì)審題，果然時(shí)間和空間都有限制：

• 時(shí)間限制：C/C++ 1秒，其他語(yǔ)言2秒
• 空間限制：C/C++ 262144K，其他語(yǔ)言524288K
• 64bit IO Format: %lld

這題除了有map的讀寫，其他都是O(1)復(fù)雜度，性能不夠難道是map性能不夠？

如果是map的性能不夠，不夠在哪里呢？眾所周知，map的原理一般是這樣：

當(dāng)一些key存入map時(shí)，會(huì)先對(duì)key計(jì)算hash值，在map中找到對(duì)應(yīng)的hash槽，這個(gè)槽之后一般是個(gè)鏈表（有的語(yǔ)言也會(huì)做一些優(yōu)化成樹(shù)狀，這里我們簡(jiǎn)化為鏈表），因?yàn)椴煌膋ey的hash值可能會(huì)重復(fù)（沖突），沖突了只能把key排成一個(gè)鏈表，每次查找時(shí)都要遍歷鏈表。

所以有沒(méi)有可能，設(shè)計(jì)者給出了一堆hash值重復(fù)的name，數(shù)量又多，導(dǎo)致每次插入、查找時(shí)都要遍歷鏈表，性能下降，導(dǎo)致超時(shí)？

于是再仔細(xì)審題，我發(fā)現(xiàn)輸入的姓名和成績(jī)是有限制的：

• name保證長(zhǎng)度不超過(guò)6，僅由小寫英文字母組成，每個(gè)名字代表唯一一個(gè)同學(xué)
• x為1位小數(shù)，0≤x≤300

name最長(zhǎng)為6，且為小寫字母，這點(diǎn)給了我一點(diǎn)啟發(fā)，能不能讓查詢map變成O(1)復(fù)雜度？

顯然可以的，小寫字母范圍為a~z，如果看成數(shù)字就是1-26，也就是27進(jìn)制，所以每個(gè)name可以表示為一個(gè)27進(jìn)制的數(shù)，這樣就可以把所有人的成績(jī)放到一個(gè)大數(shù)組里去，按name的27進(jìn)制進(jìn)行O(1)的查找。

為什么是27進(jìn)制而不是26，因?yàn)閚ame沒(méi)說(shuō)是多少位，比如只有5位，那空出的一位怎么表示？只能用0表示了，a-z就是1-26，合起來(lái)是27進(jìn)制。

參考10進(jìn)制計(jì)算法則，27進(jìn)制應(yīng)該這樣計(jì)算（以roshi為例）：

計(jì)算出的值即為數(shù)組的下標(biāo)，那么這個(gè)數(shù)組的最大值是多少呢？

26 * 27^5 + 26 * 27^4 + 26 * 27^3 + 26 * 27^2 + 26 * 27^1 + 26 * 27^0

很容易算出來(lái)是：

387420488

需要這么大個(gè)數(shù)組，大概3億多，輸入成績(jī)是個(gè)1位小數(shù)，可以轉(zhuǎn)換為int，大概4個(gè)字節(jié)，掐指一算得 1513361KB，好像比要求的524288K多，先不管空間，寫一版跑跑看，萬(wàn)一能過(guò)呢？

很簡(jiǎn)單寫出代碼：

package main

import (
    "fmt"
)

func main() {
    var n int
    var name string
    var x int32

    fmt.Scan(&n)

    var scores [387420488]int32
    var exist [387420488]int32

    var max int32
    for i := 0; i < n; i++ {
        fmt.Scan(&name, &x)

        idx := mapIndex(name)

        if x > max || i == 0 {
            fmt.Printf("perfect\n")
            max = x
            scores[idx] = x
            exist[idx] = 1
        } else {
            if exist[idx] == 0 || x > scores[idx] {
                fmt.Printf("great\n")
                scores[idx] = x
                exist[idx] = 1
            } else {
                fmt.Printf("bad\n")
            }
        }
    }
}

var index27 = [6]int32{1, 27, 27 * 27, 27 * 27 * 27, 27 * 27 * 27 * 27}

func mapIndex(x string) int32 {
    var index int32
    for i := len(x) - 1; i >= 0; i-- {
        index = index + int32(x[i]-96)*index27[len(x)-1-i]
    }
    return index
}

結(jié)果竟然報(bào)錯(cuò)了，我當(dāng)時(shí)不理解，事后理解了，我們暫且不說(shuō)，后面會(huì)說(shuō)到原因。

就是因?yàn)檫@個(gè)報(bào)錯(cuò)不明不白，明明能測(cè)試通過(guò)，到底哪里理解有偏差？亦或是內(nèi)存超了？

優(yōu)化內(nèi)存占用

上面的代碼用到了2個(gè)數(shù)組，一個(gè)存最大值，一個(gè)存值是否存在，一個(gè)數(shù)組是1513361KB，2個(gè)就是3026722KB，是最大內(nèi)存限制的5.7倍

var scores [387420488]int32
var exist [387420488]int32

exist數(shù)組可以用boolean類型，分?jǐn)?shù)最大值0<=0<=300，int16足矣

如果是這個(gè)組合，將占用 1135020KB，是上限的2倍多，還是有點(diǎn)超，先試試：

還是一樣，難道是我算法有問(wèn)題？沒(méi)道理啊。到這里我實(shí)在是沒(méi)招了，3小時(shí)也耗盡了，比賽結(jié)束。

賽后思考

賽后，我拿著這道題去找了一位剛?cè)肼氉止?jié)的朋友，想著剛?cè)プ止?jié)應(yīng)該刷過(guò)不少題吧，果然大佬就是大佬，給出了一個(gè)有新意的思路，用前綴樹(shù)做：

每一個(gè)name都構(gòu)造出一個(gè)前綴樹(shù)，查找時(shí)最多只需要查找6次，內(nèi)存使用應(yīng)該也不會(huì)太多，算是時(shí)間與空間的一個(gè)平衡。

大佬還補(bǔ)充了一句：比賽還是比較特殊的，可能就是某一個(gè)case卡主了，而你要做的就是如何能把這個(gè)特殊的case也ac掉。

大佬的話似乎很有道理，于是我寫了一個(gè)前綴樹(shù)的版本：

package main

import (
    "fmt"
)

type treeNode struct {
    max  float32
    next [26]*treeNode
}

func main() {
    var n int
    var name string
    var x float32
    fmt.Scan(&n)

    var max float32
    tree := new(treeNode)
    for i := 0; i < n; i++ {
        fmt.Scan(&name, &x)

        if x > max || i == 0 {
            fmt.Println("perfect")
            max = x
            insert(tree, name, x)
        } else {
            if tmp := searchAndStoreMax(tree, name, x); tmp != -1 {
                if x > tmp {
                    fmt.Println("great")
                    insert(tree, name, x)
                } else {
                    fmt.Println("bad")
                }
            } else {
                fmt.Println("great")
                insert(tree, name, x)
            }
        }
    }
}

func insert(node *treeNode, name string, x float32) {
    for i := 0; i < len(name); i++ {
        idx := int32(name[i] - 'a')
        if node.next[idx] == nil {
            node.next[idx] = new(treeNode)
        }
        node = node.next[idx]
    }
    node.max = x
}

func searchAndStoreMax(node *treeNode, name string, x float32) float32 {
    for i := 0; i < len(name); i++ {
        idx := int32(name[i] - 'a')
        if node.next[idx] == nil {
            return -1
        }
        node = node.next[idx]
    }
    if x > node.max {
        tmp := node.max
        node.max = x
        return tmp
    }
    return node.max
}

結(jié)果又又又是超時(shí)，我服了。

終于發(fā)現(xiàn)問(wèn)題

后來(lái)我又嘗試了很多方法都不行，比如懷疑是不是Go的map性能不行，換成Java試試，結(jié)果還是不行。

最后我在網(wǎng)上搜索?？途W(wǎng)時(shí)發(fā)現(xiàn)了一個(gè)突破口（對(duì)，沒(méi)錯(cuò)，這次比賽是在牛客網(wǎng)上舉辦的）。

簡(jiǎn)單說(shuō)，?？途W(wǎng)的ACM模式輸入可能需要讀入一行然后再自己處理成想要的數(shù)據(jù)。

抱著懷疑的態(tài)度我試了下，果然，淦！用最開(kāi)始的map就能ac掉！雖然我也不知道這兩種輸入有什么區(qū)別。關(guān)鍵我還是用的網(wǎng)站上提示的輸入方式，確實(shí)太坑了。

正確的輸入方式如下：

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {
    var n int
    var name string
    var x float64
    input := bufio.NewScanner(os.Stdin)
    if input.Scan() {
        n, _ = strconv.Atoi(input.Text())
    }

    scores := make(map[string]float64, n)
    var max float64
    for i := 0; i < n; i++ {
        if input.Scan() {
            arr := strings.Split(input.Text(), " ")
            name = arr[0]
            x, _ = strconv.ParseFloat(arr[1], 32)
        }

        ...
    }
}

之前的想法屬于強(qiáng)行增加難度了~害！想了好幾天的題竟然敗在了輸入上，真是一言難盡！

之前的方法能行嗎

我把幾個(gè)版本的輸入改了之后，看看通過(guò)后的耗時(shí)和內(nèi)存

其中27進(jìn)制版本在改成正確的輸入后，露出了廬山真面目：內(nèi)存超了！

最后

過(guò)程雖然曲折，但最終還是解決了這個(gè)入門題，而且還嘗試著用幾種方法來(lái)解，雖然不盡如人意，但終究還是有點(diǎn)收獲。

當(dāng)然我們組的小伙伴也很給力，做出來(lái)3道題，我們最終的成績(jī)是排名進(jìn)了前10%，雖然我只貢獻(xiàn)了一點(diǎn)點(diǎn)（沒(méi)完全做出來(lái)也有得分，按通過(guò)的用例算，我這題大概拿到了90%的分），也算是可以了，而且還有一道題也可能是因?yàn)檫@個(gè)輸入被卡了，所以如果這兩道卡的題都做出來(lái)，估計(jì)排名能進(jìn)前三。

初賽算是過(guò)了，接下來(lái)準(zhǔn)備復(fù)賽，如果復(fù)賽還有好玩的事情，我再來(lái)寫一篇文章，哈哈。

這一言難盡的比賽，大家給個(gè)贊鼓勵(lì)下吧。