Golangで棒グラフを描く
背景
言語処理100本ノック 2015をやっている最中に、棒グラフで表示する問題(Q37)に遭遇しました。簡単に検索したところ、意外と日本語記事が少なかったので、Gonum Plotを色々触ってみたメモを残しておきます。
packageのインストール
Gonum Plotにもありますが、go getしておきます。
# go get github.com/gonum/plot/...
何もエラーが出ず、プロンプトが表示されれば問題ありません。
ここでhgが足りないエラーがでる場合は、mercurialをインストールしましょう。
# brew install mercurial
棒グラフの作成
各設定事項はコメントで記載しました。 その他にももろもろ設定できますので、Gonum Plotをご覧ください。
gist9515002d792508b91e54766930751e37
棒グラフの出力
上記を実行すると、グラフがディレクトリに.pngで出力されます。
Reference
Golangで言語処理100本ノック2015 第3章: 正規表現
言語処理100本ノック 2015の第3章: 正規表現の10問です。
20. JSONデータの読み込み
Wikipedia記事のJSONファイルを読み込み，「イギリス」に関する記事本文を表示せよ．問題21-29では，ここで抽出した記事本文に対して実行せよ．
gist1c2eef5c84cb1bb2f2ffc568d5d60d31
Goでjsonを触ったことがなかったので勉強がてら。 結果の表示は長すぎるので割愛します。
21. カテゴリ名を含む行を抽出
記事中でカテゴリ名を宣言している行を抽出せよ．
gistd85ddaaaeedb8accc0431d2ea8458fb5
Q20で抜き出した結果をtxtに格納しています。
本問題は実質、L45-48のみです。
# go run q21.go [[Category:イギリス|*]] [[Category:英連邦王国|*]] [[Category:G8加盟国]] [[Category:欧州連合加盟国]] [[Category:海洋国家]] [[Category:君主国]] [[Category:島国|くれいとふりてん]] [[Category:1801年に設立された州・地域]]
22. カテゴリ名の抽出
記事のカテゴリ名を（行単位ではなく名前で）抽出せよ．
gistd36f7ebc49991afa58cb42101c9265b5
# go run q22.go イギリス|* 英連邦王国|* G8加盟国 欧州連合加盟国 海洋国家 君主国 島国|くれいとふりてん 1801年に設立された州・地域
正規表現のところをCategory:.*]としました。
あとは表示する箇所を*のところだけにしています。
23. セクション構造
記事中に含まれるセクション名とそのレベル（例えば"== セクション名 ==“なら1）を表示せよ．
gist4db740893310296693544caa501a9727
# go run q23.go 国名 1 歴史 1 地理 1 気候 2 政治 1 外交と軍事 1 地方行政区分 1 主要都市 2 科学技術 1 経済 1 鉱業 2 農業 2 貿易 2 通貨 2 企業 2 交通 1 道路 2 鉄道 2 海運 2 航空 2 通信 1 国民 1 言語 2 宗教 2 婚姻 2 教育 2 文化 1 食文化 2 文学 2 哲学 2 音楽 2 イギリスのポピュラー音楽 3 映画 2 コメディ 2 国花 2 世界遺産 2 祝祭日 2 スポーツ 1 サッカー 2 競馬 2 モータースポーツ 2 脚注 1 関連項目 1 外部リンク 1
(?m)がないと^が否定として認識されるところでハマりました。。。
24. ファイル参照の抽出
記事から参照されているメディアファイルをすべて抜き出せ．
gist6feafca211c2f0c574b60770553f1a71
# go run q24.go Royal Coat of Arms of the United Kingdom.svg Battle of Waterloo 1815.PNG The British Empire.png Uk topo en.jpg BenNevis2005.jpg Elizabeth II greets NASA GSFC employees, May 8, 2007 edit.jpg Palace of Westminster, London - Feb 2007.jpg David Cameron and Barack Obama at the G20 Summit in Toronto.jpg Soldiers Trooping the Colour, 16th June 2007.jpg Scotland Parliament Holyrood.jpg London.bankofengland.arp.jpg City of London skyline from London City Hall - Oct 2008.jpg Oil platform in the North SeaPros.jpg Eurostar at St Pancras Jan 2008.jpg Heathrow T5.jpg Anglospeak.svg CHANDOS3.jpg The Fabs.JPG PalaceOfWestminsterAtNight.jpg Westminster Abbey - West Door.jpg Edinburgh Cockburn St dsc06789.jpg Canterbury Cathedral - Portal Nave Cross-spire.jpeg Kew Gardens Palm House, London - July 2009.jpg 2005-06-27 - United Kingdom - England - London - Greenwich.jpg Stonehenge2007 07 30.jpg Yard2.jpg Durham Kathedrale Nahaufnahme.jpg Roman Baths in Bath Spa, England - July 2006.jpg Fountains Abbey view02 2005-08-27.jpg Blenheim Palace IMG 3673.JPG Liverpool Pier Head by night.jpg Hadrian's Wall view near Greenhead.jpg London Tower (1).JPG Wembley Stadium, illuminated.jpg
.*でマッチさせようとすると最後の|まで引っかかってしまうので.*?としています。
Fileとファイルでわかれてるがめんどくさかったですね。。。
25. テンプレートの抽出
記事中に含まれる「基礎情報」テンプレートのフィールド名と値を抽出し，辞書オブジェクトとして格納せよ．
gistb73da44413a4ccb5c9e32bd95a7ae4a4
# go run q25.go
イギリス
------------------
{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}（[[スコットランド・ゲール語]]）<br/>
*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}（[[ウェールズ語]]）<br/>
*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}（[[アイルランド語]]）<br/>
*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}（[[コーンウォール語]]）<br/>
*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}（[[スコットランド語]]）<br/>
**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}（アルスター・スコットランド語）</ref>
------------------
現在の国号「'''グレートブリテン及び北アイルランド連合王国'''」に変更
最初に基本情報を抜き出し、そこから|で区切られるテンプレートを抽出しました。
公式国名があるせいで、改行区切りではないので、\s\Sを用いて改行を含む抽出をしつつ、|を区切りとしています。
ただし単純に\n|を終端として持ってくると偶数回目が抜き出せなくなるので、\n|をダブらせるように前処理を入れています。
同様に最後の注記も抜き出せなくなるので終端処理を入れています。
課題では辞書オブジェクト(Map)に格納するところまでですが、テストとして略名と、ハマりどころの公式国名、偶数番目、最後のテンプレートもちゃんと取れているかの確認用に確立形態4、注記を表示させてみました。
26. 強調マークアップの除去
25の処理時に，テンプレートの値からMediaWikiの強調マークアップ（弱い強調，強調，強い強調のすべて）を除去してテキストに変換せよ（参考: マークアップ早見表）．
gist8fb6214399e84001eecfcd72acddd3c1
# go run q26.go 現在の国号「グレートブリテン及び北アイルランド連合王国」に変更
Q25を元に、ReplaceAllStringで'{2,5}をマッチさせています。
確認用には確立形態4を表示。
27. 内部リンクの除去
26の処理に加えて，テンプレートの値からMediaWikiの内部リンクマークアップを除去し，テキストに変換せよ（参考: マークアップ早見表）．
gist0531301d5d7252c813b3f8bc12bd074d
# go run q27.go
1801年
244,820
1兆5478億<ref name="imf-statistics-gdp">[http://www.imf.org/external/pubs/ft/weo/2012/02/weodata/weorept.aspx?pr.x=70&pr.y=13&sy=2010&ey=2012&scsm=1&ssd=1&sort=country&ds=.&br=1&c=112&s=NGDP%2CNGDPD%2CPPPGDP%2CPPPPC&grp=0&a= IMF>Data and Statistics>World Economic Outlook Databases>By Countrise>United Kingdom]</ref>
2兆3162億<ref name="imf-statistics-gdp" />
イングランド王国／スコットランド王国<br />（両国とも連合法 (1707年)まで）
グレートブリテン及びアイルランド連合王国建国<br />（連合法 (1800年)）
女王陛下万歳
ロンドン
246
1.3%
2兆4337億<ref name="imf-statistics-gdp" />
±0
.uk / .gb<ref>使用は.ukに比べ圧倒的少数。</ref>
44
（イギリスの国章）
{{lang|fr|Dieu et mon droit}}<br/>（フランス語:神と私の権利）
6
建国
1927年
{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}（スコットランド・ゲール語）<br/>
*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}（ウェールズ語）<br/>
*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}（アイルランド語）<br/>
*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}（コーンウォール語）<br/>
*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}（スコットランド語）<br/>
**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}（アルスター・スコットランド語）</ref>
ロンドン
デーヴィッド・キャメロン
927年／843年
GB / GBR
1707年
Flag of the United Kingdom.svg
22
63,181,775<ref>[http://esa.un.org/unpd/wpp/Excel-Data/population.htm United Nations Department of Economic and Social Affairs>Population Division>Data>Population>Total Population]</ref>
2012
グレートブリテン王国建国<br />（連合法 (1707年)）
2011
1 E7
36,727<ref name="imf-statistics-gdp" />
ファイル:Royal Coat of Arms of the United Kingdom.svg|85px
Location_UK_EU_Europe_001.svg
イギリスの君主
76
1 E11
+1
<references />
2012
5
2012
イギリス
グレートブリテン及び北アイルランド連合王国
英語（事実上）
エリザベス2世
イギリスの首相
現在の国号「グレートブリテン及び北アイルランド連合王国」に変更
スターリング・ポンド (£)
GBP
ルールは単純なのですが、意外と時間かかりました。
グループ文字列の概念をここで知ったのでFindAllStringSubmatch()も使ってみました。
28. MediaWikiマークアップの除去
27の処理に加えて，テンプレートの値からMediaWikiマークアップを可能な限り除去し，国の基本情報を整形せよ．
gistb0ae0915872317ffa62cedb2c505d854
# go run q28.go
1 E7
1兆5478億<ref name="imf-statistics-gdp">
スターリング・ポンド (£)
GBP
1.3%
244,820
2兆3162億<ref name="imf-statistics-gdp" />
36,727<ref name="imf-statistics-gdp" />
ロンドン
2011
63,181,775<ref>
グレートブリテン及びアイルランド連合王国建国<br />（連合法 (1800年)）
1927年
<references />
イギリスの君主
Flag of the United Kingdom.svg
（イギリスの国章）
エリザベス2世
{{lang|en|United Kingdom of Great Britain and Northern Ireland}}<ref>英語以外での正式国名:<br/>
*{{lang|gd|An Rìoghachd Aonaichte na Breatainn Mhòr agus Eirinn mu Thuath}}（スコットランド・ゲール語）<br/>
*{{lang|cy|Teyrnas Gyfunol Prydain Fawr a Gogledd Iwerddon}}（ウェールズ語）<br/>
*{{lang|ga|Ríocht Aontaithe na Breataine Móire agus Tuaisceart na hÉireann}}（アイルランド語）<br/>
*{{lang|kw|An Rywvaneth Unys a Vreten Veur hag Iwerdhon Glédh}}（コーンウォール語）<br/>
*{{lang|sco|Unitit Kinrick o Great Breetain an Northren Ireland}}（スコットランド語）<br/>
**{{lang|sco|Claught Kängrick o Docht Brätain an Norlin Airlann}}、{{lang|sco|Unitet Kängdom o Great Brittain an Norlin Airlann}}（アルスター・スコットランド語）</ref>
1801年
+1
246
Location_UK_EU_Europe_001.svg
英語（事実上）
ロンドン
5
2012
1707年
現在の国号「グレートブリテン及び北アイルランド連合王国」に変更
グレートブリテン及び北アイルランド連合王国
GB / GBR
±0
イギリスの首相
76
1 E11
2012
2兆4337億<ref name="imf-statistics-gdp" />
建国
イングランド王国／スコットランド王国<br />（両国とも連合法 (1707年)まで）
{{lang|fr|Dieu et mon droit}}<br/>（フランス語:神と私の権利）
グレートブリテン王国建国<br />（連合法 (1707年)）
.uk / .gb<ref>使用は.ukに比べ圧倒的少数。</ref>
44
927年／843年
ファイル:Royal Coat of Arms of the United Kingdom.svg|85px
女王陛下万歳
デーヴィッド・キャメロン
22
2012
6
イギリス
外部リンクとコメントアウトを消しました。
29. 国旗画像のURLを取得する
テンプレートの内容を利用し，国旗画像のURLを取得せよ．（ヒント: MediaWiki APIのimageinfoを呼び出して，ファイル参照をURLに変換すればよい）
gist84f53bc3fb6df3029aff323f42cb6c5d
# go run q29.go https://upload.wikimedia.org/wikipedia/en/a/ae/Flag_of_the_United_Kingdom.svg
API client書いたことがなかったので書いてみましたが、もっとちゃんと書けそうな気がしています。どういうことに気をつけて書くべきなのかも経験不足なので、今後の課題ですね。
感想
序盤はさくさく進んだので余裕かと思いましたが、後半でかなり手こずりしました。正規表現むずい。
今回もコードはGithubにも置いてあります。
Reference
tracerouteで * (アスタリスク)になる理由
背景
「ネットワークがつながらない！」といったトラブルシューティングをしていると、
tracerouteの結果が、以下のように経路の途中で*になる事象によく遭遇します。
今回はIPヘッダやパケットを見比べながら、なぜ*になるのかを見ていきます。
$ traceroute 8.8.8.8
traceroute to 8.8.8.8 (8.8.8.8), 64 hops max, 52 byte packets
1 192.168.43.1 (192.168.43.1) 823.037 ms * 3.936 ms
2 * * *
3 osk004bb01.iij.net (202.32.116.5) 476.654 ms 132.676 ms 120.725 ms
4 osk004ix50.iij.net (58.138.107.218) 119.609 ms
osk004ix50.iij.net (58.138.107.166) 133.204 ms
osk004ix51.iij.net (58.138.107.222) 117.566 ms
5 72.14.210.182 (72.14.210.182) 126.614 ms
210.130.133.86 (210.130.133.86) 115.229 ms 118.843 ms
6 108.170.243.36 (108.170.243.36) 119.670 ms
108.170.243.68 (108.170.243.68) 134.219 ms
108.170.243.132 (108.170.243.132) 135.462 ms
7 209.85.255.163 (209.85.255.163) 141.621 ms
216.239.41.199 (216.239.41.199) 132.251 ms 138.545 ms
8 66.249.95.77 (66.249.95.77) 165.501 ms
108.170.235.231 (108.170.235.231) 155.299 ms
66.249.95.77 (66.249.95.77) 172.740 ms
9 216.239.43.101 (216.239.43.101) 153.654 ms
72.14.235.77 (72.14.235.77) 175.888 ms
64.233.175.209 (64.233.175.209) 156.037 ms
10 * * *
11 * * *
12 * * *
13 * * *
14 * * *
15 * * *
16 * * *
17 * * *
18 google-public-dns-a.google.com (8.8.8.8) 159.839 ms 156.416 ms 166.939 ms
※プロバイダによっては*にならない場合もあるようです。
今回はDMMのSIMカードからテザリングしています。
ちなみに8.8.8.8はGoogleのパブリックDNSのIPアドレスです。覚えやすいですね。
前提知識
IPヘッダのProtocolナンバー
RFC791でIPヘッダのフォーマットは以下のように定められています。
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| IHL |Type of Service| Total Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Identification |Flags| Fragment Offset | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Time to Live | Protocol | Header Checksum | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Options | Padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
上記のProtocolフィールドが1となるものがICMPとなります。
※ProtocolナンバーはRFC790
で規定されています。
TCP、UDP(User Datagram)もそれぞれ6、17がアサインされています。
ping実行時のパケットをWiresharkで見てみると以下のようにICMP(1)となっていることがわかります。
tracerouteの仕組み
tracerouteは、冒頭のコマンド結果のように、宛先までのホップ情報を教えてくれる便利なコマンドです。
tracerouteは上記のIPヘッダにあるTime to Live(TTL)を利用して実装されています。
TTLはパケットの寿命みたいなものです。誤ったルーティングが設定されたネットワークでは、度々ループが発生します。この時、ネットワークに入ってきたパケットがいつまでもループし続けると、ネットワークの帯域を逼迫させ、通信ができなくなります。それを避けるための方法として、ルータはパケットをフォワードする際にTTLを1ずつデクリメントします。TTLが0になったパケットを受信したルータは、そのパケットをフォワードせず、破棄します。これによってネットワークが輻輳まみれになることを防ぎます。
そしてTTLが0になったときtracerouteの発行元に対して、TTLが0になったことを通知(Time Exceeded Message)します。
※これらはRFC792で以下のように規定されています。
If the gateway processing a datagram finds the time to live field is zero it must discard the datagram. The gateway may also notify the source host via the time exceeded message.
この通知には破棄したルータのIPアドレスが含まれています。
tracerouteではTTLを1つずつインクリメントし、応答があったTime Exceeded Messageに含まれるIPアドレスを表示することで実装されています。
本題
前置きが長くなりましたが、いよいよ本題に入っていきます。
tracerouteは、WindowsではICMPを用いていますが、LinuxではUDPでポート番号33434 〜33534が使われます。tracerouteをFWで通す要件がある場合は、実装する際に注意が必要です。
今回はICMPのTTLをマニュアルで設定することで、tracerouteの仕組みを擬似的に再現し、*の正体を探ります。
そのためtracerouteに-Iオプションを付けてICMPでのtraceroute結果を得ておきます。
$ traceroute -I 8.8.8.8 traceroute to 8.8.8.8 (8.8.8.8), 64 hops max, 72 byte packets 1 * * * 2 * * * 3 osk009nasgw111.iij.net (202.32.116.105) 132.515 ms 122.689 ms 119.731 ms 4 osk004bb01.iij.net (202.32.116.5) 117.981 ms 114.951 ms 121.114 ms 5 osk004ix51.iij.net (58.138.107.222) 123.171 ms 118.085 ms 122.172 ms 6 72.14.210.182 (72.14.210.182) 117.047 ms 122.246 ms 123.139 ms 7 108.170.243.66 (108.170.243.66) 117.916 ms 498.344 ms 149.948 ms 8 209.85.255.163 (209.85.255.163) 116.059 ms 132.291 ms 121.649 ms 9 72.14.233.211 (72.14.233.211) 159.789 ms 163.511 ms 173.399 ms 10 72.14.235.77 (72.14.235.77) 154.462 ms 153.933 ms 170.539 ms 11 * * * 12 * * * 13 * * * 14 * * * 15 * * * 16 * * * 17 * * * 18 * * * 19 google-public-dns-a.google.com (8.8.8.8) 168.872 ms 150.776 ms 161.775 ms
この時の通信の様子をWiresharkで見てみると以下のようになります。 TTLを1から順に増やしつつ、それぞれ3回送っていることがわかります。
勘の良い方はすでにお気づきかと思いますが、
tracerouteの結果が*ではないものはTime Exceeded Messageを返しています。
逆に言えば、*になっている箇所は応答がありません。
さらに詳しく見るためにTTLを設定したpingを打ってみましょう。
-mオプションでpingのTTLを設定できます。
長いですが、以下結果です。
192.168.43.11は自ホストのアドレスです。
$ ping -m 1 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 2 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 3 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes 36 bytes from osk009nasgw111.iij.net (202.32.116.105): Time to live exceeded Vr HL TOS Len ID Flg off TTL Pro cks Src Dst 4 5 00 5400 248e 0 0000 01 01 9958 192.168.43.11 8.8.8.8 --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 4 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes 76 bytes from osk004bb01.iij.net (202.32.116.5): Time to live exceeded Vr HL TOS Len ID Flg off TTL Pro cks Src Dst 4 5 00 5400 80d2 0 0000 01 01 3d14 192.168.43.11 8.8.8.8 --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 5 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes 36 bytes from osk004ix51.iij.net (58.138.107.222): Time to live exceeded Vr HL TOS Len ID Flg off TTL Pro cks Src Dst 4 5 00 5400 1fb3 0 0000 01 01 9e33 192.168.43.11 8.8.8.8 --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 6 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes 36 bytes from 72.14.210.182: Time to live exceeded Vr HL TOS Len ID Flg off TTL Pro cks Src Dst 4 5 00 5400 3fb3 0 0000 01 01 7e33 192.168.43.11 8.8.8.8 --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 7 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes 36 bytes from 108.170.243.66: Time to live exceeded Vr HL TOS Len ID Flg off TTL Pro cks Src Dst 4 5 80 5400 acc6 0 0000 01 01 10a0 192.168.43.11 8.8.8.8 --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 8 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes 148 bytes from 209.85.255.163: Time to live exceeded Vr HL TOS Len ID Flg off TTL Pro cks Src Dst 4 5 80 5400 5d6e 0 0000 01 01 5ff8 192.168.43.11 8.8.8.8 --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 9 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes 148 bytes from 72.14.233.211: Time to live exceeded Vr HL TOS Len ID Flg off TTL Pro cks Src Dst 4 5 80 5400 13e9 0 0000 02 01 a87d 192.168.43.11 8.8.8.8 --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 10 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes 36 bytes from 72.14.235.77: Time to live exceeded Vr HL TOS Len ID Flg off TTL Pro cks Src Dst 4 5 80 5400 6b01 0 0000 01 01 5265 192.168.43.11 8.8.8.8 --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 11 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 12 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 13 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 14 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 15 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 16 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 17 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 18 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes --- 8.8.8.8 ping statistics --- 1 packets transmitted, 0 packets received, 100.0% packet loss
$ ping -m 19 -c 1 8.8.8.8 PING 8.8.8.8 (8.8.8.8): 56 data bytes 64 bytes from 8.8.8.8: icmp_seq=0 ttl=46 time=166.696 ms --- 8.8.8.8 ping statistics --- 1 packets transmitted, 1 packets received, 0.0% packet loss round-trip min/avg/max/stddev = 166.696/166.696/166.696/0.000 ms
確かにtracerouteの結果が*ではないものはTime Exceeded Messageを返していることがわかります。
しかもその応答をTTL=0となったホップが返しているので、送信元アドレス(=tracerouteで表示するアドレス)もわかりました。
逆に*になっている箇所はpacket lossで応答なしのため、表示することができず、代替手段として*を表示するしかないようですね。
またTTL=19の最終の宛先では、通常のping応答と同様のメッセージが返ってきているので、これを自分でtracerouteを実装するとしたら、「応答があったこと」を条件にループ止めるなどで実装できそうですね。
結論
tracerouteの結果、経路の途中で*になるのは、そのホップが応答を返さないとき（フォワードのみする）。
Reference
dockerで<none>になったimageを一発で削除するシェル芸
タイトルのままですが、docker imagesを見たときにTAGが<none>となってしまったdocker imageをまとめて削除するためのシェル芸です。
シェルも書けるようになりたいなという思いから、練習がてら。
docker images | grep none | sed -E 's/ +/ /g' | cut -f 3 -d ' ' | xargs docker rmi -f
Reference
Golangでcounting BloomFilterを実装してみた
先日実装したBloomFilter に要素の削除ができるようにcounting BloomFilterを実装しました。
概要
単純なBloomFilter
では要素を削除することはできません。
BloomFilterへのマッピングが、削除したい特定の要素によるものか、はたまた別の要素によるものか区別することができないためです。
counting BloomFilterでは、BloomFilterにDelete()ができるようにマッピングをbooleanからcountingができるようmulti-bit化しています。
当然、その分空間効率性が犠牲になります。Fanらのpaper
のイントロによると、一般的には3-4[bit]で実装するそうなので、3-4倍空間効率が悪くなります。
今回はGolangのprimitive型であるuint8を使用したため、アイデア自体は変わらないですが、一般的なcounting BloomFilterよりも空間効率が劣ります。
実装と結果
gistb38c96069b177b4f64ede336c658b976
要素"2"の削除前後で結果がtrue→falseと変わっていることがわかります。
参考
Golangの関数リテラルについてメモ書き
A Tour of GoのFunction valuesを読んでいて、色々勘違いしていてわからなくなってしまったので、手を動かしてわかるようになるまでのメモ書きです。
要旨
勘違いしていたのはA Tour of Goの以下の記載についてです。
関数も変数です。他の変数のように関数を渡すことができます。
どうしても関数を変数に渡した際に「戻り値を渡している」と考えていまい、例題が理解できませんでした。
理解に至った考え方は 「関数そのものを変数に渡している」 です。
例: A Tour of GoのFunction values
ここでは関数computeが定義されています。
func compute(fn func(float64, float64) float64) float64 {
return fn(3, 4)
}
これは
引数: (float64, float64)を引数に、float64を返す関数
戻り値: float64
となる関数です。
つまり関数そのものを引数として、変数のように渡すことができます。
A Tour of Goでは「(float64, float64)を引数に、float64を返す関数」であるhypotを定義するとともに、同じ関数型の関数math.Powを引数としてcomputeに渡してあげる例となっています。
fmt.Println(compute(hypot)) fmt.Println(compute(math.Pow))
Reference
Golangで言語処理100本ノック2015 第2章: UNIXコマンドの基礎
言語処理100本ノック 2015の第2章: UNIXコマンドの基礎の10問です。
10. 行数のカウント
行数をカウントせよ．確認にはwcコマンドを用いよ．
gista7b27f35e5b111f979022b367ef696c4
# wc hightemp.txt 24 48 813 hightemp.txt
ReadLine()で一行ずつ読み込み、読み終わった時点の行数を出力させました。
11. タブをスペースに置換
タブ1文字につきスペース1文字に置換せよ．確認にはsedコマンド，trコマンド，もしくはexpandコマンドを用いよ．
gist848871be78390be2901e02908051ccc7
# sed 's/\t/ /g' ../data/hightemp.txt 高知県 江川崎 41 2013-08-12 埼玉県 熊谷 40.9 2007-08-16 岐阜県 多治見 40.9 2007-08-16 山形県 山形 40.8 1933-07-25 山梨県 甲府 40.7 2013-08-10 和歌山県 かつらぎ 40.6 1994-08-08 静岡県 天竜 40.6 1994-08-04 山梨県 勝沼 40.5 2013-08-10 埼玉県 越谷 40.4 2007-08-16 群馬県 館林 40.3 2007-08-16 群馬県 上里見 40.3 1998-07-04 愛知県 愛西 40.3 1994-08-05 千葉県 牛久 40.2 2004-07-20 静岡県 佐久間 40.2 2001-07-24 愛媛県 宇和島 40.2 1927-07-22 山形県 酒田 40.1 1978-08-03 岐阜県 美濃 40 2007-08-16 群馬県 前橋 40 2001-07-24 千葉県 茂原 39.9 2013-08-11 埼玉県 鳩山 39.9 1997-07-05 大阪府 豊中 39.9 1994-08-08 山梨県 大月 39.9 1990-07-19 山形県 鶴岡 39.9 1978-08-03 愛知県 名古屋 39.9 1942-08-02
strings.Replace()を使ってもいいかと思いましたが、rune単位で一文字ずつ読み込み、tabだったら変換する方式としました。
ファイル終端の判別は、io.EOFはerror型でruneと比較できないので、NULL文字で判断しています。
12. 1列目をcol1.txtに，2列目をcol2.txtに保存
各行の1列目だけを抜き出したものをcol1.txtに，2列目だけを抜き出したものをcol2.txtとしてファイルに保存せよ．確認にはcutコマンドを用いよ．
gist930b77e110065c0d74170d39dd9e1e85
// 題意に合わせるにはさらにリダイレクトして出力する必要がありますが、さらにcatするのも冗長なので標準出力にしました。 # cut -f 1 ../data/hightemp.txt 高知県 埼玉県 岐阜県 山形県 山梨県 和歌山県 静岡県 山梨県 埼玉県 群馬県 群馬県 愛知県 千葉県 静岡県 愛媛県 山形県 岐阜県 群馬県 千葉県 埼玉県 大阪府 山梨県 山形県 愛知県 # cut -f 2 ../data/hightemp.txt 江川崎 熊谷 多治見 山形 甲府 かつらぎ 天竜 勝沼 越谷 館林 上里見 愛西 牛久 佐久間 宇和島 酒田 美濃 前橋 茂原 鳩山 豊中 大月 鶴岡 名古屋
filepathパッケージで入力と同じディレクトリに出力するようにしました。
13. col1.txtとcol2.txtをマージ
12で作ったcol1.txtとcol2.txtを結合し，元のファイルの1列目と2列目をタブ区切りで並べたテキストファイルを作成せよ．確認にはpasteコマンドを用いよ．
gista6f97b6d6ad9b9e4808fae91095e1d20
# paste ../data/col1.txt ../data/col2.txt 高知県 江川崎 埼玉県 熊谷 岐阜県 多治見 山形県 山形 山梨県 甲府 和歌山県 かつらぎ 静岡県 天竜 山梨県 勝沼 埼玉県 越谷 群馬県 館林 群馬県 上里見 愛知県 愛西 千葉県 牛久 静岡県 佐久間 愛媛県 宇和島 山形県 酒田 岐阜県 美濃 群馬県 前橋 千葉県 茂原 埼玉県 鳩山 大阪府 豊中 山梨県 大月 山形県 鶴岡 愛知県 名古屋
入出力を標準入力から取ってくるところ、filepathを取ってくるところは本質ではないので、やめました。
練習としてはQ12でできたので。
またruneで処理するところもReadLine()などにしてわかりやすくしました。
14. 先頭からN行を出力
自然数Nをコマンドライン引数などの手段で受け取り，入力のうち先頭のN行だけを表示せよ．確認にはheadコマンドを用いよ．
gist25538f623bc1425da5da9507b34823a2
# head -n 10 ../data/hightemp.txt 高知県 江川崎 41 2013-08-12 埼玉県 熊谷 40.9 2007-08-16 岐阜県 多治見 40.9 2007-08-16 山形県 山形 40.8 1933-07-25 山梨県 甲府 40.7 2013-08-10 和歌山県 かつらぎ 40.6 1994-08-08 静岡県 天竜 40.6 1994-08-04 山梨県 勝沼 40.5 2013-08-10 埼玉県 越谷 40.4 2007-08-16 群馬県 館林 40.3 2007-08-16
読み込んだ行数をカウントして、標準入力で受け取った整数になるまでループ回すだけです。
15. 末尾のN行を出力
自然数Nをコマンドライン引数などの手段で受け取り，入力のうち末尾のN行だけを表示せよ．確認にはtailコマンドを用いよ．
gistc953b981cec15f23ef604cf03f473e38
# tail -n 10 ../data/hightemp.txt 愛媛県 宇和島 40.2 1927-07-22 山形県 酒田 40.1 1978-08-03 岐阜県 美濃 40 2007-08-16 群馬県 前橋 40 2001-07-24 千葉県 茂原 39.9 2013-08-11 埼玉県 鳩山 39.9 1997-07-05 大阪府 豊中 39.9 1994-08-08 山梨県 大月 39.9 1990-07-19 山形県 鶴岡 39.9 1978-08-03 愛知県 名古屋 39.9 1942-08-02
ファイルサイズだけを取得できるのであれば、逆から一文字ずつ読む実装のほうが巨大なファイルを読み込む場合にすぐ表示できてよさそうです。
今回は全部の行を読み込み、出力用outputに溜め込み、最後に標準出力させました。
mod演算させておき、output = append(output[i:], output[:i]...)することで順番通りに出力できるのがポイントです。
16. ファイルをN分割する
自然数Nをコマンドライン引数などの手段で受け取り，入力のファイルを行単位でN分割せよ．同様の処理をsplitコマンドで実現せよ．
gist82a113dbf0bcf2436fe80a44532c589d
# split -l 13 ../data/hightemp.txt # cat xaa 高知県 江川崎 41 2013-08-12 埼玉県 熊谷 40.9 2007-08-16 岐阜県 多治見 40.9 2007-08-16 山形県 山形 40.8 1933-07-25 山梨県 甲府 40.7 2013-08-10 和歌山県 かつらぎ 40.6 1994-08-08 静岡県 天竜 40.6 1994-08-04 山梨県 勝沼 40.5 2013-08-10 埼玉県 越谷 40.4 2007-08-16 群馬県 館林 40.3 2007-08-16 群馬県 上里見 40.3 1998-07-04 愛知県 愛西 40.3 1994-08-05 千葉県 牛久 40.2 2004-07-20 # cat xab 静岡県 佐久間 40.2 2001-07-24 愛媛県 宇和島 40.2 1927-07-22 山形県 酒田 40.1 1978-08-03 岐阜県 美濃 40 2007-08-16 群馬県 前橋 40 2001-07-24 千葉県 茂原 39.9 2013-08-11 埼玉県 鳩山 39.9 1997-07-05 大阪府 豊中 39.9 1994-08-08 山梨県 大月 39.9 1990-07-19 山形県 鶴岡 39.9 1978-08-03 愛知県 名古屋 39.9 1942-08-02
Q10を再利用しました。
書き込み用ファイルのポインタwfpを使いまわしたかったですが、if文の中で再定義しようとするとスコープから外れてしまってつらい感じでした。
N個のファイルを作成するものと勘違いしてやり直しがあったので時間が掛かりました。そのボツの供養
17. １列目の文字列の異なり
1列目の文字列の種類（異なる文字列の集合）を求めよ．確認にはsort, uniqコマンドを用いよ．
gistd7efd041ef928797af814d56bcef28ce
# cut -f 1 ../data/hightemp.txt | sort | uniq 千葉県 和歌山県 埼玉県 大阪府 山形県 山梨県 岐阜県 愛媛県 愛知県 群馬県 静岡県 高知県
必ずしもソートする必要はありませんが、sortパッケージのinterfaceを実装するのをやってみたかったので自作型runeSliceのsortを実装してみました。
18. 各行を3コラム目の数値の降順にソート
各行を3コラム目の数値の逆順で整列せよ（注意: 各行の内容は変更せずに並び替えよ）．確認にはsortコマンドを用いよ（この問題はコマンドで実行した時の結果と合わなくてもよい）．
gist89c20ddb3587c1407c5b1099ff7b1bad
# sort -nk3 ../data/hightemp.txt 千葉県 茂原 39.9 2013-08-11 埼玉県 鳩山 39.9 1997-07-05 大阪府 豊中 39.9 1994-08-08 山形県 鶴岡 39.9 1978-08-03 山梨県 大月 39.9 1990-07-19 愛知県 名古屋 39.9 1942-08-02 岐阜県 美濃 40 2007-08-16 群馬県 前橋 40 2001-07-24 山形県 酒田 40.1 1978-08-03 千葉県 牛久 40.2 2004-07-20 愛媛県 宇和島 40.2 1927-07-22 静岡県 佐久間 40.2 2001-07-24 愛知県 愛西 40.3 1994-08-05 群馬県 上里見 40.3 1998-07-04 群馬県 館林 40.3 2007-08-16 埼玉県 越谷 40.4 2007-08-16 山梨県 勝沼 40.5 2013-08-10 和歌山県 かつらぎ 40.6 1994-08-08 静岡県 天竜 40.6 1994-08-04 山梨県 甲府 40.7 2013-08-10 山形県 山形 40.8 1933-07-25 埼玉県 熊谷 40.9 2007-08-16 岐阜県 多治見 40.9 2007-08-16 高知県 江川崎 41 2013-08-12
3コラム目と指定されているので直書きでも良い気がしましたが、各コラムでソートできるようにしたかったので、Jxckさんの記事を参考にソート条件を可変にしました。
Go1.8ではsort.Sliceが実装されるのでByXXXを書かなくて良くなりそうです。
(ベンチマークを見る限り、速度は犠牲になっているようなので要件に合わせてチューニングが必要そうですが)
19. 各行の1コラム目の文字列の出現頻度を求め，出現頻度の高い順に並べる
各行の1列目の文字列の出現頻度を求め，その高い順に並べて表示せよ．確認にはcut, uniq, sortコマンドを用いよ．
gist4ea5282a6a739f8f3c7e8e0fc954fc91
# cut -f 1 ../data/hightemp.txt | sort | uniq -c | sort -r
3 群馬県
3 山梨県
3 山形県
3 埼玉県
2 静岡県
2 愛知県
2 岐阜県
2 千葉県
1 高知県
1 愛媛県
1 大阪府
1 和歌山県
ファイル内容を読み込んでから構造体に格納したものの、各フィールドを独自型にした結果、コードがひたすら長くなってしまったので微妙な気がします。メンテナンス性も低いのでベストプラクティス的なもの知る必要ありです。。。。
A Tour of GoのInterface valuesあたりを早く読めばよかった
感想
準備運動から久しく時間が空きましたが、第2章でした。
Go言語の筋トレのつもりでしたが、Linuxコマンドも知らないものが多く、勉強になりました。
今回のコードはGithubにも置いてあります。
