碼農界有古話(好吧,沒那麼古),"編程即算法",還有一句話,"數據結構即算法",不對,沒有這句話。哦,好把是蟲蟲搞錯了。應該是"數據結和算法",我承認我為了作強調數據結構的重要性偷換了下概念,實際上對於一個開發者來說實際中遇到最重要的算法問題都是數據結構的問題。
作為一名軟件開發人員,如何理解和實現數據結構來解決實際中遇到的問題,直接反映一個開發人員能力高低。
數據機構也能幫助我們理解許多複雜的核心CS概念,包括OS,網絡和分佈式系統等,比如Linux的進程管理歸根到語言層都是一個個的數據結構哈希鏈表:
基本上我們現在都不會也無需從零開始編寫算法。總是可以找到大量經過優化和測試的庫可供使用,比如C++中的Boost,go-datastructures等。
本文中蟲蟲會給大家價紹一個數據結構可視化庫Dataviz,通過對其圖形化,幫助我們更好的理解golang的各種數據結構。
Dataviz簡介
Dataviz是一個數據結構可視化庫,通過對 Graphviz的可視化功能用golang來重新打包,已實現在golang中實現基本數據結構的可視化。它還提供示大量的實例來幫助我們學習和數據結構的可視化。
那麼讓我們從簡單例子,堆來開始:
堆(heap)
現在,讓我們直接利用Dataviz來構建一個堆:
package main
import (
bheap "github/Arafatk/dataviz/trees/binaryheap"
)
func main() {
heap := bheap.NewWithIntComparator()
heap.Push(3)
heap.Push(19)
heap.Push(17)
heap.Push(2)
heap.Push(7)
heap.Push(1)
heap.Push(26)
heap.Push(35)
heap.Visualizer("heap.png")
}
這個函數輸出一個簡單的png文件,顯示了可視化的堆。
利用Dataviz可視化另一個好處是,不僅可以展示數據結構的當前狀態,還可以動態顯示數據結構中節點的增長和減少的過程。比如,如果我們從上面的不停的pop元素直到為空,這個過程用可以生成一個gif:
注意,Dataviz支持所有類型的標準堆操作,例如push,pop,empty,clear,size,top以及其他操作,比如逆向操作函數等。
讓我們看看一個相對複雜一點的數據結構,紅黑樹。
紅黑樹
紅黑樹的真正優勢在於支持在O(logN)情況下進行插入,刪除和搜索。讓我們編碼來實現如何將幾個數字映射到幾個字符以及如何將其可視化。
package main
import (
rbt "github/Arafatk/dataviz/trees/redblacktree"
)
func main() {
tree := rbt.NewWithIntComparator()
tree.Put(5, "e")
tree.Put(6, "f")
tree.Put(7, "g")
tree.Put(3, "c")
tree.Put(4, "d")
tree.Put(1, "x")
tree.Put(2, "b")
tree.Put(1, "a") //overwrite
tree.Visualizer("out.png")
}
這會生成如下的一張圖out.png:
我們還可以瞭解如何逐步構建並查看每個紅黑樹如何通過添加新節點來構建。
注意紅黑樹的基本屬性:
1、每個節點都有一個顏色屬性,每個節點或是紅的或是黑的
2、根節點必須是黑的
3、每個葉子節點(nil節點)為黑
4、如果一個節點為紅的,那麼它的兩個孩子都是黑的
5、每個節點到它子孫葉子節點的路徑上的黑色節點個數是相同的
下面的gif展示了逐步構建紅黑樹的過程。注意上以上規則如何實現的:
利用dataviz還可以做得其他有意義的事情:構建棧,AVL樹,Btrees及更多的事情
使用DataViz構建棧(Stack)
使用Dataviz構建B樹
好了,今天的內容就介紹完了,請關注蟲蟲一起學習。
閱讀更多 蟲蟲安全 的文章