Huffman codingを例にGolang実用主義を見る

2578 ワード

異なるプログラミングは異なる問題を解決するための考え方である.
一つの問題を解決するには多くの考えがあります.例えば、
  • プロセス式(C言語):問題解決の仕方をいくつかのステップに分解してデータを制御
  • オブジェクト指向式(Java/Ruby):オブジェクトを基本単位とし、その動作制御の内部状態を定義し、異なるオブジェクト間の連携により問題を解決
  • 関数式(Lisp):すべてが関数であり、一貫した考え方で過程を定義し、よく再帰する
  • 組み合わせ式:異なる解決方法を組み合わせて、golangは常にオブジェクト向けと過称式を組み合わせている
  • 例:Huffmanエンコーディング
    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もプロセス式のmakeSortedNodesmakeFuffManTreeそしてfunc (n Node) traverse(code string, visit func(rune, string))の再帰呼び出し,高次関数パラメータなどが見られる.だからgolangはもっと実用性を重視しています.
    ここでは実装の観点からHuffman符号化の対外インタフェースを定義するだけでは、汎用性と効率性にはまだ十分ではありません.golangのiopackageを参照してEncodeをEncode(v []byte, w io.Writer) (int, error)標準入出力のpackageに直接アクセスできます.もちろん、ここでは内部実装の調整をします.丈夫で効率的にしたい場合は、bufferと組み合わせてバッファを実現することもできます.
    プロジェクトフルコード:github
    関連読書:Huffman codingを例に関数式プログラミングを見る