GithubのGraphQLを触ったメモ書き

最近GraphQLなる言葉をよく見るようになったので、調べつつ、習うより慣れろで触ってみたのでその形跡を残します。

GraphQLとは

GraphQLを読んだ印象としては、API越しのQuery languageと理解しました。 RESTの次のパラダイムはGraphQLかにもあるようにREST APIとの対比で語られているようです。

自分でもなんらかのサービスで提供されているAPIを叩くことがありますが、レスポンスには実際に欲しいデータだけでなく、余分なデータも含まれています。リクエストを投げる時点で欲しい情報をクエリパラメタとして渡してあげることで、必要な情報だけをレスポンスとして得られるのが利点と考えます。 RESTの次のパラダイムはGraphQLかでは、その他の問題も完結にまとめられているのでわかりやすいです。

GithubのExploreで触ってみる

GithubGUIでGraphQLを触れるExploreを提供してくれているので、実際に触って所感を掴みましょう。 クエリのReferenceはこちら

以下は「自分のレポジトリを更新順に並べ、最初のn個を取得」するクエリです。 変数を$nとして受け取らせています。 また、viewerがログインしているユーザ(自分自身)を表します。

// query
query($n: Int!){
  viewer {
    repositories(orderBy: {field: UPDATED_AT, direction: DESC}, first: $n) {
      edges {
        node {
          name
        }
      }
    }
  }
}

// variables
{
  "n": 3
}

これを実行すると以下のようにjsonでレスポンスが返ってきます。

{
  "data": {
    "viewer": {
      "repositories": {
        "edges": [
          {
            "node": {
              "name": "goSExpression-sample"
            }
          },
          {
            "node": {
              "name": "poloniex"
            }
          },
          {
            "node": {
              "name": "goXML"
            }
          }
        ]
      }
    }
  }
}

型がある

GraphQLでは型も定義されており、今回の例だと repositoriesorderByフィールドはRepositoryOrder型になります。 ReferenceにもあるようにRepositoryOrderField型のfieldOrderDirection型のdirectionをメンバとして持っています。

なので以下のようにhogeという誤った型のクエリをわざと発行してみます。

query($n: Int!){
  viewer {
    repositories(orderBy: hoge, first: $n) {
      edges {
        node {
          name
        }
      }
    }
  }
}

すると以下のように、型が違うエラーが返ってくる実装になっていました。

{
  "data": null,
  "errors": [
    {
      "message": "Argument 'orderBy' on Field 'repositories' has an invalid value. Expected type 'RepositoryOrder'.",
      "locations": [
        {
          "line": 3,
          "column": 5
        }
      ]
    }
  ]
}

感想

とりあえず触ってみたというレベルですが、GraphQLでした。今後RESTを置き換えていくのかはわかりませんが、型があり、必要な情報だけを取ってこれるというのは場面によっては有効そうです。 RESTがこれだけ世の中に溢れていることを考えると、RESTからの移行をどうやって設計するのかなど考えるのは楽しそうですね。

Reference

Golangで言語処理100本ノック2015 第6章: 英語テキストの処理

言語処理100本ノック 2015の第6章: 英語テキストの処理の10問です。

50. 文区切り

(. or ; or : or ? or !) → 空白文字 → 英大文字というパターンを文の区切りと見なし,入力された文書を1行1文の形式で出力せよ.

gist4437579cb8e6b64166d0de27b1ce49b4

// 最初の7文のみ抜粋

# go run q50.go
Natural language processing
From Wikipedia, the free encyclopedia

Natural language processing (NLP) is a field of computer science, artificial intelligence, and linguistics concerned with the interactions between computers and human (natural) languages.
As such, NLP is related to the area of humani-computer interaction.

History

The history of NLP generally starts in the 1950s, although work can be found from earlier periods.
In 1950, Alan Turing published an article titled "Computing Machinery and Intelligence" which proposed what is now called the Turing test as a criterion of intelligence.

golangでは、lookaheadをサポートしていないので、次の一文のCapitalを回してあげるのがめんどうでした。

51. 単語の切り出し

空白を単語の区切りとみなし,50の出力を入力として受け取り,1行1単語の形式で出力せよ.ただし,文の終端では空行を出力せよ.

// q50の結果をtxtに保存しておく
# go run q50.go > ../data/q50_out.txt

gist154c531bd00e06627a06871620015ece

// 最初の3文のみ抜粋
# go run q51.go

Natural
language
processing

From
Wikipedia,
the
free
encyclopedia



Natural
language
processing
(NLP)
is
a
field
of
computer
science,
artificial
intelligence,
and
linguistics
concerned
with
the
interactions
between
computers
and
human
(natural)
languages.

