xmlからGo strcutを生成する

ツール紹介です。 Web APIのレスポンスはだいたいjsonで返ってくるので、go structを自動生成してくれる JSON-to-Goが便利でよく使っているのですが、今回はxmlで同じことをしたいと思い、chidleyというツールを触ってみたので、使い方をまとめます。

インストール

いつものごとく、go getしましょう。

# go get github.com/gnewton/chidley

使い方

READMEにもありますが、同じサンプル(test.xmlとします)を借ります。

<people>

  <person>
    <name>bill</name>
    <age>37</age>
    <married>true</married>
  </person>

  <person>
    <name>sarah</name>
    <age>24</age>
    <married>false</married>
  </person>

</people>

-Gオプションを付けることでxmlからGo structが生成されます。

# chidley -G test.xml

type ChiChidleyRoot314159 struct {
    ChiPeople *ChiPeople `xml:" people,omitempty" json:"people,omitempty"`
}

type ChiAge struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type ChiMarried struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type ChiName struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type ChiPeople struct {
    ChiPerson []*ChiPerson `xml:" person,omitempty" json:"person,omitempty"`
}

type ChiPerson struct {
    ChiAge *ChiAge `xml:" age,omitempty" json:"age,omitempty"`
    ChiMarried *ChiMarried `xml:" married,omitempty" json:"married,omitempty"`
    ChiName *ChiName `xml:" name,omitempty" json:"name,omitempty"`
}

型付きでコンバート

上記のようにデフォルトではint型やbool型もすべてstring型として解釈されます。-tオプションで型まで含めたコンバートを行ってくれます。

# chidley -G -t test.xml

type ChiChidleyRoot314159 struct {
    ChiPeople *ChiPeople `xml:" people,omitempty" json:"people,omitempty"`
}

type ChiAge struct {
    Text int8 `xml:",chardata" json:",omitempty"`
}

type ChiMarried struct {
    Text bool `xml:",chardata" json:",omitempty"`
}

type ChiName struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type ChiPeople struct {
    ChiPerson []*ChiPerson `xml:" person,omitempty" json:"person,omitempty"`
}

type ChiPerson struct {
    ChiAge *ChiAge `xml:" age,omitempty" json:"age,omitempty"`
    ChiMarried *ChiMarried `xml:" married,omitempty" json:"married,omitempty"`
    ChiName *ChiName `xml:" name,omitempty" json:"name,omitempty"`
}

age24,37int8型として解釈されていますが、chidleyでは以下のように記載されているとおり、できるだけ小さい型に合わせようとします。 今回は-128127の範囲に収まっているために、int8型となります。

chidley tries to fit the smallest Go type. For example, if all instances of a tag contain a number, and all instances are -128 to 127, then it will use an int8 in the Go struct.

接頭辞を変更する

上記の結果をみるとわかるように型の接頭辞にChiがつきます。これを変更するには-eオプションを用います。 ただし、xmlデコーダなど外部からも参照できるように大文字から始める必要があるので注意してください。

# chidley -G -e "Prefix" test.xml

type PrefixChidleyRoot314159 struct {
    PrefixPeople *PrefixPeople `xml:" people,omitempty" json:"people,omitempty"`
}

type PrefixAge struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type PrefixMarried struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type PrefixName struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type PrefixPeople struct {
    PrefixPerson []*PrefixPerson `xml:" person,omitempty" json:"person,omitempty"`
}

type PrefixPerson struct {
    PrefixAge *PrefixAge `xml:" age,omitempty" json:"age,omitempty"`
    PrefixMarried *PrefixMarried `xml:" married,omitempty" json:"married,omitempty"`
    PrefixName *PrefixName `xml:" name,omitempty" json:"name,omitempty"`
}

ちなみに""を指定してあげることで接頭辞をなしにすることもできます。

chidley -G -e "" test.xml
type ChidleyRoot314159 struct {
    People *People `xml:" people,omitempty" json:"people,omitempty"`
}

type Age struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type Married struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type Name struct {
    Text string `xml:",chardata" json:",omitempty"`
}

