GO - 八皇后
最近被 GO 語言迷上了
GO 被譽為 21 世紀的 C 語言,
在上個世紀, Brian W. Kernighan和Dennis M. Ritchie 合著了 C 的聖經:
《The C Programming Language》
而今 Alan A. A. Donovan和K&R中的Brian W. Kernighan 也寫了一本 GO 的聖經
《The Go Programming Language》
也因為開發核心成員熟悉 C, GO 寫起來和 C 很像, 沒有甚麼違和感.
近年來, 很多新的開發項目, 如 容器技術 , 虛擬貨幣, .. , 也大多用 GO 來開發
而和 python 比較起來, GO 的執行效率高, 也可以用來開發底層程式,
如 cortex-m firmware ( https://studygolang.com/articles/22742 )
egc : https://github.com/ziutek/emgo/tree/master/egc
這樣就可以用在 Ameba 的開發
--
八皇后問題 - wiki
最近在餐桌上聊到這被同學笑 XD
在 西洋棋中, 皇后可以直線前進 (橫行/縱行/斜行)
所以原本八皇后的問題是, 在 一個 8x8 的棋盤上, 如何擺上八個皇后而相安無事
( 任直線上沒有兩個皇后)
解的個數:
為了能夠突顯各方式的差異, 我們把數量擴大為 14 皇后 - 14x14 棋盤
1. 一般寫法 : 約十秒
https://github.com/neojou/go-ameba/blob/master/myexample/2-8queens/8queens-normal-recurv.go
遞迴檢查所有可能,
$time go run 8queens-normal-recurv.go
total Sulutions: 365596
real: 0m9.475s
user: 0m9.295s
sys: 0m0.136s
2. bitwise
https://github.com/neojou/go-ameba/blob/master/myexample/2-8queens/8queens-bitwise-recurv.go
演算法很重要, 學好 bitwise, 效能上可以大幅提升, 在底層世界橫行無阻^^
可以發現, 改用 bitwise 方式, 程式變得很簡潔
(1) ^(maj_con|min_con| col_con)
- a ^ b : Bitwise XOR - a xor b
- ^c Bitwise NOT (same as 1111..1 ^ c)
所以 0 變 1, 1 變 0, 可以找到這條 row, 剩下還可以擺放的位置 (bit 1 代表可以擺放)
(2) bit = D & (-D)
可以找到最低位元非 0 的 bit
執行看看
$ time go run 8queens-bitwise-recurv.go
Total solutions: 365596
real 0m0.651s
user 0m0.566s
sys 0m0.050s
可以發現 半秒多就做完了, 快了近 20 倍...
3. GO 強項 - 平行處理
現在 cpu 大多已經都是多核的, (可以 cat /proc/cpuinfo 看看有幾核)
但上述程式仍跑在單核上,
以前程式要開 thread 有些複雜, 可能會需要搭配像 pthread 的 library
GO 的 go routine , 只要一個 go task() 就解決了, atomic / channel /..
這些也都是為了平行處理而設計出來.
(1) 一般寫法 改成 4 個平行 task 來處理
https://github.com/neojou/go-ameba/blob/master/myexample/2-8queens/8queens-parallel.go
$ time go run 8queens-parallel.go
total solutions: 365596
real 0m5.125s
user 0m17.255s
sys 0m0.068s
可以發現, 平行處理是個通解的演算法, 即便不曉得八皇后的最佳演算法,
也可以用大量的平行處理單元來加速, 硬生生地把時間從約 10 秒 縮短到 約 5秒
(2) bitwise 的平行處理
https://github.com/neojou/go-ameba/blob/master/myexample/2-8queens/8queens-bitwise-recurv.go
$ time go run 8queens-parallel-bitwise.go
total solutions: 365596
real 0m0.488s
user 0m0.659s
sys 0m0.084s
仍有幫助, 從 0.651 -> 0.488 , 節省了 25%
為什麼不是直接快 4 倍, 這是因為 thread 平行處理會有基本相關程式的消耗,
另一個是 atomic 處理結果或有更好的方式來做, 不會造成子線程互相等待.
但子 task 越花時間, 這部分的損耗越不明顯, 就可以往 4 倍逼近.
Linux device driver 是否能用平行處理來加速呢?
理論上是可以的, 現在也有些探討如何讓各 cpu 分別處理中斷...
但更想的是, 將來直接用 GO 刻一個作業系統... 之後有空時, 繼續先看看 egc.. ^^
GO 被譽為 21 世紀的 C 語言,
在上個世紀, Brian W. Kernighan和Dennis M. Ritchie 合著了 C 的聖經:
《The C Programming Language》
而今 Alan A. A. Donovan和K&R中的Brian W. Kernighan 也寫了一本 GO 的聖經
《The Go Programming Language》
也因為開發核心成員熟悉 C, GO 寫起來和 C 很像, 沒有甚麼違和感.
近年來, 很多新的開發項目, 如 容器技術 , 虛擬貨幣, .. , 也大多用 GO 來開發
而和 python 比較起來, GO 的執行效率高, 也可以用來開發底層程式,
如 cortex-m firmware ( https://studygolang.com/articles/22742 )
egc : https://github.com/ziutek/emgo/tree/master/egc
這樣就可以用在 Ameba 的開發
--
八皇后問題 - wiki
最近在餐桌上聊到這被同學笑 XD
在 西洋棋中, 皇后可以直線前進 (橫行/縱行/斜行)
所以原本八皇后的問題是, 在 一個 8x8 的棋盤上, 如何擺上八個皇后而相安無事
( 任直線上沒有兩個皇后)
解的個數:
為了能夠突顯各方式的差異, 我們把數量擴大為 14 皇后 - 14x14 棋盤
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | .. |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| U | 1 | 0 | 0 | 1 | 2 | 1 | 6 | 12 | 46 | 92 | 341 | 1,787 | 9,233 | 45,752 | .. |
| D | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2,680 | 14,200 | 73,712 | 365,596 | .. |
1. 一般寫法 : 約十秒
https://github.com/neojou/go-ameba/blob/master/myexample/2-8queens/8queens-normal-recurv.go
遞迴檢查所有可能,
$time go run 8queens-normal-recurv.go
total Sulutions: 365596
real: 0m9.475s
user: 0m9.295s
sys: 0m0.136s
2. bitwise
https://github.com/neojou/go-ameba/blob/master/myexample/2-8queens/8queens-bitwise-recurv.go
演算法很重要, 學好 bitwise, 效能上可以大幅提升, 在底層世界橫行無阻^^
可以發現, 改用 bitwise 方式, 程式變得很簡潔
(1) ^(maj_con|min_con| col_con)
- a ^ b : Bitwise XOR - a xor b
- ^c Bitwise NOT (same as 1111..1 ^ c)
所以 0 變 1, 1 變 0, 可以找到這條 row, 剩下還可以擺放的位置 (bit 1 代表可以擺放)
(2) bit = D & (-D)
可以找到最低位元非 0 的 bit
執行看看
$ time go run 8queens-bitwise-recurv.go
Total solutions: 365596
real 0m0.651s
user 0m0.566s
sys 0m0.050s
可以發現 半秒多就做完了, 快了近 20 倍...
3. GO 強項 - 平行處理
現在 cpu 大多已經都是多核的, (可以 cat /proc/cpuinfo 看看有幾核)
但上述程式仍跑在單核上,
以前程式要開 thread 有些複雜, 可能會需要搭配像 pthread 的 library
GO 的 go routine , 只要一個 go task() 就解決了, atomic / channel /..
這些也都是為了平行處理而設計出來.
(1) 一般寫法 改成 4 個平行 task 來處理
https://github.com/neojou/go-ameba/blob/master/myexample/2-8queens/8queens-parallel.go
$ time go run 8queens-parallel.go
total solutions: 365596
real 0m5.125s
user 0m17.255s
sys 0m0.068s
可以發現, 平行處理是個通解的演算法, 即便不曉得八皇后的最佳演算法,
也可以用大量的平行處理單元來加速, 硬生生地把時間從約 10 秒 縮短到 約 5秒
(2) bitwise 的平行處理
https://github.com/neojou/go-ameba/blob/master/myexample/2-8queens/8queens-bitwise-recurv.go
$ time go run 8queens-parallel-bitwise.go
total solutions: 365596
real 0m0.488s
user 0m0.659s
sys 0m0.084s
仍有幫助, 從 0.651 -> 0.488 , 節省了 25%
為什麼不是直接快 4 倍, 這是因為 thread 平行處理會有基本相關程式的消耗,
另一個是 atomic 處理結果或有更好的方式來做, 不會造成子線程互相等待.
但子 task 越花時間, 這部分的損耗越不明顯, 就可以往 4 倍逼近.
Linux device driver 是否能用平行處理來加速呢?
理論上是可以的, 現在也有些探討如何讓各 cpu 分別處理中斷...
但更想的是, 將來直接用 GO 刻一個作業系統... 之後有空時, 繼續先看看 egc.. ^^
留言
張貼留言