Huffman codingを例にGolang実用主義を見る
2578 ワード
異なるプログラミングは異なる問題を解決するための考え方である.
一つの問題を解決するには多くの考えがあります.例えば、プロセス式(C言語):問題解決の仕方をいくつかのステップに分解してデータを制御 オブジェクト指向式(Java/Ruby):オブジェクトを基本単位とし、その動作制御の内部状態を定義し、異なるオブジェクト間の連携により問題を解決 関数式(Lisp):すべてが関数であり、一貫した考え方で過程を定義し、よく再帰する 組み合わせ式:異なる解決方法を組み合わせて、golangは常にオブジェクト向けと過称式を組み合わせている 例:Huffmanエンコーディング
Golangでオブジェクト指向式とプロシージャ式を組み合わせます.
まず、package全体(大きなオブジェクトとみなされる)の入力と出力を決定する必要があります.
入力:
出力:
データ構造の定義
パッケージの対外インタフェースの定義
具体的な実現構想
以上の実現形態から,オブジェクト向けのノードやTreeもプロセス式の
ここでは実装の観点からHuffman符号化の対外インタフェースを定義するだけでは、汎用性と効率性にはまだ十分ではありません.golangの
プロジェクトフルコード:github
関連読書:Huffman codingを例に関数式プログラミングを見る
一つの問題を解決するには多くの考えがあります.例えば、
Golangでオブジェクト指向式とプロシージャ式を組み合わせます.
まず、package全体(大きなオブジェクトとみなされる)の入力と出力を決定する必要があります.
入力:
map[rune]int
、そのうちrune
はgolangの文字タイプ、つまり私たちが符号化するデータ型、int
この文字が出現した回数出力:
map[rune]string
、そのうちstring
対応する01文字列符号化結果.データ構造の定義
type Node struct {
Value rune
Weight int
LeftChild *Node
RightChild *Node
}
// Nodes Node weight
type Nodes []Node
// Tree Huffman
type Tree struct {
Root *Node
}
パッケージの対外インタフェースの定義
func Encode(priorityMap map[rune]int) map[rune]string {
stortedNodes := makeSortedNodes(priorityMap)
hfmTree := makeFuffManTree(stortedNodes)
return hfmTree.encode()
}
具体的な実現構想
// makeSortedNodes []Node
func makeSortedNodes(priorityMap map[rune]int) []Node {
//
return hfmNodes
}
// makeFuffManTree Nodes Huffman ,
func makeFuffManTree(nodes Nodes) *Tree {
if len(nodes) < 2 {
panic("Must contain 2 or more emlments")
}
//
return hfmTree
}
// encode tree ,
func (tree Tree) encode() map[rune]string {
var initialCode string
encodeMap := make(map[rune]string)
tree.Root.traverse(initialCode, func(value rune, code string) {
encodeMap[value] = code
})
return encodeMap
}
// traverse ,
func (n Node) traverse(code string, visit func(rune, string)) {
if leftNode := n.LeftChild; leftNode != nil {
leftNode.traverse(code+"0", visit)
} else {
visit(n.Value, code)
return
}
n.RightChild.traverse(code+"1", visit)
}
以上の実現形態から,オブジェクト向けのノードやTreeもプロセス式の
makeSortedNodes
とmakeFuffManTree
そしてfunc (n Node) traverse(code string, visit func(rune, string))
の再帰呼び出し,高次関数パラメータなどが見られる.だからgolangはもっと実用性を重視しています.ここでは実装の観点からHuffman符号化の対外インタフェースを定義するだけでは、汎用性と効率性にはまだ十分ではありません.golangの
io
packageを参照してEncodeをEncode(v []byte, w io.Writer) (int, error)
標準入出力のpackageに直接アクセスできます.もちろん、ここでは内部実装の調整をします.丈夫で効率的にしたい場合は、bufferと組み合わせてバッファを実現することもできます.プロジェクトフルコード:github
関連読書:Huffman codingを例に関数式プログラミングを見る