As
such,
NLP
is
related
to
the
area
of
humani-computer
interaction.

Splitするだけなので余裕ですね。

52. ステミング

51の出力を入力として受け取り,Porterのステミングアルゴリズムを適用し,単語と語幹をタブ区切り形式で出力せよ. Pythonでは,Porterのステミングアルゴリズムの実装としてstemmingモジュールを利用するとよい.

// q51の結果をtxtに保存しておく
# go run q51.go > ../data/q51_out.txt

gist8a0fc9ac1d9432a9da14bd87d91476ae

# go run q52.go

// 最初の3文のみ抜粋
Natural      natur
language     languag
processing   process
From     from
Wikipedia,   wikipedia,
the      the
free     free
encyclopedia     encyclopedia
Natural      natur
language     languag
processing   process
(NLP)    (nlp)
is   is
a    a
field    field
of   of
computer     comput
science,     science,
artificial   artifici
intelligence,    intelligence,
and      and
linguistics      linguist
concerned    concern
with     with
the      the
interactions     interact
between      between
computers    comput
and      and
human    human
(natural)    (natural)
languages.   languages.
As   as
such,    such,
NLP      nlp
is   is
related      relat
to   to
the      the
area     area
of   of
humani-computer      humani-comput
interaction.     interaction.

golangでのstemming実装としてGo Porter Stemmerを使いました。

53. Tokenization

Stanford Core NLPを用い,入力テキストの解析結果をXML形式で得よ.また,このXMLファイルを読み込み,入力テキストを1行1単語の形式で出力せよ.

// 公式サイトからDownloadし、zipを解凍したフォルダで以下のshellを実行すると、実行したディレクトリにxmlファイルが生成される
# cd stanford-corenlp-full-2017-06-09
# ./corenlp.sh -annotators tokenize,ssplit,pos,lemma,ner,parse,dcoref -outputFormat xml -file <YOUR_PATH_TO>/nlp.txt
# mv ./nlp.txt.xml ../data

// xmlから自動的にgo structを作り出す
# chidley -G -e "" ../data/nlp.txt.xml

gist9672a32d376e48be9bf55571c799db31

// 最初の1文のみ抜粋
# go run q53.go
Natural
language
processing
From
Wikipedia
,
the
free
encyclopedia
Natural
language
processing
-LRB-
NLP
-RRB-
is
a
field
of
computer
science
,
artificial
intelligence
,
and
linguistics
concerned
with
the
interactions
between
computers
and
human
-LRB-
natural
-RRB-
languages
.

Stanford Core NLPを初めて触ったので実行の仕方がわからなくて苦労しました。 golangで実装するのはxmlの読み込みからです。 前処理にも書きましたが、自分でgo structを定義し直すのは面倒なので、chidleyを使って自動生成させています。

54. 品詞タグ付け

Stanford Core NLPの解析結果XMLを読み込み,単語,レンマ,品詞をタブ区切り形式で出力せよ.

gist701c1fdd47b0777c7a6c8cbb1f663bb5

# go run q54.go
Natural      natural     JJ
language     language    NN
processing   processing      NN
From     from    IN
Wikipedia    Wikipedia   NNP
,    ,   ,
the      the     DT
free     free    JJ
encyclopedia     encyclopedia    NN
Natural      natural     JJ
language     language    NN
processing   processing      NN
-LRB-    -lrb-   -LRB-
NLP      nlp     NN
-RRB-    -rrb-   -RRB-
is   be      VBZ
a    a   DT
field    field   NN
of   of      IN
computer     computer    NN
science      science     NN
,    ,   ,
artificial   artificial      JJ
intelligence     intelligence    NN
,    ,   ,
and      and     CC
linguistics      linguistics     NNS
concerned    concern     VBN
with     with    IN
the      the     DT
interactions     interaction     NNS
between      between     IN
computers    computer    NNS
and      and     CC
human    human   JJ
-LRB-    -lrb-   -LRB-
natural      natural     JJ
-RRB-    -rrb-   -RRB-
languages    language    NNS
.    .   .

Q53から出力部分を変えるのみです。

55. 固有表現抽出

入力文中の人名をすべて抜き出せ.

gist6ee9809052e2294a98ef9237316525c2

# go run q55.go
Alan
Turing
Joseph
Weizenbaum
MARGIE
Schank
Wilensky
Meehan
Lehnert
Carbonell
Lehnert
Racter
Jabberwacky
Moore

Stanford Core NLPで解析を行うと、人名がNERPERSONとして現れてくるのでそれを抜き出してあげるだけです。