type People struct {
    Person []*Person `xml:" person,omitempty" json:"person,omitempty"`
}

type Person struct {
    Age *Age `xml:" age,omitempty" json:"age,omitempty"`
    Married *Married `xml:" married,omitempty" json:"married,omitempty"`
    Name *Name `xml:" name,omitempty" json:"name,omitempty"`
}

他にも色々なオプションがありますが、自分が使いそうなところを中心にまとめました。

Reference

GolangでHopscotch Hashingを実装してみた

※2017/8/13 タイトルにtypoがあったので修正しました。 [前]GolfingでHopscotch Hashingを実装してみた [後]GolangでHopscotch Hashingを実装してみた

前回のCuckoo Hashingの実装記事から少し間が空きましたが、今回はHopscotch Hashingを実装してみようと思います。

Hopscotch Hashingとは

テーブルのハッシュ衝突を解決する目的で、Mauriceらによって導入された手法です。 論文はこちら

Hopscotch Hashingでは、各bucketにitemとbitmapを持ちます。 今回の実装では、以下のようにしています。 Hはビットマップの大きさです。

type bucket struct {
    item   int64
    bitmap [H]bool
}

type Hopscotch []bucket

itemは、InsertLookupDeleteしたい要素そのものです。 bitmapは、ハッシュ値が衝突した場合に、そのbucketから見てからH-1番目までに、その要素が存在するかを表します。

図にすると以下のようなイメージです。

f:id:cipepser:20170805134720p:plain

itemaとitembが同じハッシュ値を持っていることを保証します。 この構造を維持することで、Lookupbitmap1になっているところのitemのみをチェックすればよいので、 計算量がO(H)となります。

DeleteLookupして対象となるitemがあれば、それを削除し、対応するbitmap0としてあげればよいので簡単です。 問題はInsertですが、次節に記載します。

Insertのアルゴリズム

Hopscotch Hashingでは、ハッシュ衝突後に、空いているbucketを線形探索で探し、その空きbucketを順々に最初のハッシュ値のindexからH-1番目以内まで持ってくるということをします。 言葉だけではわかりづらいので図にすると以下のようになります。

f:id:cipepser:20170805142610p:plain

空きbucketが見つからない場合は、サイズを大きくしてテーブルを作り直してあげる必要があります。 今回の実装では2倍ずつ増やすことにしました。

実装

以上を実装したものが以下になります。

gisteb0ae2b452b62984e8b54c6298321238

テストも含めて、githubにあげてあります。

実行

テーブルサイズを10、bitmapのサイズを2として、1から10までを挿入してみます。

gist806d61d8cd2522a4a797838694069293

