読者です 読者をやめる 読者になる 読者になる

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で出力されます。 f:id:cipepser:20170324010640p:plain

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世
イギリスの首相
現在の国号「グレートブリテン及び北アイルランド連合王国」に変更
スターリング・ポンド (&pound;)
GBP

ルールは単純なのですが、意外と時間かかりました。 グループ文字列の概念をここで知ったのでFindAllStringSubmatch()も使ってみました。

28. MediaWikiマークアップの除去

27の処理に加えて,テンプレートの値からMediaWikiマークアップを可能な限り除去し,国の基本情報を整形せよ.

gistb0ae0915872317ffa62cedb2c505d854

# go run q28.go
1 E7
1兆5478億<ref name="imf-statistics-gdp">
スターリング・ポンド (&pound;)
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 APIimageinfoを呼び出して,ファイル参照を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.8GoogleのパブリックDNSIPアドレスです。覚えやすいですね。

前提知識

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 で規定されています。 TCPUDP(User Datagram)もそれぞれ617がアサインされています。

ping実行時のパケットをWiresharkで見てみると以下のようにICMP(1)となっていることがわかります。

f:id:cipepser:20170305172120p:plain

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回送っていることがわかります。

f:id:cipepser:20170305211345p:plain f:id:cipepser:20170305211351p:plain f:id:cipepser:20170305211358p:plain

勘の良い方はすでにお気づきかと思いますが、 tracerouteの結果が*ではないものはTime Exceeded Messageを返しています。 逆に言えば、*になっている箇所は応答がありません。

さらに詳しく見るためにTTLを設定したpingを打ってみましょう。 -mオプションでpingTTLを設定できます。 長いですが、以下結果です。
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"の削除前後で結果がtruefalseと変わっていることがわかります。

参考

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列目の文字列の異なり

1列目の文字列の種類(異なる文字列の集合)を求めよ.確認にはsort, uniqコマンドを用いよ.

gistd7efd041ef928797af814d56bcef28ce

# cut -f 1 ../data/hightemp.txt | sort | uniq
千葉県
和歌山県
埼玉県
大阪府
山形県
山梨県
岐阜県
愛媛県
愛知県
群馬県
静岡県
高知県

必ずしもソートする必要はありませんが、sortパッケージのinterfaceを実装するのをやってみたかったので自作型runeSlicesortを実装してみました。

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にも置いてあります。

Reference