56. 共参照解析

Stanford Core NLPの共参照解析の結果に基づき,文中の参照表現(mention)を代表参照表現(representative mention)に置換せよ.ただし,置換するときは,「代表参照表現(参照表現)」のように,元の参照表現が分かるように配慮せよ.

gistf36c33493e5d272f743916088a8ad6f5

// 最初の5文のみ抜粋
# go run q56.go
Natural language processing From Wikipedia , the free encyclopedia Natural language processing -LRB- NLP -RRB- is [the free encyclopedia Natural language processing -LRB- NLP -RRB-] (a field of computer science) , artificial intelligence , and linguistics concerned with the interactions between computers and human -LRB- natural -RRB- languages .
As such , NLP is related to the area of humani-computer interaction .
Many challenges in NLP involve natural language understanding , that is , enabling [computers] (computers) to derive meaning from human or natural language input , and others involve natural language generation .
History The history of NLP generally starts in the 1950s , although work can be found from earlier periods .
In 1950 , Alan Turing published an article titled `` Computing Machinery and Intelligence '' which proposed what is now called the [Alan Turing] (Turing) test as a criterion of intelligence .

参照表現を()で括り、もとの代表参照表現を[]で括っています。
全文まとめてStanford Core NLPで解析したからか微妙な解析結果もちらほらあるようです。 しかし一文ずつ解析すると文をまたがった表現が拾えないので全文まとめた解析としました。

57. 係り受け解析

Stanford Core NLP係り受け解析の結果(collapsed-dependencies)を有向グラフとして可視化せよ.可視化には,係り受け木をDOT言語に変換し,Graphvizを用いるとよい.また,Pythonから有向グラフを直接的に可視化するには,pydotを使うとよい.

gistea1dc7dec630b507a0d3ce336acda10f

# go run q57.go
# dot -T png ../data/q57.dot -o ../data/q57.png
# open ../data/q57.png

f:id:cipepser:20170820125921p:plain

最初の一文をグラフにしました。 Goでの有向グラフの書き方は以前まとめたのでこちらをご覧ください。

58. タプルの抽出

Stanford Core NLP係り受け解析の結果(collapsed-dependencies)に基づき,「主語 述語 目的語」の組をタブ区切り形式で出力せよ.ただし,主語,述語,目的語の定義は以下を参考にせよ.

  • 述語: nsubj関係とdobj関係の子(dependant)を持つ単語
  • 主語: 述語からnsubj関係にある子(dependent)
  • 目的語: 述語からdobj関係にある子(dependent)

gist01e16fef3dd5e2f567fa7b63896e239d

# go run q58.go
challenges   involve     generation
others   involve     generation
understanding    enabling    computers
Turing   published   article
experiment   involved    translation
ELIZA    provided    interaction
patient      exceeded    base
ELIZA    provide     response
which    structured      information
underpinnings    discouraged     sort
that     underlies   approach
Some     produced    systems
which    make    decisions
systems      rely    which
that     contains    errors
implementations      involved    coding
algorithms   take    set
Some     produced    systems
which    make    decisions
models   have    advantage
they     express     certainty
Systems      have    advantages
Automatic    make    use
that     make    decisions

mapで実装しようとしたらcannot assign to struct fieldのエラーが出てハマりました。

59. S式の解析

Stanford Core NLP句構造解析の結果(S式)を読み込み,文中のすべての名詞句(NP)を表示せよ.入れ子になっている名詞句もすべて表示すること.

gist6f587f61adc2ca08abf5eda2201d2dcb