実行結果

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {1 [true false]}
2   |  {0 [false false]}
3   |  {0 [false false]}
4   |  {0 [false false]}
5   |  {0 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {0 [false false]}
9   |  {0 [false false]}

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {1 [true false]}
2   |  {0 [false false]}
3   |  {0 [false false]}
4   |  {2 [true false]}
5   |  {0 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {0 [false false]}
9   |  {0 [false false]}

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {1 [true false]}
2   |  {3 [true false]}
3   |  {0 [false false]}
4   |  {2 [true false]}
5   |  {0 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {0 [false false]}
9   |  {0 [false false]}

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {1 [true false]}
2   |  {3 [true false]}
3   |  {0 [false false]}
4   |  {2 [true true]}
5   |  {4 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {0 [false false]}
9   |  {0 [false false]}

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {1 [true false]}
2   |  {3 [true false]}
3   |  {0 [false false]}
4   |  {2 [true true]}
5   |  {4 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {5 [true false]}
9   |  {0 [false false]}

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {1 [true true]}
2   |  {6 [false true]}
3   |  {3 [false false]}
4   |  {2 [true true]}
5   |  {4 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {5 [true false]}
9   |  {0 [false false]}

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {1 [true true]}
2   |  {6 [false true]}
3   |  {3 [false false]}
4   |  {2 [true true]}
5   |  {4 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {5 [true false]}
9   |  {7 [true false]}

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {6 [true false]}
2   |  {0 [false false]}
3   |  {0 [false false]}
4   |  {2 [true false]}
5   |  {0 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {5 [true false]}
9   |  {0 [false false]}
10  |  {0 [false false]}
11  |  {1 [true true]}
12  |  {8 [false true]}
13  |  {3 [false false]}
14  |  {4 [true false]}
15  |  {0 [false false]}
16  |  {0 [false false]}
17  |  {0 [false false]}
18  |  {0 [false false]}
19  |  {7 [true false]}

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {6 [true false]}
2   |  {0 [false false]}
3   |  {0 [false false]}
4   |  {2 [true false]}
5   |  {0 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {5 [true false]}
9   |  {0 [false false]}
10  |  {0 [false false]}
11  |  {1 [true true]}
12  |  {8 [false true]}
13  |  {3 [false false]}
14  |  {4 [true true]}
15  |  {9 [false false]}
16  |  {0 [false false]}
17  |  {0 [false false]}
18  |  {0 [false false]}
19  |  {7 [true false]}

-----------------------------
No.     | bucket
-----------------------------
0   |  {0 [false false]}
1   |  {6 [true false]}
2   |  {0 [false false]}
3   |  {0 [false false]}
4   |  {2 [true false]}
5   |  {0 [false false]}
6   |  {0 [false false]}
7   |  {0 [false false]}
8   |  {5 [true false]}
9   |  {0 [false false]}
10  |  {0 [false false]}
11  |  {1 [true true]}
12  |  {8 [false true]}
13  |  {3 [false false]}
14  |  {4 [true true]}
15  |  {9 [false true]}
16  |  {10 [false false]}
17  |  {0 [false false]}
18  |  {0 [false false]}
19  |  {7 [true false]}

itemとして8を挿入しようとしたときにテーブルの作り直しが起こっています。

感想

Insertの実装が思いの外、苦戦しました。添字のミスがないように一つ一つ確かめながら実装したので身には付いたかなと思います。 テーブルの作り直しもバグが入りがちで、ループになったり、挿入がされていなかったりで理解してから実装までが大変でした。

References

Golangでパーセントエンコーディングをデコードする

前回の記事でGo言語でパーセントエンコーディングを行ったので、今回はデコード編です。 とはいえ、標準でデコードするQueryUnescape()関数が用意されているので、そちらを使うのみです。 前回のように半角スペースの置換を気にする必要はありません。 ドキュメントにも以下のように記載されています。

func QueryUnescape

converting %AB into the byte 0xAB and ‘+’ into ‘ ’ (space).

実装は以下です。

package main

import (
    "fmt"
    "net/url"
    "regexp"
)

func main() {
    str := "パーセント エンコーディング"

    // encode
    str = url.QueryEscape(str)
    str = regexp.MustCompile(`([^%])(\+)`).ReplaceAllString(str, "$1%20")

    // decode
    str, _ = url.QueryUnescape(str)

    fmt.Println(str)
    // パーセント エンコーディング
}

References

Golangでパーセントエンコーディング

Goには標準のurlパッケージにQueryEscape()関数が用意されているので、これを利用してパーセントエンコーディングができます。 しかし、単純にQueryEscape()を使うと、以下のように半角スペースが+と表示されてしまいます。

package main

import (
    "fmt"
    "net/url"
)

func main() {
    str := "パーセント エンコーディング"

    str = url.QueryEscape(str)

    fmt.Println(str)
    // %E3%83%91%E3%83%BC%E3%82%BB%E3%83%B3%E3%83%88+%E3%82%A8%E3%83%B3%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0

}

ASCIIコード表を見ると半角スペースには0x20が割り当てられているので、これを置換してあげればOKです。

package main

import (
    "fmt"
    "net/url"
    "regexp"
)

func main() {
    str := "パーセント エンコーディング"

    str = url.QueryEscape(str)
    str = regexp.MustCompile(`([^%])(\+)`).ReplaceAllString(str, "$1%20")

    fmt.Println(str)
    // %E3%83%91%E3%83%BC%E3%82%BB%E3%83%B3%E3%83%88%20%E3%82%A8%E3%83%B3%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0

}

References

パケットキャプチャを可視化する

パケットキャプチャを取得することは多いもののWiresharkでの解析ばかりなので、 Goで可視化してみることにしました。

実装

入力としてfile.pcapを受け取り、gopacketでキャプチャデータを解析しています。 可視化はGraphvizを用いました。

gistf0b03462dc06db3ce515c677b10b0d14

上記を実行するとdigraph.dotとしてDOTファイルが出力されるので、 これをGraphvizに渡せば完了です。

dot -T png ./digraph.dot -o ./digraph.png

結果

結果として2パターンをほど試してみました。 ホストPCの環境だと、絶えずいろいろな通信が発生しており、可視化するのが楽しいのです。しかし、アドレス逆引きされるとどのサービスを使っているのか一発でわかってしまうので例示は避けました

こちらはテスト用に適当なドメインpingしています。自ホストが10.0.2.15です。

f:id:cipepser:20170717232516p:plain

次の例では、ネットワーク初心者の新卒がDockerでネットワークの勉強をしてみたを参考に、検証環境を用意してみました。 OSPFの224.0.0.5があるので、動的に経路情報を渡している様子が見えますね。

f:id:cipepser:20170717232529p:plain

感想

自分で使ってみて思ったのは、変な通信がないか確認できるのがよいなということでした。同セグメントをグループ化するなどするともっと良さそうです。 フィルタやL4以上の情報(逆にL2も)も可視化できそうなので、これをもとにツール化したいところですが、future workということで。

References

Golangでローソク足チャートを描くパッケージを書いた

Golangでグラフを描くときには gonum plot が便利です。 これを使った例として、以前、棒グラフの記事も書きました。 その他の例としては、公式のwikiGo でグラフを plot するパッケージを試したが参考になります。
gonumのレポジトリを見ると 棒グラフや箱ひげ図、折れ線グラフなどが標準で実装されています。 (他にも関数などおもしろそうなものもあります)
ところがローソク足チャートは標準で実装されていないようです。 レポジトリのWikiを見ているとオリジナルのPoltterをカスタマイズするチュートリアルがあったので、 今回はローソク足チャートを実装してみました。

実装

実装はこちら。 gonumのPlotter定義にあるように Plot(draw.Canvas, *plot.Plot)を実装してあげる必要があります。
Plot(draw.Canvas, *plot.Plot)を実装した独自の型を、plot.New()で生成した*Plot型の変数に、Add()してあげれば、グラフが描けます。
今回はこのように実装しました。 流れは大まかに以下です。

  1. canvas(出力先画面)のサイズに応じた座標変換をplot.Transforms()で行う。
  2. ローソクの幅を決める
  3. データの最安値、最高値、始値終値をもとに箱とヒゲを描画する。

陽線と陰線は、始値終値から計算できるので、Plot()ではなく、 コンストラクタに委任し、各ローソクにColorフィールドとして持たせることにしました。
それ以外にも軸の表示とか、データをどうやってもたせるのがいいのかとか 実装する箇所は意外と細かく広範囲に渡るので詳しくは実装をご参照ください。

使い方

インストー

go get github.com/cipepser/plot

描画

実行例は以下です。 描画したいデータはdataに格納してください。

gist31d1820b58d1a4c7cf8d9d2e0013e515

結果

グラフは実行したディレクトリにimg.pngとして出力されます。

f:id:cipepser:20170709160604p:plain

References

Golangで長いステートメントを次の行へ継続する

文字列の結合をしていると以下のように長くなることがあります。 改行したくなります。

str := stmt1 + stmt2 + stmt3 + stmt4 + stmt5 + stmt6 + stmt7 + stmt8 + stmt9 + stmt10

少しググった限りだと文字列に改行が含まれ複数行になる場合の記事ばかりが見つかったので、備忘録として残しておきます。 複数行に渡る記述は以下のようにすればOKです。

str := stmt1 +
       stmt2 +
       stmt3 +
       stmt4 +
       stmt5 +
       stmt6 +
       stmt7 +
       stmt8 +
       stmt9 +
       stmt10

+を行頭にもってくるとコンパイルエラーになるので注意です。

Reference