Golangで言語処理100本ノック2015 第9章: ベクトル空間法 (I)
言語処理100本ノック 2015の第9章: ベクトル空間法 (I)の10問です。
enwiki-20150112-400-r10-105752.txt.bz2は,2015年1月12日時点の英語のWikipedia記事のうち,約400語以上で構成される記事の中から,ランダムに1/10サンプリングした105,752記事のテキストをbzip2形式で圧縮したものである.このテキストをコーパスとして,単語の意味を表すベクトル(分散表現)を学習したい.第9章の前半では,コーパスから作成した単語文脈共起行列に主成分分析を適用し,単語ベクトルを学習する過程を,いくつかの処理に分けて実装する.第9章の後半では,学習で得られた単語ベクトル(300次元)を用い,単語の類似度計算やアナロジー(類推)を行う. なお,問題83を素直に実装すると,大量(約7GB)の主記憶が必要になる. メモリが不足する場合は,処理を工夫するか,1/100サンプリングのコーパスenwiki-20150112-400-r100-10576.txt.bz2を用いよ.
※コード中ではr100コーパスで実装している箇所もありますが、難関と評判のQ85でハマりr10コーパスにしています。
80. コーパスの整形
文を単語列に変換する最も単純な方法は,空白文字で単語に区切ることである. ただ,この方法では文末のピリオドや括弧などの記号が単語に含まれてしまう. そこで,コーパスの各行のテキストを空白文字でトークンのリストに分割した後,各トークンに以下の処理を施し,単語から記号を除去せよ.
以上の処理を適用した後,トークンをスペースで連結してファイルに保存せよ.
gist4ea9f91550e8b265f80751d8bd005e6b
❯ go run q80.go ❯ head -3 ../data/q80.out.txt Anarchism Anarchism is political philosophy that advocates stateless societies often defined as self-governed voluntary institutions but that several authors have defined as more specific institutions based on non-hierarchical free associations Anarchism holds the state to be undesirable unnecessary or harmful While anti-statism is central anarchism entails opposing authority or hierarchical organisation in the conduct of human relations including but not limited to the state system As subtle and anti-dogmatic philosophy anarchism draws on many currents of thought and strategy Anarchism does not offer fixed body of doctrine from single particular world view instead fluxing and flowing as philosophy There are many types and traditions of anarchism not all of which are mutually exclusive Anarchist schools of thought can differ fundamentally supporting anything from extreme individualism to complete collectivism Strains of anarchism have often been divided into the categories of social and individualist anarchism or similar dual classifications Anarchism is usually considered radical left-wing ideology and much of anarchist economics and anarchist legal philosophy reflect anti-authoritarian interpretations of communism collectivism syndicalism mutualism or participatory economics
トークンの先頭と末尾と書いてありますが、"-izein").
のようなトークンで不要な記号の除去ができないので、一つの記号を除去したあと再帰的にremoveSymbol()
を呼び出すことで、きちんと不要な記号を削除できるようにしました。
81. 複合語からなる国名への対処
英語では,複数の語の連接が意味を成すことがある.例えば,アメリカ合衆国は"United States",イギリスは"United Kingdom"と表現されるが,"United"や"States","Kingdom"という単語だけでは,指し示している概念・実体が曖昧である.そこで,コーパス中に含まれる複合語を認識し,複合語を1語として扱うことで,複合語の意味を推定したい.しかしながら,複合語を正確に認定するのは大変むずかしいので,ここでは複合語からなる国名を認定したい.
インターネット上から国名リストを各自で入手し,80のコーパス中に出現する複合語の国名に関して,スペースをアンダーバーに置換せよ.例えば,"United States"は"United_States","Isle of Man"は"Isle_of_Man"になるはずである.
gistcfab66b743e9507879fb63a272086782
❯ go run q81.go ❯ head -10 ../data/q81.out.txt | grep United The term anarchism isma compound word composed from the word anarchy and the suffix -ism themselves derived respectively from the Greek i.e anarchy from anarchos meaning one without rulers from the privative prefix ἀν- an- i.e without and archos i.e leader ruler cf archon or arkhē i.e authority sovereignty realm magistracy and the suffix or -ismos -isma from the verbal infinitive suffix -ίζειν -izein The first known use of this word was in 1539."Anarchist was the term adopted by Maximilien de Robespierre to attack those on the left whom he had used for his own ends during the French Revolution but was determined to get rid of though among these anarchists there were few who exhibited the social revolt characteristics of later anarchists There would be many revolutionaries of the early nineteenth century who contributed to the anarchist doctrines of the next generation such as William Godwin and Wilhelm Weitling but they did not use the word anarchist or anarchism in describing themselves or their beliefs Pierre-Joseph Proudhon was the first political philosopher to call himself an anarchist marking the formal birth of anarchism in the mid-nineteenth century Since the 1890s from France the term libertarianism has often been used as synonym for anarchism and was used almost exclusively in this sense until the 1950s in the United_States its use as synonym is still common outside the United_States On the other hand some use libertarianism to refer to individualistic free-market philosophy only referring to free-market anarchism as libertarian anarchism
List of countries of the world in alphabetical orderから国名リストを拝借しました。ただし、一語からなる国名の場合は、_
で繋げてあげる必要もないので複数語からなる国名のみをターゲットとしています。
82. 文脈の抽出
81で作成したコーパス中に出現するすべての単語tに関して,単語tと文脈語cのペアをタブ区切り形式ですべて書き出せ.ただし,文脈語の定義は次の通りとする.
- ある単語tの前後d単語を文脈語cとして抽出する(ただし,文脈語に単語tそのものは含まない)
- 単語tを選ぶ度に,文脈幅dは{1,2,3,4,5}の範囲でランダムに決める.
gist5d8c3571da29019ef73a187ab1f77edb
❯ go run q82.go ❯ head -20 ../data/q82.out.txt Anarchism Anarchism Anarchism is Anarchism political Anarchism philosophy Anarchism Anarchism Anarchism is Anarchism political Anarchism philosophy is Anarchism is Anarchism is political is philosophy is that is advocates is stateless political is political Anarchism political Anarchism political philosophy political that
あるトークンの前後d
単語を抜き出すだけなので簡単ですね。
83. 単語/文脈の頻度の計測
82の出力を利用し,以下の出現分布,および定数を求めよ.
- f(t,c): 単語tと文脈語cの共起回数
- f(t,∗): 単語tの出現回数
- f(∗,c): 文脈語cの出現回数
- N: 単語と文脈語のペアの総出現回数
gist817e4f2f21365f6871e98e1f25dfc2a5
go run q83.go N: 22760703
結果は表示しきれないため、総出現回数N
のみを表示しています。
84. 単語文脈行列の作成
83の出力を利用し,単語文脈行列を作成せよ.ただし,行列Xの各要素は次のように定義する.
ならば,
ならば,
ここで,はPositive Pointwise Mutual Information(正の相互情報量)と呼ばれる統計量である.なお,行列の行数・列数は数百万オーダとなり,行列のすべての要素を主記憶上に載せることは無理なので注意すること.幸い,行列のほとんどの要素は0になるので,非0の要素だけを書き出せばよい.
gista18d59730627de797661466de14525ab
// PPMIの大きい上位10個のみを表示 ❯ go run q84.go the number of the word: 390101 the number of contex word: 390101 length of X: 22760703 n(X)/(n(t) * n(c)): 0.0001495655404405392 ------------------ {{<br>MONSIEUR LECOQ} 13.30823695164182} {{Gols Gols} 13.02055487919004} {{nah nah} 12.979732884669785} {{LECOQ <br>MONSIEUR} 12.929583100984313} {{Kimmage Kimmage} 12.915194363532214} {{Terenure Terenure} 12.822248251022769} {{Priorswood Priorswood} 12.792134270774987} {{ου for} 12.728418456388878} {{molalities as} 12.5192987064402} {{Snana Made} 12.513398984313012}
何やらhtmlタグが入っていますが、先に進むことにします。。。 このあとの問題が次元削減なので、この時点での要素がどれくらいの規模になるのか表示させました。 また同時にどのくらいスパースなのかも見ておくことにしました。0.01%くらいの充填率のようです。
85. 主成分分析による次元圧縮
84で得られた単語文脈行列に対して,主成分分析を適用し,単語の意味ベクトルを300次元に圧縮せよ.
全量の確認
まず最初に述べておきますが、全量は実装できていません。
インプットとなるQ82の出力は以下のように6930万行となっています。
❯ wc ../data/q82.out.txt 69306584 138756729 852050914 ../data/q82.out.txt
本問題では、PCAを行う必要があるため、Golangで主成分分析する - 逆さまにしたでも紹介したpackage stat - gonumを利用しています。
ところがこの方法でPCAをしようとするとpanic: runtime error: makeslice: len out of range
のエラーが発生します。
Sparse matrix formatsを用いて、Sparseに行列を持つところまでは実装していますが、statパッケージでは、データの格納以前に初期化として、runtime
のmakeslice
を行うため上記エラーで失敗します。
どうしてもPCAできず、トレーニングデータのサイズを小さくすることで対処しています。
❯ head -1000000 ../data/q82.out.txt > ../data/q82_tmp.out.txt
gist002868aaa7d7abfa20365039735c192a
実は上記でも3500万行くらいであればメモリの確保はできるのですが、スワップが発生して計算が終わらないので、100万行まで落としています。 それでも1日以上掛かりました。。。
❯ go run q85.go // 出力はgobで行っておりバイナリフォーマットのため省略
86. 単語ベクトルの表示
85で得た単語の意味ベクトルを読み込み,"United States"のベクトルを表示せよ.ただし,"United States"は内部的には"United_States"と表現されていることに注意せよ.
gistffdac9cafb3d1efad815290df09730a1
❯ go run q86.go United_States : &{{1 [-0.014999052638340955 -0.06666512410686669 0.002520661466195838 (中略) -6.730425781930617e-15 -1.0561597069590151e-14]} 300}
問題文をそのまま実装してあげればOKです。もはやスパースではなくなっていますね。
goのmapは順番を保存しないので(一般的に保存しないため、以前改修されました)、rowの位置はQ85のdictt
で保存しておいたものを使います。
87. 単語の類似度
85で得た単語の意味ベクトルを読み込み,"United States"と"U.S."のコサイン類似度を計算せよ.ただし,"U.S."は内部的に"U.S"と表現されていることに注意せよ.
gistc5505e492f63667d5fe9e84e746ba955
❯ go run q87.go 0.4862803570718515
Q86で表示したベクトルのコサイン類似度を計算します。
mat
パッケージにはDot
関数があるので、そちらで内積とノルムを計算します。
最初に実装したときは、ノルムの平方根を取るのを忘れてしまいました。。。
データ数が少ないからか、コサイン類似度は0.486
でした。
88. 類似度の高い単語10件
85で得た単語の意味ベクトルを読み込み,"England"とコサイン類似度が高い10語と,その類似度を出力せよ.
gistc699a2323bcbc81fda3f93df14b922a5
※コード中にも記載していますが、England
が零ベクトルとなったため、United_States
で代用しています。
トレーニングデータを増やす必要があります。。。
❯ go run q88.go 1 case : 0.9548240697912775 2 2005 : 0.9108531345148447 3 2008 : 0.9019300375926617 4 addition : 0.8825165206539555 5 2012 : 0.8660833551129663 6 2001 : 0.8660833551129661 7 highest : 0.4998879708231505 8 turn : 0.4994728313281741 9 UK : 0.49755475904637503 10 event : 0.49489020770038084
Q87の拡張版みたいな問題です。
sortするためにCosineSimilarity
型を定義しています。
United_States
は西暦に関することが多いですね。case
も類似度が高いので各年で起きた事件などでしょうか。
89. 加法構成性によるアナロジー
85で得た単語の意味ベクトルを読み込み,vec("Spain") - vec("Madrid") + vec("Athens")を計算し,そのベクトルと類似度の高い10語とその類似度を出力せよ.
gista29690d4cf9fe2c6deac6c8cad633092
❯ go run q89.go 1 Spain : 1.0000000000000002 2 terms : 0.9997587662737554 3 languages : 0.9990898124310773 4 cases : 0.9967353219953207 5 small : 0.9960712723292813 6 Germany : 0.9843980937275112 7 areas : 0.9791005134719385 8 church : 0.9774278193367258 9 Rome : 0.9751437717985347 10 2000 : 0.9482871637356568
実装自体は、Q88をほとんど使いまわせます。分散表現することで、単語が意味ベクトルとなったため、加算減算ができるようになりました。
ただし、上記では、Q88と同様にMadrid
とAthens
が零ベクトルとなってしまっているため、Spain
だけで類似度を計算しているのと同じです。
結果を見ると実装自体は間違っていないので、トレーニングデータが不足していますね。
感想
解答中にも記載していますが、Q85,88,89は十分な結果が得られていません。 分散表現を実装することで単語の加法減法ができるようになったことと、どのように分散表現を作るのかは勉強になりましたが、Sparseな行列に対するPCAをうまく実装するのは改めて戻ってきたいと思います。
いつも通りコードはGithubにも置いてあります。
Reference
GolangでIBLTを実装してみた
前回の記事では、IBLTの概要について記載しました。 今回はIBLTのデータ構造と実装について記載します。 なお、使った図などはこちらにスライドとしてまとめています。
データ構造
IBLTは以下のようにm
個のcell
を持ちます。
各cell
には、count
、keySum
、valueSum
の3フィールドがあります。
今回はkeyとvalueはint
型として実装します。
cell
は上記3つのフィールドを持つstructとし、IBLT
をcell
のsliceとして、以下のように定義します。
type cell struct { count, keySum, valueSum int } type IBLT []cell
ハッシュ関数
IBLTではBloomFilterと同じようにkey-value pairをInsert
/Delete
するためcell
を決定するためハッシュ関数を用います。今回の実装上は、説明用の図に合わせ、ハッシュ関数の数をk = 3
としています。
メソッドの実装
前回の記事も記載しましたがIBLTでサポートされるメソッドは以下の4つです。
それぞれ実装していきます。
Insert
まずは、Insert
です。
Insert
は単純で、T
をIBLTとし、i = 1, ..., k
のハッシュ関数に対して以下の操作を行います。
- ].count++]
- ].sumKey += key]
- ].sumValue += value]
Insert(key=5, value=10)
とすると以下のようになります。
さらにInsert(key=2, value=30)
を追加でInsert
してみます。
実装は以下のようになります。
func (iblt IBLT) Insert(key, value int) { hash := util.CalcMD5Hash(strconv.Itoa(key)) hashA := hash[:int(len(hash)/2)] hashB := hash[int(len(hash)/2):] i64HashA, _ := strconv.ParseInt(hashA, 16, 64) i64HashB, _ := strconv.ParseInt(hashB, 16, 64) for i := 0; i < k; i++ { iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].count++ iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].keySum += key iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].valueSum += value } }
Get
次にGet
です。フローチャートに表すと以下のようになります。
何パターンか例を見ていきましょう。
(key, value) = (5, 10), (2, 30)
が挿入済みのIBLTに対して、Get(key=2)
を行ってみます。
1つ目のハッシュ関数でcount
が1
かつkeySum
がkey
と一致したため正しくvalue=30
を返せています。
次に(key, value) = (5, 10), (2, 30)
が挿入済みのIBLT(1つ前と同じ)に対して、Get(key=3)
(Insert
していないkey
)を行ってみます。
1つ目のハッシュ関数でcount
が0
となったため正しくfalse
を返せています。
最後に(key, value) = (5, 10), (2, 30)
が挿入済みのIBLT(前2つと同じ)に対して、Get(key=9)
(Insert
していないkey
)を行ってみます。
1つ目のハッシュ関数でcount
が1
となりましたが、keySum
がkey
と一致しませんでした。
2,3つ目のハッシュ関数ではcount
が2
となり、k = 3
個のハッシュ関数の探索が終わったため、正しくfalse
を返します。
Getに関する補足
上で見たようにGet
は、ハッシュ関数で特定したcell
のcount
が1
かつkeySum
がkey
と一致(一つしかInsert
していないcell
でkey
が一致する)であれば、valueSum
を返します。BloomFiterと同じく、いくつかのハッシュ関数が衝突したとしても一つでも衝突してない(count
が0
)のcell
があれば、正しくfalse
を返します。
BloomFilterと異なる点としては、ハッシュ衝突が起こっても、keySum
のチェックがあるため、key
が異なればfalse
を返します。ただし注意が必要なのは、count
が1
のときにのみ正しいvalue
を返してくれる点です。Insert
が複数に渡って行われた場合、count
が2
以上のcell
ばかりになり、正しくInsert
したkey
であってもfalse
を返します。つまり、false-negativeがあります(false
と返したが、実はkey
はInsert
されている)。
false-negativeが起こる例も見てみましょう。
(key, value) = (5, 10), (2, 30), (3, 20)
が挿入済みのIBLT(これまでの例より(3, 20)
が多い)に対して、Get(key=2)
(Insert
済みのkey
)を行ってみます。
1,2,3つ目のハッシュ関数のいずれでもcount
が2
となり、k = 3
個のハッシュ関数の探索が終わったため、誤ってfalse
を返します。
この辺は、原論文で言及されていないのですが、あまり嬉しくない性質ですね。
実装は以下です。
func (iblt IBLT) Get(key int) (bool, int) { hash := util.CalcMD5Hash(strconv.Itoa(key)) hashA := hash[:int(len(hash)/2)] hashB := hash[int(len(hash)/2):] i64HashA, _ := strconv.ParseInt(hashA, 16, 64) i64HashB, _ := strconv.ParseInt(hashB, 16, 64) for i := 0; i < k; i++ { idx := util.DoubleHashing(i64HashA, i64HashB, i, len(iblt)) if iblt[idx].count == 0 { return false, 0 } if iblt[idx].count == 1 { if iblt[idx].keySum == key { return true, iblt[idx].valueSum } return false, 0 } } return false, 0 }
Delete
Delete
はInsert
の逆の手順となります。
- ].count--]
- ].sumKey -= key]
- ].sumValue -= value]
(key, value) = (5, 10), (2, 30)
が挿入済みのIBLTにDelete(key=2, value=30)
を行ってみます。
(key, value) = (5, 10)
だけInsert
した状態と一致し、正しくDelete
できています。
ここで、Insert
していないkey
に対してもDelete
が実行できることに注意してください。
実装は以下です。
func (iblt IBLT) Delete(key, value int) { hash := util.CalcMD5Hash(strconv.Itoa(key)) hashA := hash[:int(len(hash)/2)] hashB := hash[int(len(hash)/2):] i64HashA, _ := strconv.ParseInt(hashA, 16, 64) i64HashB, _ := strconv.ParseInt(hashB, 16, 64) for i := 0; i < k; i++ { iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].count-- iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].keySum -= key iblt[util.DoubleHashing(i64HashA, i64HashB, i, len(iblt))].valueSum -= value } }
ListEntries
最後にListEntries
です。
ListEntries
はkey-value pairを列挙するため、以下のPair
を定義します。
type Pair struct { key, value int }
フローチャートは以下のようになります。
これまでと同じように例を見ていきます。
(key, value) = (5, 10), (2, 30)
が挿入済みのIBLTにからPair
を列挙するため、
ListEntries()
を行ってみます。
cell
を前から順番に見ていき、count
が1
となるcell
が見つかれば、そのPair
を列挙、削除し、また最初からcell
を見ていきます。
Insert
済みであった(5, 10), (2, 30)
が列挙できました。
実装は以下です。
func (iblt IBLT) ListEntries() []Pair { var pairs []Pair newIblt := NewIBLT(len(iblt)) copy(newIblt, iblt) LABEL: for i := 0; i < len(newIblt); i++ { if newIblt[i].count == 1 { pairs = append(pairs, Pair{ key: newIblt[i].keySum, value: newIblt[i].valueSum, }, ) newIblt.Delete(newIblt[i].keySum, newIblt[i].valueSum) goto LABEL } } return pairs }
最後に
false-negativeがあるので使い所を選ぶのではないかというのが所感ですが、集合一致のような列挙が必要な用途では要素をサマライズしたテーブルを渡せるIBLTは有用そうです。実際、Grapheneでは、新しいブロックに2000tx入っている前提で2.6KBに圧縮できると述べられており、同条件のCompact Blocksの10KBに比べて3倍以上の圧縮効率となります。
また、今回実装したIBLTだけでなく、BloomFilterやcounting BloomFiterの実装もGithubにあげてあります。
References
- ビットコインキャッシュの使用ブロック伝播速度を10倍にする新技術”Graphene”
- Graphene: A New Protocol for Block Propagation Using Set Reconciliation
- Invertible Bloom Lookup Tables
- O(1) Block Propagation
- ビットコインとは何か? 第4回:ビットコインの仕組み(取引承認と採掘) - Bitcoin日本語情報サイト
- BloomFilterについて調べてみた - 逆さまにした
- GolangでBloomFilterを実装してみた - 逆さまにした
- Golangでcounting BloomFilterを実装してみた - 逆さまにした
- goBloomFilter/iblt
- Bitcoin block propagation with IBLT, Part I: infographic
- Bitcoin Cashのブロック伝搬速度を10倍にするGrapheneで使われているInvertible Bloom Lookup Tables(IBLT)について調べてみた - 逆さまにした
- How IBLT Works
Bitcoin Cashのブロック伝搬速度を10倍にするGrapheneで使われているInvertible Bloom Lookup Tables(IBLT)について調べてみた
Bitcoin Cashのブロック伝搬速度を10倍にするという話もあるGrapheneでも使われている Invertible Bloom Lookup Tables(以下、IBLT)について調べました。
背景
IBLTはもともと集合一致などで使われるデータ構造です。ブロックチェーンに限った技術ではありませんが、ここではGrapheneでも導入として話される内容で述べます。
まず、マイナーがBTCやBCHのブロックをマイニングする際には、各マイナーノードが持つmempoolから一定のポリシー(feeが高い順など)に基づき、ユーザのトランザクション(以下、tx)を選びます。
ところが各マイナーが持っているmempoolは完全に同期しておらず、マイナーは新しいブロックを見つけたら(マイニングに成功したら)、そのブロックに含んでいるtxもブロードキャストする必要があります。Grapheneはこの「ブロックに含まれるtxを伝搬するコスト」を下げたいことがモチベーションとなります。
仮に完全にmempoolが同期できており、同じポリシーでtxを選ぶならtxをブロードキャストする必要もありません。例えば、「feeが高い順にtotal block sizeがxxMBまで」というポリシーに基づいて、同期されたmempoolからtxを選べば、新しいブロックに含まれるtxは確定できるため、わざわざ伝達してあげる必要もありません。
しかし、上述の通り、mempoolは完全に同期できてはいません。とはいえ、各マイナーが持つmempoolはほとんど同じです。この前提のときに効率的にmempoolという集合の差分を伝え、集合一致させる技術がIBLTです。
BloomFilterとIBLT
IBLTは、BloomFilterと多数の類似性を持つため、BloomFiterと比較し、IBLTをみていきます。まず、一般的なBloomFilterでは、以下の操作をサポートします。
- keyのInsert
- kyeのGet
counting BloomFilterでは、空間効率性を少々犠牲にし、
- keyのDelete
も可能にします。
※BloomFilterについては、以前の記事 や実装(と要素技術)を参照ください。
対して、IBLTでは、以下の操作をサポートします。
特筆すべきはListEntries
で、IBLTに含まれるkey-value pairを列挙することができます。
ListEntries
の利用方法を見るために、
Bitcoin block propagation with IBLT, Part I: infographicを参考にブロックチェーンでどのようにIBLTが使われるのか見てみたいと思います。リンク先の図を見ながらだとわかりやすいと思います。
IBLTを使った集合一致
集合一致までの流れを箇条書きで記載します。
- マイナーは、複数のtxを含めたブロックを生成
- 各txをkey-value pairとしてIBLTに割り当てる
- k個のハッシュ関数でkeyに対するハッシュ値を計算し、ハッシュ値をindexと思って各txをIBLTのcellに格納
- 3.で作成したIBLTをブロードキャスト
- IBLTを受け取ったマイナーは自分のmempoolから1.のminerと同じポリシーでtxを選ぶ(ただし、mempoolは完全に同期しているわけでないので、同じtxが選ばれるとは限らない)
- 選んだtxたちに対して、2.,3.と同じ操作で、受信側のマイナーでもIBLTを作成
ListEntries
によって3.のIBLTのkey-value pairを列挙し、6.のIBLTからDelete
していく- 7.の操作で選んだtxの差分が得られる
Grapheneでは、上記を効率的に行うために、BloomFilterを差分を計算する補助として使っています。BloomFilterは、false-positiveはあってもfalse-negativeは原理的にないので、受信側でIBLTを作る時のフィルタとして使っているようです。
長くなってしまったので、IBLTのデータ構造やサポートされる各操作の実装は次回の記事にまとめます。
References
- ビットコインキャッシュの使用ブロック伝播速度を10倍にする新技術”Graphene”
- Graphene: A New Protocol for Block Propagation Using Set Reconciliation
- Invertible Bloom Lookup Tables
- O(1) Block Propagation
- ビットコインとは何か? 第4回:ビットコインの仕組み(取引承認と採掘) - Bitcoin日本語情報サイト
- BloomFilterについて調べてみた - 逆さまにした
- GolangでBloomFilterを実装してみた - 逆さまにした
- Golangでcounting BloomFilterを実装してみた - 逆さまにした
- Bitcoin block propagation with IBLT, Part I: infographic
Atom gotestsでレシーバがあったときにテストが自動生成されないバグを直した話
Atom gotestsでレシーバがあったときにテストが生成されないバグを直した話
少し前に以下のツイートをし、Atom pluginのgotestsを使って ユニットテストの自動生成をしてました。
goのテスト自動生成ツール。めっちゃ便利。すごい。https://t.co/15Fd5sq2VI
— さいぺ (@cipepser) 2018年2月25日
ところがタイトルにあるように、レシーバがあるようなfunc
では、テストが自動生成されませんでした。
実際にテストを生成しているのはcweillのgotestsで、 (例ですが)以下のようにコマンドラインで実行すると、レシーバありでも問題なく、テストが生成されました。
❯ gotests -w -only=Hello ./hello.go
ご想像の通りplugin側に問題があったので、修正しました。 PRを送り、無事マージされたので 同じような問題で困っている方がいれば最新版へアップデートして、利用してみてください。
References
【Golang】gobで変数をファイルに保存する
gobは、Go専用のバイナリシリアライズフォーマットです。 シリアライズフォーマットとしては、Protocol Buffers1がデファクトでしょうし、Go専用のgobは他の言語で扱えず、使い勝手としても難しいところです。 しかし、Goしか使っていないような環境で、変数をファイルに保存したい場合などでは便利なので、備忘メモとしてもまとめたいと思います。
考え方は、Gobs of data - The Go Blog やencoding/gobでinterface{}をシリアライズする がとても参考になりました。
また、Redditでも議論されているように、structのsliceをdeep copyしたいときの手段としてgobが有用そうです。
概要
gobは、encoding/gob
に標準パッケージとして用意されています。
使う際も
NewEncoder(w io.Writer)
とNewDecoder(r io.Reader)
が用意されているので、jsonを扱うときと同じ要領で扱うことができます。
今回は、以下で定義したPerson
型の変数をファイルへ保存、ファイルから復元してみます。
type Person struct { Name string Age int }
ファイルへ保存
package main import ( "encoding/gob" "log" "os" ) type Person struct { Name string Age int } func main() { p := Person{ "Alice", 20, } f, err := os.Create("./save.txt") if err != nil { log.Fatal(err) } defer f.Close() enc := gob.NewEncoder(f) if err := enc.Encode(p); err != nil { log.Fatal(err) } }
ファイルから復元
package main import ( "encoding/gob" "fmt" "log" "os" ) type Person struct { Name string Age int } func main() { f, err := os.Open("./save.txt") if err != nil { log.Fatal(err) } defer f.Close() var q Person dec := gob.NewDecoder(f) if err := dec.Decode(&q); err != nil { log.Fatal("decode error:", err) } fmt.Println(q) // {Alice 20} }
References
Visual Studio Codeをインストールするときにやったこと
AtomからVScodeに移行したメモです。 自分しか使ってないようなkey-bindとかもありますが、 同じように設定に困ったら参考にしてください。
カラーテーマ
表示関連
goのソースコードのみタブを半角スペース2つへ
"[go]": { "editor.insertSpaces": true, "editor.tabSize": 2, "editor.autoIndent": false }
全角スペースを強調
以下パッケージをインストール
半角スペースを強調
表示
→ 空白文字の表示の切り替え
折り返し
"editor.wordWrap": "on"
key-bind系
パッケージ
エディタの分割
defaultのまま
{ "key": "ctrl+alt+cmd+[IntlYen]", "command": "workbench.action.splitEditor" }
cmd+cでESCされてしまう(vimパッケージによる)
ショートカットを削除
{ "key": "", "command": "extension.vim_cmd+c" }
行を跨いて左右の移動ができない(vimパッケージによる)
ショートカットを削除
{ "key": "", "command": "extension.vim_left" }
{ "key": "", "command": "extension.vim_right" }
go to def
ショートカットを変更
定義へ
{ "key": "cmd+d", "command": "editor.action.goToDeclaration", "when": "editorHasDefinitionProvider && editorTextFocus && !isInEmbeddedEditor" }
定義から戻る
{ "key": "shift+cmd+d", "command": "workbench.action.navigateBack" }
置換
ショートカットを変更
{ "key": "shift+cmd+f", "command": "editor.action.startFindReplaceAction" }
移動
ショートカットを変更
行頭へ
{ "key": "ctrl+a", "command": "cursorLineStart", "when": "editorTextFocus" }
行末へ
{ "key": "ctrl+e", "command": "cursorLineEnd", "when": "editorTextFocus" }
Go関連
パッケージ
合わせて必要なパッケージをターミナルからインストールしておく。
go get -u -v github.com/nsf/gocode go get -u -v github.com/rogpeppe/godef go get -u -v github.com/zmb3/gogetdoc go get -u -v github.com/golang/lint/golint go get -u -v github.com/lukehoban/go-outline go get -u -v sourcegraph.com/sqs/goreturns go get -u -v golang.org/x/tools/cmd/gorename go get -u -v github.com/tpng/gopkgs go get -u -v github.com/newhook/go-symbols go get -u -v golang.org/x/tools/cmd/guru go get -u -v github.com/cweill/gotests/... go get github.com/derekparker/delve/cmd/dlv
go tests generate
ショートカットを登録
{ "key": "shift+cmd+g", "command": "go.test.generate.function" }
go testsの実行(*_test.goで以下コマンドを実行)
{ "key": "f5", "command": "go.test.file" }
go testsのcoverageを表示
{ "go.buildFlags": ["-cover"] }
markdown
preview
{ "key": "ctrl+shift+m", "command": "markdown.showPreviewToSide", "when": "editorLangId == 'markdown'" }
previewと本文が一緒に動かないようにしたい
{ "markdown.preview.scrollPreviewWithEditorSelection": false }
ターミナル
ターミナルへ移動
{ "key": "ctrl+cmd+t", "command": "workbench.action.terminal.focusPrevious" }
ターミナルのカーソルを縦棒(|)にする
{ "terminal.integrated.cursorStyle": "line" }
その他
メッセージボックスを消す
以下ショートカットを追加
{ "key": "escape", "command": "workbench.action.closeMessages", "when": "globalMessageVisible" }
最後に
最終的なkeybindings.json
とsettings.json
は、Githubに上げてあります。
References
ブロックチェーンアプリケーション開発の教科書を読んでハマったところメモ
ブロックチェーンアプリケーション開発の教科書 / 加嵜長門(著), 篠原航(著), 丸山弘詩(編集)を読みました。
上記の構成になっており、仮想通貨界隈で議論されているトピックについて網羅的に記載されています。トピックの多さにびっくりしました。
特にエンジニアの方で、「ブロックチェーンや仮想通貨盛り上がってるけど何をしたらいいのかよくわからない」という場合は
とりあえず本書を読んでおけばよいなという感じです。
そしてなんといっても本書のメインである「Ethereumのスマートコントラクト実装:6-8章」はひたすら丁寧に記載されています。各行の処理やこの関数で何をしてるのかなど。
まさに自分もライトニングネットワークというような用語となんとなくの意味はわかるものの、
スマートコントラクトの実装などになるとさっぱりという状態だったので、
本書を読むべきタイミングで読めたことをうれしく思います。
とても良かったのでおすすめしたいのですが、バージョン違いなどで本書通りでは動作しない箇所がありました。 自分で手を動かしてハマってしまったところをメモ代わりに残します。 途中でハマり投げ出したくなった方の一助になればと思います。
version
上述の通り、本書が書かれたタイミングからバージョンが上がってしまったことによるハマりどころもあるのかと思うので、 本記事でもバージョンを記載しておきます。 良くも悪くも発展途上のため、今後のアップデートなどで動作が変わると思うのでご注意ください。
geth
geth-darwin-amd64-1.8.1-1e67410e
npmのバージョン
> npm version { 'dapps-token': '1.0.0', npm: '5.6.0', ares: '1.13.0', cldr: '32.0.1', http_parser: '2.7.0', icu: '60.2', modules: '59', napi: '2', nghttp2: '1.29.0', node: '9.5.0', openssl: '1.0.2n', tz: '2017c', unicode: '10.0', uv: '1.19.1', v8: '6.2.414.46-node.18', zlib: '1.2.11' }
truffle
> truffle version Truffle v4.0.6 (core: 4.0.6) Solidity v0.4.19 (solc-js)
コマンド6.1.4.3: Gethの初期化処理
genesis.json
でtypoしてしまったため、一度実行に失敗しました。
キャッシュもっているのか修正後も以下のようにFatal
となってうまくいきませんでした。
一度genesis.json
を消してから再実行したら成功しました。
# geth --datadir ~/geth/private_net init ~/geth/private_net/genesis.json Fatal: Failed to read genesis file: open ~/geth/private_net/genesis.json: no such file or directory
コード8.2.3.1: トークンのコントラスト
StandardToken.sol
がimportできませんでした。
truffle(develop)> test Error: Could not find zeppelin-solidity/contracts/token/StandardToken.sol
本文とStandardToken.sol
のPATHが変わっているのでDappsToken.sol
を修正します。
// DappsToken.sol pragma solidity ^0.4.18; import "zeppelin-solidity/contracts/token/ERC20/StandardToken.sol";
上記に伴って、DappsToken.sol
中のDappsToken
の引数もuint
からuint256
に変更します。
また、totalSupply
もERC20/BasicToken.sol
中でtotalSupply_
となっているので修正します。
// DappsToken.sol contract DappsToken is StandardToken { string public name = "DappsToken"; string public symbol = "DTKN"; uint public decimals = 18; function DappsToken(uint256 initialSupply) public { totalSupply_ = initialSupply; balances[msg.sender] = initialSupply; } }
8-2 ERC20準拠のトークン作成のファイル位置
慣れれば当然なのでしょうが、本節で書いた各ファイルの配置は、
dapps-token
をカレントディレクトリとして以下です。
./contracts/DappsToken.sol(コード8.2.3.1) ./migrations/2_deploy_dapps_token.js ./test/DappsTokens.js
Ropstenネットワークへのデプロイ
コード8.3.2.14の通りにgas
を設定しても以下のエラーメッセージが出てきて、デプロイできませんでした。
> truffle migrate --network ropsten Using network 'ropsten'. Running migration: 2_deploy_dapps_token.js Deploying DappsToken... ... <hash> Error encountered, bailing. Network state unknown. Review successful transactions manually. Error: The contract code couldn't be stored, please check your gas amount.
truffleの公式ドキュメントや
githubのissue、
StackExchange
あたりを読んでも、同じエラーメッセージなのに解決策がマチマチで、ここで一番ハマりました。
自分の場合は、2_deploy_dapps_token.js
のgas
と同じく
truffle.js
のgas
も以下のように設定することでうまくいきました。
// truffle.js module.exports = { networks: { ropsten: { provider: function() { return new HDWalletProvider( mnemonic, "https://ropsten.infura.io/" + accessToken ); }, network_id: 3, gas: 2000000 } } };
Tips
truffleを終了させる
truffle(develop)> .exit
truffle migrateをやり直すとき
コンパイル結果がbuild
配下にあるので、削除したほうが無難です。
> rm -R build
Refs
- ブロックチェーンアプリケーション開発の教科書
- RUNNING MIGRATIONS - TRUFFLE
- The contract code couldn't be stored, please check your gas amount during successful deployment #558
- The contract code couldn't be stored, please check your gas amount - StackExchange
- 作者: 加嵜長門,篠原航,丸山弘詩
- 出版社/メーカー: マイナビ出版
- 発売日: 2018/02/01
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る