技術文章 » 參加了個演演算法比賽，真是一言難盡啊

參加了個演演算法比賽，真是一言難盡啊

2022-09-05 15:00:32

hello大家好呀，我是小樓。

上週參加了一個區的程式設計師技能比賽的初賽，其實就是演演算法比賽，雖然最後結果是過了初賽，但過程真是一言難盡啊。

這次的演演算法比賽和ACM非常類似，雖然我大學是數學專業，雖然大學也修過ACM這門課，但是我的演演算法是真的不行，很菜很菜的那種。

好在這次比賽是組（抱大腿）隊模式，3人一組，3個小時時間，一共7道演演算法題，1入門，2簡單，2中等，2困難。

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

由於我知道我比較菜，所以比賽一開始，我就挑了一個看起來最簡單的題目做，難題交給隊友。

結果是3個小時過去，這個看起來最簡單的題目，愣是沒有做出來，下面就結合這道題講講我的心路歷程。

這道題的描述是這樣的：

看起來文字很多，其實要表達的很簡單，就是輸入一些成績，每個成績輸進去時，如果超過全班最好成績則輸出prefect，如果超過自己的最好成績則輸出great，如果沒超過自己最好成績則輸出bad。

是不是很簡單？用一個max變數儲存全班最好成績，用一個map儲存每個人的最好成績，不就解決了嗎？

不過這是我第一次用這個oj系統，連使用者都是剛註冊的，所以我還特地看了一會輸入輸出的demo，這次比賽只能使用ACM的輸入輸出模式，例如如果用的是Go語言，輸入輸出應該是這樣：

學會了輸入輸出之後，一口氣寫入如下的解法：

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
			}
		}
	}
}

在我正得意，覺得這題10分鐘就能解決的時候，提交上去的程式碼竟然超時了，在比賽時沒有截圖，提交後顯示有少數用例超過了2秒，oj的判定原理是準備一堆測試用例，如果全部通過則判定為通過，當然這批測試用例肯定不是那麼好通過的，設計者會出各種極端的case。

優化map效能

調轉頭去仔細審題，果然時間和空間都有限制：

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

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

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

當一些key存入map時，會先對key計算hash值，在map中找到對應的hash槽，這個槽之後一般是個連結串列（有的語言也會做一些優化成樹狀，這裡我們簡化為連結串列），因為不同的key的hash值可能會重複（衝突），衝突了只能把key排成一個連結串列，每次查詢時都要遍歷連結串列。

所以有沒有可能，設計者給出了一堆hash值重複的name，數量又多，導致每次插入、查詢時都要遍歷連結串列，效能下降，導致超時？

於是再仔細審題，我發現輸入的姓名和成績是有限制的：

  • name保證長度不超過6，僅由小寫英文字母組成，每個名字代表唯一一個同學
  • x為1位小數，0≤x≤300

name最長為6，且為小寫字母，這點給了我一點啟發，能不能讓查詢map變成O(1)複雜度？

顯然可以的，小寫字母範圍為a~z，如果看成數位就是1-26，也就是27進位制，所以每個name可以表示為一個27進位制的數，這樣就可以把所有人的成績放到一個大陣列裡去，按name的27進位制進行O(1)的查詢。

為什麼是27進位制而不是26，因為name沒說是多少位，比如只有5位，那空出的一位怎麼表示？只能用0表示了，a-z就是1-26，合起來是27進位制。

參考10進位制計演演算法則，27進位制應該這樣計算（以roshi為例）：

計算出的值即為陣列的下標，那麼這個陣列的最大值是多少呢？

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

很容易算出來是：

387420488

需要這麼大個陣列，大概3億多，輸入成績是個1位小數，可以轉換為int，大概4個位元組，掐指一算得 1513361KB，好像比要求的524288K多，先不管空間，寫一版跑跑看，萬一能過呢？

很簡單寫出程式碼：

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
}

結果竟然報錯了，我當時不理解，事後理解了，我們暫且不說，後面會說到原因。

就是因為這個報錯不明不白，明明能測試通過，到底哪裡理解有偏差？亦或是記憶體超了？

優化記憶體佔用

上面的程式碼用到了2個陣列，一個存最大值，一個存值是否存在，一個陣列是1513361KB，2個就是3026722KB，是最大記憶體限制的5.7倍

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

exist陣列可以用boolean型別，分數最大值0<=0<=300，int16足矣

大小 範圍
int8 1位元組 -128 ~ 127
int16 2位元組 -32768 ~ 32767
int32 4位元組 -2147483648 ~ 2147483647

如果是這個組合，將佔用 1135020KB，是上限的2倍多，還是有點超，先試試：

還是一樣，難道是我演演算法有問題？沒道理啊。到這裡我實在是沒招了，3小時也耗盡了，比賽結束。

賽後思考

賽後，我拿著這道題去找了一位剛入職位元組的朋友，想著剛去位元組應該刷過不少題吧，果然大佬就是大佬，給出了一個有新意的思路，用字首樹做：

每一個name都構造出一個字首樹，查詢時最多隻需要查詢6次，記憶體使用應該也不會太多，算是時間與空間的一個平衡。

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

大佬的話似乎很有道理，於是我寫了一個字首樹的版本：

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
}

結果又又又是超時，我服了。

終於發現問題

後來我又嘗試了很多方法都不行，比如懷疑是不是Go的map效能不行，換成Java試試，結果還是不行。

最後我在網上搜尋牛客網時發現了一個突破口（對，沒錯，這次比賽是在牛客網上舉辦的）。

簡單說，牛客網的ACM模式輸入可能需要讀入一行然後再自己處理成想要的資料。

抱著懷疑的態度我試了下，果然，淦！用最開始的map就能ac掉！雖然我也不知道這兩種輸入有什麼區別。關鍵我還是用的網站上提示的輸入方式，確實太坑了。

正確的輸入方式如下：

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)
		}

		...
	}
}

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

之前的方法能行嗎

我把幾個版本的輸入改了之後，看看通過後的耗時和記憶體

版本 是否通過 耗時 記憶體
map版 是 315ms 10096KB
27進位製版 否 - -
字首樹版 是 433ms 43720KB

其中27進位製版本在改成正確的輸入後，露出了廬山真面目：記憶體超了！

最後

過程雖然曲折，但最終還是解決了這個入門題，而且還嘗試著用幾種方法來解，雖然不盡如人意，但終究還是有點收穫。

當然我們組的小夥伴也很給力，做出來3道題，我們最終的成績是排名進了前10%，雖然我只貢獻了一點點（沒完全做出來也有得分，按通過的用例算，我這題大概拿到了90%的分），也算是可以了，而且還有一道題也可能是因為這個輸入被卡了，所以如果這兩道卡的題都做出來，估計排名能進前三。

初賽算是過了，接下來準備複賽，如果複賽還有好玩的事情，我再來寫一篇文章，哈哈。

這一言難盡的比賽，大家給個贊鼓勵下吧。

搜尋關注微信公眾號"捉蟲大師"，後端技術分享，架構設計、效能優化、原始碼閱讀、問題排查、踩坑實踐。