// 最初の1文のみ抜粋
# go run q59.go
(NP (JJ Natural)(NN language)(NN processing))
(NP (NNP Wikipedia))
(NP (NP (DT the)(JJ free)(NN encyclopedia)(JJ Natural)(NN language)(NN processing))(PRN (-LRB- -LRB-)(NP (NN NLP))(-RRB- -RRB-)))
(NP (DT the)(JJ free)(NN encyclopedia)(JJ Natural)(NN language)(NN processing))
(NP (NN NLP))
(NP (NP (NP (DT a)(NN field))(PP (IN of)(NP (NN computer)(NN science))))(, ,)(NP (JJ artificial)(NN intelligence))(, ,)(CC and)(NP (NP (NNS linguistics))(VP (VBN concerned)(PP (IN with)(NP (NP (DT the)(NNS interactions))(PP (IN between)(NP (NP (NNS computers))(CC and)(NP (JJ human)(-LRB- -LRB-)(JJ natural)(-RRB- -RRB-)(NNS languages)))))))))
(NP (NP (DT a)(NN field))(PP (IN of)(NP (NN computer)(NN science))))
(NP (DT a)(NN field))
(NP (NN computer)(NN science))
(NP (JJ artificial)(NN intelligence))
(NP (NP (NNS linguistics))(VP (VBN concerned)(PP (IN with)(NP (NP (DT the)(NNS interactions))(PP (IN between)(NP (NP (NNS computers))(CC and)(NP (JJ human)(-LRB- -LRB-)(JJ natural)(-RRB- -RRB-)(NNS languages))))))))
(NP (NNS linguistics))
(NP (NP (DT the)(NNS interactions))(PP (IN between)(NP (NP (NNS computers))(CC and)(NP (JJ human)(-LRB- -LRB-)(JJ natural)(-RRB- -RRB-)(NNS languages)))))
(NP (DT the)(NNS interactions))
(NP (NP (NNS computers))(CC and)(NP (JJ human)(-LRB- -LRB-)(JJ natural)(-RRB- -RRB-)(NNS languages)))
(NP (NNS computers))
(NP (JJ human)(-LRB- -LRB-)(JJ natural)(-RRB- -RRB-)(NNS languages))
--------------

S式の簡易パーサを実装したのでそちらを使いました。 Treeは再帰的に処理させやすくてよいですね。

感想

Stanford Core NLPはもう少し丁寧に触るとかなりおもしろそうですね。 ステミングあたりなどは言葉から知らなかったり、パーサを初めて書いてみたり色々収穫の多い章でした。

いつも通りコードはGithubにも置いてあります。

Reference

GolangでS式の簡易パーサを書いてみた

言語処理100本ノック 2015のQ59でS式の解析の問題に出会ったので、パーサの自作なるものにチャレンジしたく、書いてみました。

前提

  • リテラルstringのみであるとする
  • パースした結果は多分木に格納する1

タスク

以下のS式を多分木にパースします。

(a(b(d(i)(j))(e)(f(k)))(c(g)(h(l(n))(m))))

わかりやすいように改行を入れると以下のようになります。

(a
  (b
    (d
      (i)
      (j)
    )
  (e)
  (f
    (k)
  )
)
(c
  (g)
  (h
    (l
      (n)
    )
    (m)
    )
  )
)

木にすると以下なイメージです。

f:id:cipepser:20170826135824p:plain

実装

Tree

まず、多分木を以下のように定義します。

type Tree struct {
    Parent *Tree
    Child  []*Tree
    Value  string
}

root node

root nodeは親を持たないので、便宜的に自分自身を親として、コンストラクタを書きます。

func NewTree() *Tree {
    t := &Tree{}
    t.Parent = t
    return t
}

実装

パーサの実装は以下です。

gistb526d47b5f834803b8d69ce4ccecbc63

Install

githubにあげてあるので以下でInstallできます。

# go get github.com/cipepser/goSExpression-sample/gose

Usage

以下のようにParse()でパースできます。

s := `(a(b(d(i)(j))(e)(f(k)))(c(g)(h(l(n))(m))))`
t, err := gose.Parse(s)

if err != nil {
  log.Fatal(err)
}

結果の表示は簡易的ですが、以下のようにWalk()でできるようにしました。

// t.Walk()

I am ' a '
my parent is ' a '
-------
I am ' b '
my parent is ' a '
-------
I am ' d '
my parent is ' b '
-------
I am ' i '
my parent is ' d '
-------
I am ' j '
my parent is ' d '
-------
I am ' e '
my parent is ' b '
-------
I am ' f '
my parent is ' b '
-------
I am ' k '
my parent is ' f '
-------
I am ' c '
my parent is ' a '
-------
I am ' g '
my parent is ' c '
-------
I am ' h '
my parent is ' c '
-------
I am ' l '
my parent is ' h '
-------
I am ' n '
my parent is ' l '
-------
I am ' m '
my parent is ' h '
-------

Reference


  1. あとで思えば抽象構文木にしたほうがよかった

Golangでjsonをbsonに変換する

Go言語でMongoDBを扱っているとjsonをbsonに変換したくなります。 APIのレスポンスがjsonで返ってきて、それをMongoDBに格納したいときなどですね。

Go言語でMongoDBを触るためのdriverには、mgoがあります。 変換もmgoからできるのでgo getしておきます。

go get gopkg.in/mgo.v2

あとはUnmarshalJSON()を適用してあげればOKです。 逆にbsonをjsonにしてあげたいときはMarshalJSON()を使います。

それぞれ実装例は以下です。

gist2bd83a17dba79bec793e5f07296e7b6e

References

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