競技プログラミング in Go #3
今回
今回は下記の記事を参考に迷路の最短路と特殊な状態の列挙のAtCoderの問題を解いていく。
qiita.com
幅優先探索
問題：C - 幅優先探索
解答：Submission #20044513 - AtCoder Beginner Contest 007
考えたこととか
[][]runeにしておくと、距離を保存する時に '1'~'9' までしか入れられないから面倒だった。距離用に [][]intの多次元配列を用意して、距離を見たい時はそっちから参照するようにした。
チーズ(Cheese)
問題：E - チーズ (Cheese)
解答：Submission #20049509 - 第１０回日本情報オリンピック 予選（オンライン）
考えたこととか
めちゃくちゃ苦戦した。計4回提出したが、大まかな方針は間違っていなかった。自作のqueueのパフォーマンスが悪かったため、queueについて少し計算を加えるような実装になっているとTLEやMLEが発生してしまっていた。これを通した時はqueueはそこまで原因になっていないと思っていたが、色々試す中で結果的にqueueに対する走査が減ったようでACとなった。これは時間を置いて再度解きたい。
Grid Repainting
問題：D - Grid Repainting
解答：Submission #20050170 - AtCoder Beginner Contest 088
考えたこととか
最大になる時は最短経路を通過する時なので、.の総数から最短経路のマスの数を引けば良い。素直な問題だったのですぐ解けた。
Darker and Darker
問題：A - Darker and Darker
解答：Submission #20050717 - AtCoder Grand Contest 033
考えたこととか
#を通過できないように前処理を入れたらあとはBFSをする。探索時に数字を渡しておいて、maxを取っていけば探索終了時にそれが答えになる。これも素直な問題だったのですぐ解けた。
器物損壊！高橋君
問題：C - 器物損壊！高橋君
解答：Submission #20134936 - AtCoder Regular Contest 005
考えたこととか
コストの扱いを考慮することはできていたけれど、上手く実装できなかった。ARC005には解説がないため、検索をして探したところ01BFSを使うと良いとのこと。なんのことかわからなかったので調べたらすごくわかりやすい記事を発見した。
これによりコストが低い選択肢が優先的に処理されるようになるため、障害物を避けた経路をより選択して探索を行うことができる。また、同じノードにたどり着く複数の経路があったとしても、01BFSではコストが低い選択肢を先に処理しているため、訪問済みとしてそのノードにチェックを入れて後続の探索で打ち切ることができる。
キューにpushFrontを実現するため、SliceTricksを見ながら実装を行った。
SliceTricks · golang/go Wiki · GitHub
しかしこれはTLEになってしまう。
先ほどのチーズ(Cheese)ではキューの実装が悪かったためにTLEになっておりキューに対する処理を減らすことでACできたが、今回はそうはいかなかった。そのため他の人の01BFSを使った解答を見たら下記のパッケージを使っていることがわかった。
go/src/container/list at master · golang/go · GitHub
SliceTricksの実装だとappend時に配列をたくさん作ることになり、特にpushFrontでは要素の長さだけ毎回メモリを確保してしまっていたのだと思う。なのでcontainer/listのようにlinked listになっていると非常に高速になった。
One-stroke Path
問題：C - One-stroke Path
解答：Submission #20176878 - AtCoder Beginner Contest 054
考えたこととか
探索できたものを数えれば良いのでそう実装していたのだがWAになってしまった。サンプルだけ通っていて何が起きているのかわからず解説を読んで通した。
WAの原因はindexの取り違いだった。for-rangeで回していた二次元配列の値をindexと間違えていて、DFSで誤った値が処理されていた。二次元配列のループはfor-rangeにせずにふつうにiをインクリメントしながら走査してvec[i][j]と値を見た方が直感的な気がした。
解説に載っていたDFSの前後でvisitedをtrue/falseとするコードはすごく良かったので取り入れて解答した。これを読む前はDFSで再帰する際にcopyして渡していたので、かなりメモリ効率が良くなったと思う。
カード並べ
問題：D - カード並べ
解答：Submission #20177931 - 第９回日本情報オリンピック 予選（オンライン）
考えたこととか
数が少ないので全部列挙してしまうのが良さそう。また、数字だと桁を考慮しないといけないので数字で扱うよりも文字列で扱って、mapのlenを取る実装が良さそう。懸念として文字列の結合コストがある。ここだけは気になる。
実際に実装してそれでOKだった。ただ、選択した数字のインデックスに対応して[]boolをtrueにして選び取る実装をしてしまい時間を食ってしまった。[]intにして選択したものをappendしてその順序を維持してmapに突っ込む。AC。
One-stroke Pathで学んだdfsの前後で状態をコントロールする実装ができたので嬉しい。
まとめ
DFSもBFSも特に迷わず実装できているけれど、状態をどうコントロールするのかまだスラスラ書けないので制約が増える度に手が遅くなるのを感じる。ただ書いていてすごく楽しい。
達人に学ぶDB設計を読んだ
背景
年末に読んだ。
感想
論理設計と物理設計
物理設計はなかなか馴染みがないので主に論理設計で知識が増えた。
論理設計はドメインをRDBにどういう形で落とし込むか決めることだ。設計にはエンティティの抽出、エンティティの定義、正規化、ER図の作成という流れを踏む。
一方、物理設計はテーブル定義、インデックス定義、ハードウェアのサイジング、ストレージの冗長構成決定、ファイルの物理配置決定、という流れを踏む。サイジングはあまり考えたことがなかったため下記の文章は気づきがあった。
データ量というのは、システムの運用開始から、基本的には増えていきます。
たしかに論理設計でテーブルの関係性だけを見ていると当たり前の話だけどわかってなかったな、と思った。
バックアップ
障害によってデータが失われた時に、それを復旧できるようにしておく必要がある。バックアップには主にフルバックアップ、差分バックアップ、増分バックアップの3種類がある。
フルバックアップは名前の通りデータを全てバックアップしておくこと。しかしバックアップに要する時間やリソース負荷が高く、整合性を保つためにサービス停止が必要など、運用上のコストが大きいという欠点がある。
差分バックアップは、フルバックアップした日以降はフルバックアップのデータとの差分をバックアップすることでフルバックアップのコストを軽くする手法。欠点としてはリカバリ時に差分をひとつひとつ適用させていく必要があるため、オペレーションが手間になるということだ。
増分バックアップは差分バックアップに似ており、フルバックアップした日以降はその日の変更分のみをバックアップする。
リカバリ
定時で行うバックアップだけだと障害発生直前の状態に戻すことができない。そのため、バックアップファイルだけでなく、トランザクションログを使って巻き戻すことが必要になる。
正規化
正規形とは、一言で言うと、データベースで保持するデータの冗長性を排除し、一貫性と効率性を保持するためのデータ形式です。
正規形についてどのようなものなのか改めて理解するきっかけとなった。定義はネットに沢山転がっているので省略。ここでは関数従属について理解が少し大変だったので整理したことを残しておく。
関数従属性
関数従属性は入力により出力が決定するような性質を指す。これはつまり主キーによってレコードが決定するということである。
発展して部分関数従属性というものがある。主キーが複数のカラムで構成されている時、主キーの一部のカラムで決定するカラムが存在するとする。その場合、そのテーブルは部分関数従属性を満たしていると言う。一方、部分的な関係性がなく主キーを構成する全てのカラムによりレコードが決定する場合は完全関数従属と呼ぶ。
最後に推移的関数従属だ。まず、主キーによって決定したカラムがある。そのカラムが別のカラムのキーとなっているとする。この時、主キーとそのキー、そのキーによって得られるカラムが推移的な関係となっている。名前の通りカラムが推移的な従属関係にある声質を推移的関数従属と呼ぶ。
関数従属性は漢字が並んでいてやや読み飛ばしたくなるが、内容はいたってシンプルだ。従属性が中途半端なテーブルに対して直感的に違和感を感じることはあるが、このように言語化され名前を知っていると解釈ができるし腑に落とせるので良かった。
サロゲートキー
アンチパターンやグレーパターンでは「まぁ、そうだな」と思うような悪手がたくさん載っていたが、サロゲートキーがそこに含まれていたのは意外だった。サロゲートキーは論理的なキーであり本来は不要なため、自然キーによる解決をする方が望ましいとのこと。理由は論理モデルをわかりにくくしてしまうため、何の役割を果たしているのか、ER図を見てもわからないから。
これは正直よくわかっていない。サロゲートキーはもはやサロゲートキー自体に意味が生まれていて、そういうコンテクストは共有されているような気がする。ORMのライブラリでもサロゲートキーが前提となっているようなものも多い。むしろ自然キーによる解決をされたテーブルの方が見かけないような気もしている。が、どうなんだろうか。理論的には全て自然キーで決定できるようにエンティティを抽出すべき、という話なのかも知れないが、現実はもっと複雑だと思う。このあたりは、書籍の性質上、主キーは自然キーであって然るべきと言っておく必要もあるのだろうか。
まとめ
正規化をちゃんと整理できたのは良かったなぁと思った。パフォーマンス関連は詳細まで話がなかったため別の書籍も参照した方が良いと思った。パフォーマンスだけで書籍が出ているくらい深遠なので、むしろ簡潔にしたのだと思う。
アンチパターンもひと通り読むことができたので、なんとなく感じていた違和感の名前を知れたのは良かった。
競技プログラミング in Go #2
前回
今回
今回は下記の記事を参考に部分和とLake CountingのAtCoderの問題を解いていく。
qiita.com
たくさんの数式
問題：C - Many Formulas
解答：Submission #19722074 - AtCoder Regular Contest 061
考えたこととか
+を入れるパターンを全列挙すれば良いと考えた。考慮として先頭の数字の扱いや桁の扱いがあるが、上手く考えきれず結構時間がかかってしまった。けれど、演算子ではなく符号で考えてしまえば先頭の数字を意識せずに処理ができることに気がついた。これに気がつくまで時間がかかってしまった。
解説を読むと、ビット演算で演算子を入れることが可能な箇所を全列挙して計算すると良いと書いてあったので、符号で考えるのは想定パターンじゃないのかも。
全列挙はビット演算で行った。Goで解いたがビット演算はC++と同じなので直感的に記述できた。ただ、ビット演算を書いていてi&1<<j >= 1でビットが立っているか確認する処理でバグらせてしまった。&は<<よりも優先順位が高いので、((i&1)<<j) >= 1となってしまっていた。あと、解答した後に思ったけれど、(i>>j)&1とすれば== 1と書けるのでわかりやすいかも。
解説では桁を考慮して10を掛けて足すような処理をしていた。ここはGoのSliceを上手く使って書けたのは良かった。
Train Ticket
問題：C - Train Ticket
解答：Submission #19722660 - AtCoder Beginner Contest 079
考えたこととか
これはすぐできた。数字の入力だけど文字列で受け取り、'0'を引くことで各数字の配列を得る。1パターンだけ見つければ良いので全部試して7になったら打ち切る。
All Green
問題：C - All Green
解答：Submission #19738173 - AtCoder Beginner Contest 104
考えたこととか
自力では解けなかった。要復習。
解説を読んだ上での感想として、得点パターンの確認を怠っていた。回答数ばかりに意識を取られて、どのような得点の積み方があるのか考えていなかった。さらにそこから、得点パターンを踏まえた上で最適化した積み方を考える必要があった。
高橋君とお肉
問題：A - 高橋君とお肉
解答：Submission #19738359 - AtCoder Regular Contest 029
考えたこととか
すぐできた。焼き時間をソートして空いている方を優先して焼けば良い。
派閥
問題：D - 派閥
解答：Submission #19765185 - AtCoder Beginner Contest 002
考えたこととか
自力で解けなかった。
1番大きいCycleを探せではなく1番大きいMeshを探せという問題。互いに知っている特性から、伸びているEdgeの数がそのNodeの関係数の最大値となる。なので、Edge先を番号を配列として控えておき、それをEdge先の各Nodeとも関係性があるのか確認するような処理にすれば、その最大値が答えになると思い実装をした。しかし、これでは解けなかったので解説を読んだ。
解説によると、これは最大クリーク問題と呼ばれる有名な問題とのこと。NP困難。
Meshと呼んでいたけど正しくはクリーク。今回の問題は入力値が小さい数字なので全探索できる。例えば1~3までの議員がいるなら、関係性の組み合わせは{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}の計8パターンになる。入力内容のグラフから、このパターンを全部確かめて最大のクリークになるものを探せば良い。
深さ優先探索
問題：A - 深さ優先探索
解答：Submission #19841473 - AtCoder Typical Contest 001
考えたこととか
問題名が答えみたいなもの。実装で思ったこととして、再帰関数の引数はバリデーションせずに渡してしまった方が楽。境界判定とかはインデックスとして使う前でやればOK。
一度通ったところに目印をつけておかないと無限ループするので、通ったところは'#'として通れなくしておく。
埋め立て
問題：B - 埋め立て
解答：Submission #19843166 - AtCoder Regular Contest 031
考えたこととか
さっきの問題には始点と終点があったので一瞬悩んだ。けれど数字が小さいので全探索できると気づいた。全ての座標から開始して、通過した点を'o'から'x'にする。もし埋め立てることが可能なのであれば、1つの座標から全ての'o'の座標を通過できるはずなので、全座標が'x'になったら埋め立て成功。
実装でひと手間必要だったところは2つあった。
まず多次元配列のコピー。全座標について通過した点の値を変える全探索をするため、探索用にコピーをしておく必要がある。しかし、多次元配列内の配列をコピーしても配列の値のポインタは変わらないので、ちゃんと値までコピーしてあげる必要がある。
func copyMatrix(src [][]rune) [][]rune { dst := make([][]rune, len(src)) for i, v := range src { dst[i] = make([]rune, len(v)) copy(dst[i], v) } return dst }
あとは探索の開始点を'x'ではなく'o'にしておくことだ。'x'のままで渡してしまうとバリデーションに引っかかってしまう。そのため前処理として開始点を'o'にする1行入れてあげるだけで実装がかなり楽になる。
バウムテスト
問題：B - バウムテスト
解答：Submission #20036890 - AtCoder Regular Contest 037
考えたこととか
自力で解くことができなかった。また、解説を読んでもすぐに解けなかった。不正解だった思考、解説を読んだ後、最終的な解答とその思考の順で書く。
不正解だった思考
紆余曲折しながら考えたので取り留めもない思考になっている。文章にすると非常にわかりづらいけれど、その通り思考も整理しきれていなかったのだとわかる。
まず、1度通ったノードを再度通れるなら閉路なので、それを判定できるようにすれば良さそうだと考えた。しかし、これまでのように通過したノードを通れないノードにすると、通過済みなのか元から通過できないのか判断できなくなってしまう。そのため、ステータスとして未探索と探索中と閉路の3つを用意してあげれば良さそうだと思った。探索中のステータスのノードにぶつかったら、閉路として塗り直す。そうすれば最終的に残る木が答えになる。
これについてグラフをイメージすると8の字のような形の時に上手くいかなそうだなとか、閉路の位置によってはバグりそうだな、と漠然と思っていた。手は動かしていたもののそれらしい解答が実装できず解説を読むことにした。解説を読んで
詳細は間違っていたけれど、閉路の判定には通過済みノードを用いて再帰的に処理すれば良いというところは合っていた。また、不正解だった思考の時は閉路だとわかった時に再帰を打ち切ろうと思っていたけれど、木としてカウントをしなければ良いだけなので処理を続けてしまって良い。もし途中で打ち切ってしまったとしても、繋がっているのであれば後続のループで判定は可能なので気にしなくて良い。このあたり意識して実装を行いsubmitした。
解答（誤答）：Submission #20032525 - AtCoder Regular Contest 037
しかしこれは誤答だった。サンプルは全てACだったのでいまいちわからず、ググってみたらまさにというものがあった。
アルゴリズム - AtCoder ARC 37 バウムテスト ACできない理由がわからない｜teratail
探索で根を考慮できていなかった。グラフによっては1つのグラフを2つのグラフとみなすようになっていた。ということで根を考慮して再submit。
解答（これも誤答）：Submission #20033904 - AtCoder Regular Contest 037
実装のどこかミスってるんだと思う。当たり前だけど。最終的な解答
解説ブログや他のACの解答を見て修正を行った。シンプルになった。
解答：Submission #20036890 - AtCoder Regular Contest 037感想
これまでの探索では上下左右のノードにしか遷移しなかったが、今回は任意のノードに遷移できるという点が違いだと思う。上下左右の遷移の場合、通過したノードを通行禁止にしてしまえば無限ループせずに探索できるため、その思考に固執してしまったと思う。特に解説を読む前の思考で、ステータスで色分けをすると考えていたが、その色塗り対象はエッジだった。これは上下左右に遷移するグラフの考え方に近い。
任意のノードに遷移できるグラフだと回しているループのインデックスの前後でinvalidな状態を判定できないので、別途訪問状態を保持しておく必要がある。それが今回の実装だとvisited := make(map[int]bool)だ。このmapを使って訪問判定をする発想ができなかった。
まとめ
バウムテストは解説を読んでもなかなか解けなかった。周辺ノードではなく任意のノードに遷移できるグラフの閉路判定は別途訪問状態を保持しておく必要がある、という知識はしっかり憶えておいてすぐに頭から引き出して書けるようにした方が良いと思った。
今回解けなかった問題、時間がかかってしまった問題は来月あたりに再度解きたい。
ゼロからはじめるデータベース操作を読んだ
背景・モチベーション
いままでRDBにはあまり関わってこなかったため理解が浅い。DBとなるとKVSを触る機会の方が多かった。RDBが裏側にいたとしてもデータ部隊が別に存在しSQLを書いたりDBの設計に関わることはなかった。SQLを書くとしても、redashでデータを見る時程度で、しかもクエリはコピペで済ませてしまっていた。
さすがにやらないとまずいな、ということで昨年末にようやく読んだ。
現状の知識
以前にredashでクエリを作る時に、合計数を出すクエリが書けないことがあった。そこに別チームの同僚が通りすがり、「countも知らんの！？！？？！？！？！？？？！？！？？」と言われた。あの時の顔を思い出すと夜しか眠れない。
環境
テキトーにdockerイメージをpull。
$ docker pull postgresql $ docker run -e POSTGRES_PASSWORD=password postgresql $ docker exec -it $(containerのID) bash $ root@container_id> psql -U postgres
読んだ箇所のおおまかな内容
DBって何だ
これはさすがに理解していたので流し読み。DBMSにSQLのパーサーがいて、DBに対して実行し、結果をDBMS経由で返すという流れ。これ以上の深い理解はしていないけれど。
SQLって何だ
SQLに歴史ありという感じだった。SQLはISOで規格を定められた標準SQLというものがあり、普段目にしているSQLはこれだという。また、クエリの種類にもDDL（データ定義言語）・DML（データ操作言語）・DCL（データ制御言語）と分けることができる。それぞれ CREATE 、 SELECT 、 COMMIT などが該当する。詳しく調べるほどの興味が出なかったけど、トリビアとして面白かった。ここに興味が持てると、クエリを高度に抽象化した次元で理解できそう。たぶん。
本書ではクエリはキーワードを大文字、テーブル名を頭文字だけ大文字、あとは小文字としているが、スタイルは議論の余地があるらしい。 techlife.cookpad.com
基本的なCRUD
基本的なので見覚えはあるけど構文を雰囲気で記憶していたので改めて確認すると真新しい感覚になった。
DBの作成
create <DB名>;
テーブルの作成
create table <テーブル名> ( <カラム名> <データ型> <制約>, <カラム名> <データ型> <制約>, . . . <テーブルの制約1>, <テーブルの制約2>, ..., <テーブルの制約N> );
データ型と制約についてはうっすら理解していたけれど、それだとまた勉強することになりそうだったので公式のリファレンスを眺めた。
MySQL :: MySQL 5.6 リファレンスマニュアル :: 11 データ型
MySQL :: MySQL 5.6 リファレンスマニュアル :: 1.7.3 MySQL における制約の処理
定義の変更
alter table <テーブル名> add column <列名> <データ型> <制約>; alter table <テーブル名> drop column <列名>;
変更する際は新しいカラムをaddしてから古いカラムをdropする。
データの選択
select <列名>, ..., <列名N> from <テーブル名>; select distinct <列名>, ..., <列名N> from <テーブル名>;
distinctは複数列にも書けるが、その際は積がselectされる。
NULLの操作
NULLを含む演算をするとNULLになる。特別にIS NULLとIS NOT NULLが用意されている。
MySQL :: MySQL 5.6 リファレンスマニュアル :: 3.3.4.6 NULL 値の操作
MySQL :: MySQL 5.6 リファレンスマニュアル :: B.5.5.3 NULL 値に関する問題
MySQL :: MySQL 5.6 リファレンスマニュアル :: 8.2.1.8 IS NULL の最適化
NOT NULLのカラムに対してIS NULLを行うと最適化されるとリファレンスにあった。そもそもNOT NULLのカラムに対してIS NULLつけないだろと思ったけど、ORMとかで人間が組み立てない場合はロジック次第でそういうクエリは生まれそうだなと思った。
集約関数
count・sum・avg・max・minなど。集約関数はNULLを除外して行われるというのが意外。先ほどまでNULL値を含めた演算はNULLになるという理屈はどこへいったのやら。
特に気をつけたいのはavgだ。NULLが除外されるため、分母がNULLを除いた数になる。
集約関数ではないが、他にはgroup byやhaving、order byなど。これらの動作は理解していたけれど、いざ実際に自分で0から書いてみると割と難しい。集約関数と組み合わせて色んなことができる。
更新
insert・delete・drop・updateなど。これは大体雰囲気でわかっていたけれど、テーブルのコピーについて初見の知識があった。特定のテーブルを別のテーブルにコピーする際は下記のように書くことができる。
insert into dst (a, b, c) select a, b, c from src;
複雑な問い合わせ
VIEW
VIEWという存在を初めて知った。これは集合を返却する関数のようなもので、from句に続いてテーブルのように使うことができる。
ただし、あくまで関数のようなものなのでVIEWにデータは存在しない。VIEWが評価されるとVIEWの定義であるクエリが実行される。
スカラ・サブクエリ
サブクエリは知っていたが、スカラ・サブクエリという単語は初見だった。これはサブクエリの結果としてスカラ値を返却するものだ。where句では集約関数を使うことができないが、スカラ・サブクエリを利用することで使うことができる。
相関サブクエリ
理解できた気がするけど0から自分で組み立てる自信はないのできっと理解できていない。相関サブクエリはクエリとサブクエリの関係性を紐付けて実行するものだと理解している。
select shohin_bunrui, shohin_mei, hanbai_tanka from shohin as s1 where hanbai_tanka > ( select avg(hanbai_tanka) from shohin as s2 where s1.shohin_bunrui = s2.shohin_bunrui group by shohin_bunrui );
これにより各商品分類ごとに分類の平均を超えた商品を選び出すことができる。
集合演算
union・intersect・exceptがそれぞれ和・積・差に対応する。これらは同じカラムについてレコードが増減する操作だ。
一方、カラムが増減する結合方法がjoinだ。結合方法によってレコード数も変わることはあるけれど、テーブルを横にくっつけるイメージがある。
inner joinはあるテーブルとあるテーブルに共通するカラムを用いて、それをキーとしたレコードを作成する。外部キーを使った結合とかでイメージがしやすかった。outer joinはキーとしているカラムがテーブルで共通していなくても無理やりくっつけてしまう結合方法。3つ以上のテーブルの結合もfrom句に同じ記述を繰り返すことで実現可能である。
最後にcross joinがある。これはテーブル同士の直積をとる。なのでレコード数が膨大になる。実務でどう使うと嬉しいケースがあるのかさっぱりわからない。
MySQL :: MySQL 5.6 リファレンスマニュアル :: 13.2.9.2 JOIN 構文
InnoDBって何だ
MySQLのリファレンスを見ると、度々InnoDBという単語が出てくる。一体これは何なんだと思いググった。
つまりMySQLのストレージエンジンらしく、いまはオラクルの持ち物らしい。
InnoDB - Wikipedia
mysql-server/storage/innobase at 8.0 · mysql/mysql-server · GitHub
まとめ
何も知らなかったので何もかも新鮮だった。新卒研修でやったはずなんだけどな。
さすがにこのレベルは基礎の基礎なので、リファレンスしなくても書けるようにしたい。
サーバーサイドGo入門 #5 ~redisを使う~
前回はこちら prelude.hatenablog.jp
今回作るもの
redisを用いてReadのレスポンスを早めましょう。
ユーザーIDの追加
redisの導入にあたりまずユーザーIDをTODOに追加します。このユーザーIDをredisのキーとして用いTODOを保存します。
type TODO struct { gorm.Model // これ UserID int `json:"userID"` Author string `json:"author"` Name string `json:"name"` Description string `json:"description"` DueDate time.Time `json:"dueDate"` }
ユーザーIDの追加に伴い、TODO一覧APIをユーザーIDを指定して取得するものに変更しましょう。
func list(c *gin.Context) { userID := c.Param("user_id") todos := make([]TODO, 0) if err := gormDB.WithContext(c).Find(&todos, "user_id = ?", userID).Error; err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } c.JSON(http.StatusOK, todos) } func setupRouter() *gin.Engine { router := gin.Default() router.GET("/todos/:user_id", list) router.POST("/todo", add) return router }
redisの導入
redis clientの初期化
では早速redisを導入しましょう。使用するライブラリは下記です。import時にv8をつける必要があることに注意しましょう。
github.com
redisのクライアントもgorm同様にグローバルに定義し、main関数で初期化します。
// これと var redisClient *redis.Client func main() { _gormDB, err := gorm.Open(mysql.Open("root:mysql@tcp(127.0.0.1:3306)/todo?parseTime=true"), &gorm.Config{}) if err != nil { panic(err) } sqlDB, err := _gormDB.DB() if err != nil { panic(err) } defer sqlDB.Close() if !_gormDB.Migrator().HasTable(&TODO{}) { if err := _gormDB.Migrator().CreateTable(&TODO{}); err != nil { panic(err) } } gormDB = _gormDB // これ redisClient = redis.NewClient(&redis.Options{ Addr: "localhost:6379", Password: "", DB: 0, }) log.Println(setupRouter().Run(":8080")) }
このクライアントを用いるように修正します。
redisを使う
今回はredisを下記のように使います。
list：ユーザーIDをキーとしたデータがredisにあればそれを使用。なければDBから取得し、redisに保存。add：ユーザーIDをキーとしてredisに保存されているTODOを削除。
ちなみに、redisにsetする際に下記のinterfaceを要求されます。
type BinaryMarshaler interface { MarshalBinary() (data []byte, err error) }
encoding - The Go Programming Language
そのため、set前にjsonにencodingしている点に注意してください。実際のコードはこのようになります。
func list(c *gin.Context) { userID := c.Param("user_id") todos := make([]TODO, 0) if b, err := redisClient.Get(c, userID).Bytes(); err == nil { if err := json.Unmarshal(b, &todos); err == nil { c.JSON(http.StatusOK, todos) return } } if err := gormDB.WithContext(c).Find(&todos, "user_id = ?", userID).Error; err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } j, err := json.Marshal(todos) if err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } if err := redisClient.Set(c, userID, j, 5*time.Minute).Err(); err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } c.JSON(http.StatusOK, todos) } func add(c *gin.Context) { if c.Request.Body == http.NoBody { c.JSON(http.StatusBadRequest, gin.H{"error": "body is required"}) return } var todo TODO if err := json.NewDecoder(c.Request.Body).Decode(&todo); err != nil { c.JSON(http.StatusBadRequest, gin.H{"error": "body is invalid"}) return } if err := gormDB.WithContext(c).Create(&todo).Error; err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } if err := redisClient.Del(c, strconv.Itoa(todo.UserID)).Err(); err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } c.JSON(http.StatusOK, todo) }
redisを動かす
redisのイメージを取得し、動かします。
$ docker pull redis $ docker run --rm --name redis -p 6379:6379 redis redis-server --appendonly yes
curlで確認
下記の通りcurlを行い確認します。2度目のTODO一覧の取得時間が非常に短いこと、TODOを追加した後のTODO一覧の取得が1度目の取得と同じ程度に遅くなることを確認してください。
$ curl -X POST http://localhost:8080/todo -d \ '{"userID": 1, "author": "Rob", "name": "Develop Generics", "description": "Add feature of generic type system", "dueDate": "2022-12-31T00:00:00Z" }' | jq
$ curl http://locahost:8080/todos/1 | jq
コード全文
// main.go package main import ( "encoding/json" "log" "net/http" "strconv" "time" "github.com/gin-gonic/gin" "github.com/go-redis/redis/v8" "gorm.io/driver/mysql" "gorm.io/gorm" ) var gormDB *gorm.DB var redisClient *redis.Client type TODO struct { gorm.Model UserID int `json:"userID"` Author string `json:"author"` Name string `json:"name"` Description string `json:"description"` DueDate time.Time `json:"dueDate"` } func list(c *gin.Context) { userID := c.Param("user_id") todos := make([]TODO, 0) if b, err := redisClient.Get(c, userID).Bytes(); err == nil { if err := json.Unmarshal(b, &todos); err == nil { c.JSON(http.StatusOK, todos) return } } if err := gormDB.WithContext(c).Find(&todos, "user_id = ?", userID).Error; err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } j, err := json.Marshal(todos) if err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } if err := redisClient.Set(c, userID, j, 5*time.Minute).Err(); err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } c.JSON(http.StatusOK, todos) } func add(c *gin.Context) { if c.Request.Body == http.NoBody { c.JSON(http.StatusBadRequest, gin.H{"error": "body is required"}) return } var todo TODO if err := json.NewDecoder(c.Request.Body).Decode(&todo); err != nil { c.JSON(http.StatusBadRequest, gin.H{"error": "body is invalid"}) return } if err := gormDB.WithContext(c).Create(&todo).Error; err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } if err := redisClient.Del(c, strconv.Itoa(todo.UserID)).Err(); err != nil { c.JSON(http.StatusInternalServerError, gin.H{"error": err.Error()}) return } c.JSON(http.StatusOK, todo) } func setupRouter() *gin.Engine { router := gin.Default() router.GET("/todos/:user_id", list) router.POST("/todo", add) return router } func main() { _gormDB, err := gorm.Open(mysql.Open("root:mysql@tcp(127.0.0.1:3306)/todo?parseTime=true"), &gorm.Config{}) if err != nil { panic(err) } sqlDB, err := _gormDB.DB() if err != nil { panic(err) } defer sqlDB.Close() if !_gormDB.Migrator().HasTable(&TODO{}) { if err := _gormDB.Migrator().CreateTable(&TODO{}); err != nil { panic(err) } } gormDB = _gormDB redisClient = redis.NewClient(&redis.Options{ Addr: "localhost:6379", Password: "", DB: 0, }) log.Println(setupRouter().Run(":8080")) }
まとめ
現実のサーバーサイドの開発ではキャッシュは非常によく行われるものと思います。今回はredisを深く理解して使うことよりも、まずGoで扱ってみて最初の1歩のハードルを低くすることを目的としました。
redisを使いキャッシュしていますが今回のコードでは速くなりません。そもそも処理が少ないため、redisとのやり取りによるオーバーヘッドの方が高くつきます。
雑談
redisの後はgoroutineとgPRCの導入を書こうと思っていましたが失踪しそうです。
競技プログラミング in Go #1
背景
2年半くらい前に少しやって以来あまりできていない。たまに思い立ったように問題を解いたり蟻本を読んでみたりするものの、以前の内容を憶えておらず同じような内容を初見の顔をして勉強していることが多い。
まずはこの現状を打破して継続できるようにしたい。そもそもではあるが、最強最速アルゴリズマーになってアルゴリズムを仕事にするのは力量的にも難しいため、教養と知的好奇心と趣味としての競プロを楽しんで続けられるようにしていきたい。
なんで続かなかったんだろう...
自分なりに考えてみると、理由がいくつかありそうだ。
まず、C++を使っていた。私はC++を普段仕事や趣味で使っていなかった*1。使っていた理由は、競プロの解説や解答例でC++が使われることが多いからだ。けれど、時間を置くとすぐにわからなくなり毎回調べていた。問題を解くということに集中するためにはC++は扱う技量が足りていなかった。
また、競プロの優先順位をなかなか上げられなかった。他にも知らなきゃいけないことが多かったのだ。仕事で活かせる機会が少ない*2競プロに大きく時間を割くことができなかった。
継続のために
まず言語はGoにしようかなと思っている。Goは個人的に触っており、コーディングテストでも毎回選択している*3。そのため、Goで競プロに慣れておくメリットは大きいかなと思っている。Rustを使うことも検討したけれど、業務で使う可能性を考えるとRustよりもGoの方が高いかなぁ、と思う。まだまだ求人少ないし。
また、何を考えてどう解き、解説に何が書いてあるのか、そして時間を置いてもう一度解く必要があるのか、という当たり前のことができていなかった。理解より解くことが目的化していたからこそ中途半端になっていた。ここの思考を記録して整理しておく必要性を感じた*4。管理内容は後述する。
競プロにおけるGo
微妙らしい。
これ理由はけっこう簡単で、いくつか問題解いてみると分かるんだけど、強い型付けなのがかなり辛くって、キャストとかを超明示的に書かないといけない部分が多すぎるんだよね。実装速度がとにかく出ない。
— chokudai(高橋 直大)🍆 (@chokudai) March 7, 2017
go言語競プロだと厳しいって言ったけどtouristならtargetキープできる程度には使えると思うし、コンテストで競い合う向きじゃないけど、それがメインウェポンだと楽しめないってほどではない、くらいの印象。
— chokudai(高橋 直大)🍆 (@chokudai) March 7, 2017
これはたしかにそうで鬱陶しさや足りない機能が目立ってしまう。
例えば、未使用変数がワーニングじゃなくてエラーになるとか、タプルがないこととか、min/maxの関数がないとか。探せばたくさんある。
精選10問
なんやかんやあるけれど、とりあえず解いていこう。
思い立った時に毎回お世話になっている気がするが、drkenさんの記事を参考に解いていく。
今回はこれをGoで解いた。
Placing Marbles
Submission #19666903 - AtCoder Beginner Contest 081
Card Game for Two
Submission #19669348 - AtCoder Beginner Contest 088
Kagami Mochi
Submission #19669660 - AtCoder Beginner Contest 085
学び
知っていると思っていたようなことも競プロをやると厳密な理解を求められるのでよりクリアになった。
- breakで抜けるスコープは1つなので大域脱出したいならラベルを使う
- 数値のstringをループで回してruneを操作する場合、内部では文字コードになってしまうが、
'0'を引くことで数値を得られる sort.Xxxに渡す関数であるfunc (i, j int) boolのiとjはインデックスのため、比較を行う場合はfunc (i, j int) bool { v[i] > v[j] }のように書く- Goの配列のインデックスに負数は不可（Pythonとは違う）
管理方法
前述した思考の記録は、神ツールであるNotionを使っている。聖書や古事記などまだ印刷技術がなかった時代に書かれたもの大半はNotionで進捗管理されていたと言われている。そのくらい強力なツールだ。
こんな感じで復習できるようにまとめつつ思考過程と解説を載せている。初めはScrapboxで関連問題が表示されるようにしていたけれど、Notionの使い勝手の良さに負けてしまった。まだまだ改善の余地がありそうなので、もっと上手く管理したい。
結び
失踪せずに#2を書きたい。次回は蟻本の全探索の部分和問題とLake Counting問題の類題を解いていく。
コンテストは出れる時に出る。寝たい。
Go言語による並行処理を読んだ
結構前に下記の本を読んだ。メモをしていたのでここにも残しておこうと思う。
- 作者:Katherine Cox-Buday
- 発売日: 2018/10/26
- メディア: 単行本（ソフトカバー）
前提知識
今までgoroutineを使うことはあってもいくつか作ってsync.WaitGroupで待つ、くらいのことしかしていなかった。
なぜなら、どう動くのか/いかに動かすのかの理解がなく単純なことしかやらせていなかったからだ。
本書を読んで、こ慣れた扱いも少しはできるようになったかなと思う。よかったよかった。
へーってなったところ
syncを使う？channelを使う？
goroutineを使う時にsyncパッケージを使うのか、channelを使うのか、というのは悩みどころだと思う。事実、私はよく悩んでいた。どちらでもやりたいことはできるけど使い分ける基準があるのだろうか、とgoroutineを書くときはいつもモヤモヤしていた。
本書以前にsyncパッケージのドキュメントには下記のようにある。
syncパッケージでは排他制御といった基本的な同期のためのプリミティブを提供します。Once型とWaitGroup型以外は、低水準ライブラリ内で利用されることを想定しています。高水準の同期はチャネルや通信によって行われたほうが良いでしょう。
また、公式FAQには下記のようにある。
ミューテックスに関して言えば、syncパッケージがそれを実装していますが、Goのプログラミングスタイルでは、高水準の技術を使うことを推奨しています。特に、プログラムを書く際にはある瞬間にただ1つのゴルーチンがある特定のデータの責任を持つように心がけてください。メモリを共有することで通信してはいけません。かわりに、通信することでメモリを共有しましょう。
高水準の同期とは何だろうか。
本書ではこれらsyncパッケージとchannelのどちらを使うのか、という決定木が載っている。これが非常にわかりやすい。内容は並行処理のスコープが特に意識されていると感じた。
ちなみに公式wikiに使い分けについて言及がある。
MutexOrChannel · golang/go Wiki · GitHub
他の並行処理に関する公式資料は過去記事でまとめた。
実装パターン
goroutine雰囲気erなので、並行処理でどう実装するのか手札をあまり持っていなかった。本書は並行処理パターンという章で色んな実装パターンの実例を読むことができる。selectの使い方やchannelを上手く使うことで孫goroutineを扱ったり。さらにpipelineやfan-in/fan-outなどのロジックは単純な機能を組み立てて複雑なことまで表現することのできるGoらしさを強く感じた。
chanの仕様についても理解することができる。例えばchanがnilや空の時の挙動であったり、キューとしてどう振る舞っているのかなど。chanを深く理解していなかったが、本書を読んでからはchanを使った他人の実装も読めるようになった気がする。
「並行処理をバリバリ書かないから実装パターンを手札として増やしても仕方がない」と思うこともあったが、実装パターンを多く読むことで並行処理をGoでどう使い使われるのかの想像力がかなり豊かになる点はすごく良かったと思う。さっきも書いたけど他人の書いた並行処理が読めるとレビューもしやすくなるし、ライブラリもどんどん読める。
応用
エラー伝播やハートビート、流量制限は、若干難しかった。
しかし、実際の開発を前提に置いて話が展開されるため、イメージはしやすかった。
まだまだ読み込みの浅さを感じているので、このあたりはまたいつか読み直したい。
わからなくて調べたこと
CSP
並行処理一般の理論で追いつけないところがあった。なんとなく言いたいことはわかるけれど雲を掴むような気持ちで読んでいた。
GoはCSP（Communicating Sequential Process）という理論を土台？としている。CSPはプロセスが通信によってコミュニケーションをする、というものでGoの「共有ではなく通信によりメモリを共有する」という思想の基になっている話だ（たぶん）。公式ドキュメントにCSPを土台にした背景が少し書いてある。
わからなかった理由として、アクターモデルとの分別がついていないことがある。アクターモデルもアクター同士がメッセージを相互に送ってコミュニケーションするのでは？といまだに腑に落ちていない。
アクターモデルの理解がそもそも浅いため、いまの自分には手に負えないものだった。
アクターモデルのwikiにCSPに言及している部分もあったけど、いまいちわからなかった。
ただ、本書にも記載があるがGoは並行処理の複雑さに言語仕様から立ち向かってくれたおかげで、我々は簡単にコードを書くことができている。CSPの理解を深めることでGoの並行処理がより上手に書くことができることは本書が示していると思う。
今後何か意識したいところ
syncとchannelの使い分け。- パターンに依拠した実装
- goroutineを使わない選択肢を思考すること
まずは並行処理のスコープを狭くしつつ、基本に忠実に書くこと。そしてその上でパターンを使ってgoroutineの力を引き出すように書くことが求められると思う。これが逆転するとせっかく複雑さを回避しようとしているのに、スコープの広いchanに悩まされることだろう。
また、goroutineに固執せず、使わなくて良いなら使わない。goroutineは非常に大きな力だけれども、並行処理は使わない方が単純明快だ。しっかりと検証した上で必要になったら使いたい。本書で知ったことを使いたくなってもグッと堪えるのは大事だろう。
