Atcoder初心者が成績アップに繋がったと感じた考え方の工夫
こんにちは。
id:shallow1729です！この記事ははてなエンジニア Advent Calendar 2020の7日目の記事です。
昨日は
id:stefafafanさんで「iTerm2の機能を使いこなして日頃の作業の効率をあげたい2020」でした！
iTerm2僕も使ってるはずなんですけど知らない機能がいっぱいでした。
はじめに
この記事は半年ほど前から参加していたAtcoderというプログラミングコンテストを振り返って、特に成績アップに繋がった問題を解く時の思考方法の工夫について書いたものです。まだ始めて4ヶ月ほどで十分に参加できていないのでまだ茶色ですが、ここ三回はパフォーマンスが一気に上がって、Atcoder Begineer Contest(以下ABC)の問題ならD問題までは安定して解けるようになってきましたし、E問題も方針はうまく選べるようになってきました。まだまだ初心者ですが、工夫が成長に繋がった事がすごく嬉しかったので試した事をいろいろ書いてみようと思います。なお、この記事ではABC181からABC184の問題のネタバレも入っているのでそういうのが嫌な人はブラウザバックしてもらえたらと思います。
アルゴリズムの勉強
メインの考え方の話の前にアルゴリズムの知識に関する話から入ります。プログラミングコンテストに参加するとなるとアルゴリズムの知識が結構いると思っていたのですが、少なくとも僕が参加していたABCのD問題ぐらいまでだと、自分の実装の計算量を見積もるなどの基本的なアルゴリズムの解析やメモ化を使った高速化はできる必要がありますが、名前のあるアルゴリズムの実装についての知識はそれほど多くは求められていないような印象です。計算量の見積もりが重要な理由は、コンテストの制限時間は結構短いので、明らかに間に合わなそうな実装の時はパフォーマンス改善を考えたり、逆に不必要にパフォーマンスチューニングをして実装コストを増やさないなどの判断を素早くできる必要があるからです。経験上はO()あたりがギリギリ間に合うか間に合わないかという感覚なのでそういうイメージで設計をすると良い気がします。ただ、もう少しテクニカルなアルゴリズムの知識についていうと、スタックやキュー、グラフの全探索あたりは頻繁に出てくるので実装に慣れておく必要があるかなと思います。あと、場合の数を求める問題などで出てくるでかい素数で割った余りを答えよみたいな奴対策でmod計算用のライブラリは事前に用意しておいたほうがいいと思います。modの計算というのはこちらで紹介されているようなやつです。
drken1215.hatenablog.com これだけは持っておかないと方針があってる回答でもTLEになってしまったりするので。。。
E問題になると整数問題で使うアルゴリズムや二分探索、Union-Find Treeなど、もう少しアルゴリズムの知識を必要とする問題も出てくる印象なので勉強はやっとくに越した事は無いと思います。ただ、知識があるのと実際に知識を使えるようになる事の間は結構あると感じているので、知識があれば問題が解けるかというとそうでは無いと思います。
数学的な問題解決の思考方法
今回メインで書きたかったのは数学の問題を解く時によくやるような試行錯誤のテクニックです。数学の勉強ってもちろん覚えないといけないことがたくさんありますけど、大事なのはそれをうまく使って問題を解くところというのは受験などを経験した人は分かるんじゃないかなと思います。そこの能力って才能として見られがちですが、案外訓練で改善できるものだと思っています。実際数学の問題解決の方法についてはいくつか本があって、有名な本だとG.Polyaの「いかにして問題をとくか」があると思います。今回はそういう試行錯誤の技術について、実際の問題を解いた時の思考の流れと一緒に説明できたらなと思います。
実験する
見慣れない問題や方針に困る問題を見たらとりあえず手を動かしてみましょう。いくつか試してみるとアイデアが思いつく事があると思います。
なんか難しそうな問題ですね。難しそうな問題はとりあえず手を動かしてみましょう。(0, 0)から(100, 0)だと(0, 0)->(50, 50)->(100, 0)で二手、(0, 0)から(101, 0)だと(0, 0)->(50, 50)->(100, 0)->(101, 0)で三手になりそうです。じゃあ(0, 0)から(105, 0)なら四手になるかというとそうはならなくて(0, 0)->(52, 52)->(104, 0)->(105, 0)で三手になってしまいます。こんな感じで実験をすると最大でも三手でクリアできると分かってくるんじゃないかなと思います。あとは一手か二手か三手かを判定する方法を考えるという形になります。(この場合分け難しかったんですよね。。。今後の反省点です。。。)
全ての都市間について移動ができるようなグラフの問題に見えます。グラフの問題として全探索を行っても解けるかなと思いますが、実際に経路を並べてみるともっと単純なパターンが見えてきます。4都市の場合は例にあるように
- 1->2->3->4->1
- 1->2->4->3->1
- 1->3->2->4->1
- 1->3->4->2->1
- 1->4->2->3->1
- 1->4->3->2->1
というパターンがあります。1を除くと2, 3, 4については単純に順列の全列挙になっている事がわかります。順列の全列挙はPythonだとitertoolsで用意されているのでそれを使ってしまえば良いという感じです。これを紹介した理由として、実験する時は元の問題の文章に引っ張られずにフラットに見ると良いよと伝えたかったからでした。もちろん問題文から得られるイメージは解決に役立つ事もありますが、変にバイアスになって重要な性質を見落としたりする事もあるので要注意です。
逆から考える
問題の道筋が見えない時はゴールから逆算するという戦略が有効です。
この問題は各人iについてから
までの間
リットル水を使おうとした時に使おうとする水の量がWを超える瞬間があるか？という事に答える問題です。NとTが 最大で
なので単純に時刻ごとに全件を足してると間に合わなさそうです。この問題に答えるために各時刻で使われる水の量の総和さえあれば良さそうです。ある時刻に使われる水の量の総和は「その一つ前の時刻に使われている水の量」+「その時刻に使い始める水の量」-「その時刻に使うのをやめる水の量」で求められます。つまり、この問題を解くためにはこれらの情報を準備すればいい事がわかります。「その時刻に使い始める水の量」は時刻
の関数として
で初期化の時に計算できる。「その時刻に使うのをやめる水の量」についても同様ですね。「一つ前の時刻に使われている水の量」は初期値0で時間発展の中で都度計算されるものなので特別な準備は不要です。このようにすると計算時間が間に合うようになります。大事なのは問題を解くのに必要なデータ構造を先に考えて、それをもらった入力から作れるか？と考えた点です。ゴールから考えた事で実装までの流れが見えやすくなりました。
簡略化した問題を考える
複雑な問題をそのまま解くのではなくて、それをもう少し簡単な問題にした時に解けるかを考えてそこから考えるという奴です。
atcoder.jp 例えばこの問題はN人の児童と身長の変わる一人の先生でペアの身長差が最小になるような組み合わせを作るという問題です。この問題だと「先生の身長が変わる」というのは明らかに問題を難しくしています。なので、いったん先生の身長は変わらないと仮定して自由度の少し減った問題を考えます。そうすると小学校でよくやるように背の順で並んでペアを組むという戦略が多分思いつきやすくなると思います。N人の児童を背の順にソートして隣同士をペアにすればいいという基本方針が思いついた段階で、先生の身長が変わるという条件を持ってきます。この問題は先生の身長のパターンを全て試した中でペアの身長差が最小の答えを求めればいいとわかりますね。この問題を解くために考える必要がある事は二つで、一つは先生の身長が決まった場合にペアを決めるという事、もう一つはペアが決まった時に合計をどのように求めたらいいかという問題があります。前者についてはソートされた配列の中での自分の場所を決める問題なので二分探索が使えそうです。後者のペアが決まった時に合計をどのように求めたらいいかについてですが、児童のペアの作り方は先生とペアになるか、前の人とペアになるか、後ろの人とペアになるかになります。例えばもともと前の児童とペアになっていた児童の間に先生が割り込んできた場合、その児童は後ろの児童とペアを組むことになります。同様にそこから後ろの児童は全員ペアが前の人から後ろの人に変わります。なので、ペアの身長差の総和は先生より前のペアについての総和と先生と児童のペアの身長差と先生と児童のペアから後ろのペアの身長差の総和の三つで計算できるようになります。先生と児童のペア以外は事前に前のペアと組む場合と後ろのペアと組む場合について累積和を作っておけば定数時間で総和を計算できますね。難しい問題に見えますがステップを分割して一つ一つの段階をよく考えればきっと解けるんじゃないかなと思います。
最後に
というわけで今回は僕が成績アップに繋がったと感じたプログラミングコンテストの問題を解くための考え方の工夫をまとめてみました。一番伝えたかったのは数学の問題を解くイメージでプログラミングの問題を解くと筋道を立てやすいよというところです。プログラミングと数学の関連はよく強調される一方で個人的にはなかなか実感を持てなかったのですが、今回試行錯誤をする中でなんとなく分かってきたような気がします。とはいえ僕もまだまだ解けない問題多いので、もっと試行錯誤して今後もプログラミングコンテスト楽しめたらなと思います。
明日は
id:kouki_danさんです！よろしくお願いします！！
AtCoder Beginner Contest 175に参加しました！ + 最近やってたこと
タイトルの通り先週末はAtCoder Beginner Contest 175に参加しましたー。
ABCの三問しか解けなくて悔しかったけどパフォーマンスは1119なので緑ぐらいのパフォーマンスにはなりました！
C問題を開始20分で解けて気分良くD問題に行けたのですが、結局Dをうまく通せずに終わってしまいました。
atcoder.jp D問題、Kの範囲に対してNがむっちゃ小さい+飛び先が自分自身でない事から循環しうる事がまず分かって、一周した時に0より大きいかで場合分けが必要なのもなんとなく分かってパフォーマンス的にもO(N2)程度で済みそうやしいけるかなと思ったものの、これ結構大変じゃない？？ってなって解くのにひよってしまいました。Dなんだからもっと簡単なのあるでしょ？とか思って20分ぐらい悩んでも思いつかないから諦めて循環見つけようってなりました。多分一般には循環は深さ優先探索で見つけるんだと思うんですけど、グラフアルゴリズムはまだあまり勉強してない状態だったのでこの前趣味で書いたFloydのうさぎとかめのアルゴリズムを使いました。 Floydのうさぎとかめのアルゴリズムは動画でたまたま知って面白かったのでその時に実装しました。
でも今思うと循環を難しく考えすぎですね。
今回の場合なら循環の開始地点と開始地点は一致すると考えていいので、単に開始地点をメモって、開始地点に戻ってくるまでfor文を回すだけで十分ですね。
で、一周させた時にスコアが0より大きいなら何周もさせればどんどん大きいスコアにする事ができます。一方で0より小さいなら何周もさせる意味は無いので一周させる中でベストの値を返せば良いです。ここまでは制限時間内に思いついてそこそこ通るものができたのですが、いくつか通らないまま終わってしまいました。何で引っかかっていたかというと一周のスコアが0より大きい場合に先に周れるだけ周ってからあまりを足してたんですけど、それが良くなかったんですよね。
4 40 3 1 4 2 1000 2000 4000 -6000
↑みたいな入力の時って10周させるよりも9周して残りいい感じのところでやめた方がいいスコアになるんですよね。なので周るだけ周ってからあまりを進むのではなく、一周回るまでの範囲で連続する長さをいろいろとって、残りの値で周れるだけ回った中で一番いいスコアをとるのが実際はいい戦略になります。こういうの結構教育的ですね。端数をあまり雑に扱うと痛い目をみるんだなーって思ったので次からの教訓にします。Eからは見てないです。正確にはEはチラ見してそっ閉じしました。問題にはなんか見覚えあると思いつつ全然分からなかったので諦めました。
前のABC174から二週間あって、その間はほとんどCとDの問題を解いていました。全探索とか合同式を使う問題をパッと解けたいなーと思ってその辺を勉強していました。2値の全探索ならbit演算でシュッとかけると思うんですけど3値以上のめんどくさいやつの時の実装がなんかうまく書けないなーってなってました。一回アドリブで再帰を使って実装したんですけど、こちらの記事にきれいにまとまってるように考えて書くとすごくいい感じになりました。
あとは「アルゴリズムイントロダクション」とか「離散数学への招待」みたいな本を読んでました。まだちゃんと勉強できてないんですけどマトロイドとかいうやつむっちゃかっこよくないですか！？凸関数の一般化みたいな感じっぽいですね。凸関数、最適化がスムーズにいくのがイメージつくと思うんですけどそれをもっと抽象化する事で貪欲法が使えるかを判断できるって感じですよね。ちょーかっこいい！！なんか面白そうだからちゃんと勉強したいですね！！
あとはなんか急にどうやってグラフって描画されるんだろう？ってのが気になってコンピューターグラフィクスのラスタライズのアルゴリズムを調べたりしてました。アルゴリズムの勉強、なんか自分の肌に合ってる気がしているのでもっと深くやっていきたいです。
AtCorderに初めて参加した！！
あんまり人に読ませる文章ではないです。
感想: 楽しかった！！！
前職はプログラミングコンテストが盛んな会社だった。黄色とか大会での優勝経験がある人とかが何人もいて、みんなすごいなーと思いつつ、自分の仕事はアルゴリズムがそれほど陽に出てこなかったし、しかも非情報系から未経験でエンジニアになった事もあって他に勉強する事が山ほどあったからちょっと遠くから見ている感じになっていた。あと、正直アルゴリズムを学ぶという事の意味がよく分からなかったというのもある。アルゴリズムを見てるとよく思いつくなーと思いつつ自分が思いつけるだろうか？みたいな悩みがあった。僕は物理学がすごく好きで、なぜかというと運動方程式やマクスウェル方程式みたいな少数の知識だけで多くの問題を解けるからだ。それはシンプルで綺麗という個人的な美的感覚にあってたのもあるし、記憶力や発想力がそれほど無くてもできるから自分に合っていたというのもある。それに比べるとアルゴリズムはなんとなく場当たり的な発想のように見える部分が多かった。結局最初に勉強した時はソートアルゴリズムとかグラフアルゴリズムみたいなのの教科書的な話に一通り目を通して終わってしまった。
アルゴリズムに興味を持ったきっかけは数年前に買って以来ずっと本棚に眠っていた「アルゴリズムイントロダクション」を一ヶ月ほど前に読んだ時だった。分割統治法の説明の中で出てきたマスター法による計算時間の見積もりのところがすごく面白かった。それまで分割統治法が使えるかをケースバイケースでやっていたのが、ある程度一般化された数学で考えられる事を知った。あとは動的計画法や貪欲法が適用できるかに関する考察も面白かった。こういう知識をうまく自分の中で整理できたら自分でもアルゴリズムを設計できるかなって思って、なのでアルゴリズム設計の指針についていろいろ仮説を立てて、どういう手法を使えば良いか分からない実際の問題で試して仮説を検証してみたいなと思った。
そういう訳でAtCoderの問題を挑戦しようという感じで「AtCoder Beginner Contest 174」に挑戦してみた。一応過去問をいくつかは解いてて、D~Fで一問解けるかなぐらいにはなってきたので４問答えるのを目標にした。結果としてはABDの三問解けた。C難しかった...Eは解けるようになりたいなー...
Aはまあプログラミング慣れてる人ならすぐだと思う。Bは分子シミュレーションの研究していた頃に100億回ぐらい書いたので一瞬だった。Cはなんていうか、整数から逃げ続けたツケという感じがする。試験中に鳩の巣原理で2と5が無ければ11111...はKで割れるのを証明できるのを知ってすげーって思ったけどデカい数字を割るのが良くなくてTLEになってしまった。最近だとmodは高校で習うんだろうか？数学オリンピックとかだと普通に出てくるから国際的には習うもんなのかな？僕は結局大学含めて出会う事なく学生時代を終えてしまいました。次は間違えないようにする。Dはなんか実験してこれで行けそうかなって感じでやったら行けた。解けたのはいいけどなんか思いつきに頼ってしまった感じで良くない...。Eは簡単そうに見えて全然思いつかなかった。解説読んで二分探索なるほどねーってなった。なんかうまく考え方の中に組み込めそうな気がするからあとでしっかりめに考察する。Fはなんかこの前セグメント木作ったからそのまま使えそうならやってみるかという感じだったけどなんかうまくできなかった。慣れない事するもんじゃない。解説眺めた感じセグメント木ですらなさそう。
という事で初挑戦は700点でした。難しかったけどやっぱこういうのは勉強した事をゲーム感覚で試せていいなって思った。次は４問解きたい。
契約による設計とテスト駆動開発で大きいタスクを楽にする
こんにちは。id:shallow1729です。先日一ヶ月ぐらいの工数のかかる大きめのタスクを担当しました。そのタスクは機能に関連するテーブルやエラーになる条件が多く、初めはどこから手をつけたらいいか分からない状態でした。今回紹介する契約による設計とテスト駆動開発は自分がうまくとっかかりを見つけて手を進める上ですごく役に立った開発手法です。うまく実装を進められない時とかに思い出してもらえたらと思います。
大きいタスクの難しさ
これはエンジニアとしての経験則ですが、規模の大きい機能の開発はたとえそこにアルゴリズム的な困難さを伴わなくても難しいものになるように思います。
もちろん全体のアーキテクチャを考えるには設計手法の理解が必要ですし、関連するツールが増えるとそれらの理解が必要だったりするので技術的な課題に直面しやすいというのも事実だと思いますが、実際に開発をしている中でそういう技術的な課題感が特に無いのに手が動かなくなる場面がいくつかありました。初めは原因がよく分からなかったのですが自己分析してみて以下のような問題があるように感じました。
- 考慮する事の多さに対する疲弊
- 動作確認がなかなかできなくて不安になる
1つめの問題はタスクが大きくなるとそれだけ関連するものが増えるために起きる問題に思われます。ユーザーのデータの状態や入力フォームによって動作が変わる機能の場合、それらの状態や入力の数だけ条件分岐が発生することになります。僕が先日関わった仕事は6個のテーブルに更新が走る処理で、入力フォームやそれらのテーブルの状態によってはユーザーに適切なエラーメッセージを伝える必要がありました。このような実装では例えアルゴリズム的にはシンプルでも考える事が多いので神経を使って実装する必要があります。
2つめの問題はタスクが大きくなると動作確認ができるまでの期間が長いために起きる問題に思われます。普段僕は手元環境を立ち上げて実際に動作確認をしながら実装を進めているのですが、このようなやり方はある程度すでに存在するシステムの拡張をする時にできる方法で、大きな機能開発の場合はコードを書き始めてから実際に手元環境で動作確認できるようになるまでに数日かかってしまう事もあるので使えないケースがあります。こうなると数日間動作確認をせずにコードを書く事になるので感覚的には数日間仕事が進んでないような気持ちがして気分が沈みますし、実際に動かしてみて初めてうまくいってない事が分かって大きくやり直す可能性も見えて不安になります。
ここで書いた課題はどちらかというと心理的な課題に思うのですが、今回僕はこれらの精神的な負担を下げるために契約による設計を用いたモジュール設計手法とテスト駆動開発を実践してみました。今回の実践の流れとしては最初に契約による設計を使って全体について擬似コードを書いて、そのあとモジュールごとに擬似コードをベースに自動テストを実装しながらプロダクトのコードを書くという流れで行いました。こうなった経緯としては初めは擬似コードがあれば実装が進むかなと思ったら思ったより手が動かなかったのでテスト駆動も取り入れたという感じです。実際は擬似コードを書かずに事前条件や事後条件の洗い出しだけしてさっさとテストを書いていく方がいいかもしれないとも思いました。なので、まだまだ工夫中ですが、参考になれば幸いです。
契約による設計について
契約による設計(Design By Contract)というのはBertrand Meyerが考案した開発手法で、コードの品質、特にモジュールの信頼性を高める事で再利用性や利便性を高める事ができ、かつオブジェクト指向で用いる抽象化と非常に相性の良い開発手法です。契約による設計は名前の通りモジュールの呼び出し元と呼び出し先の間で契約を結ぶようなイメージで説明できます。まず、モジュールが呼び出された時、呼び出されたモジュールはその呼び出しに対して適切に処理を行えるかの確認を行います。このバリデーションは事前条件(precondition)と呼ばれます。契約による設計では事前条件を満たさない入力は受け付けない一方で、事前条件を通過した場合に呼び出し先は予定されている処理を実行し、必ず期待されている条件を満たす実行結果を返すように実装します。この期待されている条件というのは事後条件(postcondition)と呼ばれます。たとえ呼び出し先のモジュールで例外が発生しなくても事後条件を満たさない出力である場合はその出力を返さずに何らかの処理をする必要があります。また、もう一つ不変条件(class invaliant)というのがあって、これは例えば木構造のクラスでノードAの子ノードの親ノードはノードAでないといけない、というような常に成り立つ必要のある条件に関する制約です。これは例えば複数のデータ操作を伴う処理が中途半端な段階で失敗した時にデータ不整合を防ぐチェックと考えるといいかなと思います。
また、今回の本筋ではありませんが契約による設計は特に抽象化を伴う場合にはLiskovの置換原則を成立させるためのいくつかの条件を表現する事ができます。Liskovの置換原則というのは筋の良い抽象化を行うための数学的な表現で、よくSOLID原則の一つとして紹介されると思います。 例えば抽象化を行った場合のモジュールの事前条件と事後条件の規則を説明すると、抽象化を行う場合、子モジュールは親モジュール以上の値域の入力を受け取れるように設計する必要がありますし、親モジュール以下の値域で値を返さなければ置換不可能な設計になってしまいます。この契約による設計を用いた指針は元々の数学的な表現よりも実装に近くて扱いやすいと思いますし、単に置換可能な設計と言われてるよりも実装のイメージが付きやすくてよいなというのが個人的な感想です。
契約による設計を用いた擬似コード
例えばサインアップのフォームの入力を受け取って確認メールを飛ばすメソッドだとこんな感じかなと思います。
method_name
input: // 入力
user_account: user_account // 変数名と変数の型
email_address: string
password: string
data1: bool
db: db
output: // 戻り値
error_code
pre_condition: // 事前条件
// メールアドレスの形式が使用可能なものか
email_address_is_valid_format(email) == true
error_handle: return 'ERROR_CODE1'
// パスワードの形式が使用可能なものか
password_is_valid_format(password) == true
error_handle: return 'ERROR_CODE2'
// メールアドレスがすでに使われているか？
user_account.exists(email_address => email_address) == false
error_handle: return 'ERROR_CODE3'
post_condition: // 事後条件
// 一時的な登録データの作成は行われているか
temporary_data.exists == true
error_handle: exit
// 確認メールは送信されたか
email.sent == true
error_handle:
count = 0
while (count<5){
retry
count++
}
exit
code: // メインのロジック
// 一時データを登録して確認メールを送信する
token = create_temporary_data(user_account, email_address, password, data1, db)
email = create_confirm_email(token)
send_email(email_address, email)
擬似コードなので文法についてはご了承ください。ポイントはpre_conditionとpost_conditionでこのメソッドの事前条件と事後条件がどのようなものかと、それらのバリデーションに引っかかった場合にどうハンドリングするかを書いています。エラーを返したりプログラムを終了するだけではなく例えばメール送信や画像アップロードなど外部APIを叩く場合はリトライを試すという処理もここに書きます。
契約による設計の枠組みで考えて設計をしてみると分かるのですが、想定内の入力以外を初めに排除する事で入力の多様性について悩む問題が減るのでかなり見通しがよくなります。また、エラーハンドリングや失敗時の処理というあまり楽しくないけど設計能力が問われる仕組みについてもメインのロジックと分離して考える事ができるので筋道が立ちやすくなり、考慮漏れを事前に防げそうだな感じました。この擬似コードはメインのロジックがシンプルなので気になりませんが、複雑な実装の場合はメインのロジックを書きながらエラーハンドリングも書いていくと思考のノイズになりがちな気がするので、そういう例外をメインのロジックから分離して正常系の複雑な部分に集中できて良かったなと思いました。このように契約による設計を用いる事でメインのロジックとそれ以外の処理を分離して考える事ができるので「考慮する事の多さに対する疲弊」を抑える事ができました。ただ、多くの言語で事前条件や事後条件のバリデーションはサポートされていないので、実装時に工夫する必要があります。事前条件についてはunless文を最初にまとめて書けば良いかなと思いますが、事後条件についてはあまりうまく分離ができず、処理を進める中で適宜バリデーションと例外処理を書くしかないなと思いました。とはいえ事後条件については自明なケースも多いと思うので実際はバリデーションしないとかもあるかなと思います。
テスト駆動開発の心理的効用
テスト駆動開発といっても正直僕がやったのはとりあえずテストを先に書いてから実装するというだけの事なので、あまりテクニックの紹介はできません。ですが、それでも先ほど説明した実装時の心理的障壁を解消するには十分な効果があると感じたので紹介します。
まずテストが通る事で仕事が進んでいる事がわかるという安心感があります。しかも契約による設計で例外ケースやエッジケースがはっきりしているのでテストケースはあまり悩む必要がなく、実装もとりあえずバリデーションの実装だけ先に書こうとなるのであっというまに5個ぐらいのテストケースを通るところまで実装できて気分が良いです。また、デグレーションのリスクにかなり強くなるので書いてて気になったら安心してリファクタを行う事ができるのも良かったです。
テスト駆動開発をやる時に心がけるといいなと思ったのは人に見せるテストとはある程度分けて考えるという事です。多くのチームではプルリク作成時にプロダクトのコードと合わせてユニットテストも書く規約にしていると思うのですが、テスト駆動開発を始める時はそういう最終的に納品するコードとは分けて考えた方が良いと思います。例えばあるモジュールに対するテストはだいたいどのテストケースでも同じような初期化が必要だと思います。こういう時に初期化部分を共通化しておこうとか綺麗な設計にしようとかそういう事を初めから意識するとなかなか手が動かなくなる気がします。初めはコピペしながらテストケースをどんどん用意するぐらいのゆるい気持ちで進めて、適宜綺麗にしていくぐらいでいいかなと思います。
終わりに
今回は大きな開発に伴う心理的な負担を和らげる方法という文脈で契約による設計やテスト駆動開発といった開発手法を紹介しました。一方でこれらの手法が筋の良い設計につながるという話題は特にしなかったので興味のある方はいろいろ参考文献を見てみたりしてください。正直開発手法は人間的な側面を無視できないのでこれがベストと言い切れるような指標もなくて議論が難しいなと思うのですが、こういう開発手法を個人レベルで始めるのは自由だと思うので自分なりにいろいろ学んで試してみると開発が楽しくなっていいんじゃないかなと思います。
参考文献
契約による設計については以下の本が参考になるかもです。
https://www.amazon.co.jp/dp/4798111112
自動テストやテスト駆動開発については自分も勉強中ですがこの辺を読み進めています。
異なるシステム間での大量データの同期について
2022/03/19 追記
続編みたいなやつ書きました。 shallow1729.hatenablog.com
はじめに
メリークリスマス!!
はてなのエンジニアのid:shallow1729です。この記事ははてなエンジニア Advent Calendar 2019の25日目の記事です。昨日は
id:hitode909さんの以下の記事でした!
blog.sushi.money
今回はタイトルにある「異なるシステム間での大量データの同期」について、仕事でいくつか関わったので悩んだ事をログに残そうと思います。一緒に難しいねって笑ってくれたら嬉しいです。
「異なるシステム間での大量データの同期」って何のこと？
これは自分がつけた名前なのですが、例としてはシステムを完全にリニューアルするとかでDBのスキーマを再設計したシステムにデータを移すような場合や、あるシステム上の大量のデータをスプレッドシートのようなものに同期させてデータ分析をするようなケースを想定しています。前者のようなシステム移行は一度きりの同期でよくて、後者の場合はどの程度リアルタイム性が必要かによりますが定期的に同期が必要です。
- 同期元のデータを正しく変換する事
- 同期を短時間で済ませる事
- データの整合性を保つ事
前者については、データを正しく変換するには同期元と同期先のデータの両方を理解する必要があるという点で難しいです。一般に一つのシステムのテーブル構成を理解するのはすごく大変ですし、利便性を考えてあまり直感的で無いスキーマ設計をする事もあると思うので、そういうコンテキストも含めてある程度理解しないとうまく変換が出来ないです。また、テーブルのデータを丸ごと同期するような場合はうまく実装しないと数日では済まないようなものになってしまったりします。最後に、そのような大量のデータを同期しつつ、全体として整合性を保つのは非常に困難です。（困難な理由はあとで説明します。）こういう感じでとても難しいのですが、難しいなりに考えたことをまとめていきます。
12/25追記: こういったタスクにはETLという名前があるそうです。そちらで検索するといろいろ詳しい知見が得られそうです!
同期の仕組みの設計
とはいえAPIの設計はコミュニケーションも開発工数も非常に多くかかるものだと思うので、直接DBを見に行くという選択も十分あると思います。状況に応じて考える、で良いと思います。
データの同期方法
データの不整合が発生する仕組みと解決策
APIを介するにしても同期元のDBを直接見に行くにしても、大量のデータを整合性を保って取得することは非常に困難です。例えばある日の22時00分に、前日の22時00分から先に更新された全てのレコードを取得する場合を考えます。この場合前日の22時00分から当日の22時00分までのデータが取得されるのが期待できます。ですが、実際にはリクエストを順番にさばくためにあるテーブルのデータを取得し始めるのが22時05分からだとすると、あるデータは22時00分のもの、別のものは22時05分のものになります。これをある程度解決する方法としては検索範囲を前日の22時00分から当日の22時00分までとして取得することです。(つまり、リクエストの範囲について後ろも指定する。)この場合でも例えば22時05分にあるデータを取得し始めた場合、もし22時00分から22時05分の間に更新が行われた場合には22時00分のデータは消えてしまうことになります。
差分同期と一括同期
データ同期のさせ方としては、同期させるタイミングで都度全てのデータを一気に同期する一括同期と、事前に大半のデータを同期させておいて、都度差分だけを同期する方法があります。差分同期のメリットとしては前回の同期からの差分だけを同期させれば良いので短時間で処理が完了する事です。ですが差分同期は特にデータの削除が行われる場合実装が難しいので、使えるタイミングは限られると思います。
差分同期
差分同期(データは作成しかされない場合)
データが更新、削除しない場合差分同期は非常に有効な手段になると思います。 例えば毎日22時のデータを同期する場合は前日の22時に作成されたデータからその日の22時までに作成されたデータを同期すれば良いです。 また、s3やcloud storageのオブジェクトを他のバケットにコピーするような場合は、作成日時のような情報で範囲指定はできないですが、単純にバケットのデータのキーのリストを同期先のデータのキーのリストと比較して差分をインポートするという実装でも、都度全て同期するよりはずっと短時間で完了します。（当たり前といえば当たり前ですが）
差分同期(データの更新も行われる場合)
更新があった場合は先ほどのデータ不整合の仕組みで説明したような事が起きてしまいます。差分同期の場合の先ほど紹介しなかった他の解決策としては、同期元のシステムから更新リクエストを都度もらうという手もあるように思います。あとは、システム移行のように最後に一度同期が取れておけば良いという場合や、多少データ不整合があっても良いという場合には先ほど説明したような比較的起こりにくいデータ不整合は許容するという手もあると思います。
差分同期(データの削除が行われる場合)
差分同期の難しい点はデータの削除が行われた場合にそれを同期するのが困難な点です。前日に22時以降に更新されたデータを同期する、という条件で同期する場合に前日の22時以前に作成されて同期済みのデータが削除されたとすると、このデータの削除を同期する事ができません。なので、仕組みとしては削除履歴のようなものを同期元に用意するか、削除リクエストを同期元からもらう必要があると思います。あとは毎回全てのデータについてユニークキーを比較して消えてるものを見つけて削除する、という事もできると思います。
一括同期
一括同期は前回同期したデータを全て消して再度全て同期するような実装です。あるいは、システム移行の場合は一度に全てを移行するような実装です。 一括同期であっても同期中に同期元のDBの書き込みがあったりするとデータの不整合は生じてしまうのですが、特に削除される事のあるデータの場合差分同期より実装が楽なので、データがむちゃくちゃ多すぎてどうしようもない時でなければ一括同期は良い選択だと思います。
その他
パフォーマンスチューニング
今回話しているようなケースの場合、データのINSERTが大量にあるので積極的にバルクインサートを使ってN+1を解決するのが重要かなと思います。SELECTの時のN+1は身近な気がしますけど、INSERTでもN+1はかなり強烈で、実際これを解決するだけで10倍程度速度改善できた事もあります。他にはUUIDを払い出す場合もSELECT文が都度発行されるのでN+1にならないように一括で取得すると結構効いたりします。
ページング
APIにしてもDBから直接データを取るにしても、あまり大量のデータを取得しようとするとネットワークのタイムアウトなどがありうるので考慮しておく必要があります。SQLであってもAPIであってもオフセット法やシーク法などの実装があると思います。
エラーログと再実行の処理
システム移行の場合はデータの同期に数時間から数日かかる可能性もあります。そのような時に想定外の事が起きてエラーで止まった場合に備える事が必要です。備えとして必要なことは
などです。 パフォーマンスの点では一つのトランザクションが大きい方がN+1の問題を解決できて良いですが、あまり大きすぎて一つの実行に時間がかかりすぎると途中で失敗した時につらくなるので適切な粒度を考える必要があるかなと思います。
あとがき
以上、異なるシステム間での大量データの同期について、自分なりに考えたことをまとめました。拙い文章ですが最後まで読んでくださってありがとうございます。 2020年もよろしくお願いいたします！
読書中: 低レベルプログラミング (Igor Zhirkov)
始めに注意ですが、これはレビューのつもりでは書いてなくて、今ざっくりとこんな事に興味があるとか最近考えている事について本をテーマに喋ってるだけです。まだレビューが書けるほど読めてないですが、満足するぐらい読んだら何か書くかもしれません。
プロセスの管理とかそういうOSのやってくれる事と計算モデルとかそういうプログラミング言語に関する事については雰囲気が掴めてきたものの肝心のそのつなぎ目がよく分からなくて本を探していた。僕は学生時代物理学とか化学の理論的な研究をやってた人間で、コンピュータの事を真面目に勉強し始めたのは社会人になってITのエンジニアという職に就いてからだ。もう社会人になって一年半も過ぎるのでこの言い訳を外してしまいたいけど、なかなか自分に自信を持てるほどコンピュータに詳しくなったとは言い難い。結局抽象的な事をどんなに学んでも実際に作ったものはノイマン型のアーキテクチャに色々肉付けされた何かの上で動く事になる。なんとなくそういう現実を見ずに理論ばかり眺める事に後ろめたさを感じていたように思う。
この本はアセンブリ言語とC言語とその間について説明してある本で、まだ全体を軽く眺めた程度だが比較的理論的な説明が好きな人に受ける本な気がする。アセンブリ言語を説明するところではCPUなどの実行環境についての説明とその背景についての説明がいろいろされ、コンピュータが今のように非常に難しいものになってしまった歴史について納得しながら読み進める事ができた。正直前提知識が結構多い本に思われて、おそらく情報系の学部で学ぶいろいろな知識はあるのが前提な気がする。とはいえググりながら読み進めたらなんとかなりそうではある。僕のような学生時代に情報系の教育を受けていなかった人間としてはこういう障害はむしろ嬉しいもので、その業界で生きてる人たちにとっての常識の感覚を身につけたり、初歩的な本では載っていない学問的広がりについて知る事ができる。大学教育の良いところは研究の最前線にいる人から直接話が聴けるところで、何気ない雑談の中でその学問の世界が見えてきて、そうやって知識を彩のあるものにしてくれる点にあるように思う。正直この本がいつか振り返った時に良い本だと思えるかは分からないが、なんとなくいつか振り返る事ができるぐらいには深く理解をするきっかけとなるように思っている。昨日頑張って読み進めた結果今朝は脳が死んでしまっていたのでこれからはほどほどに読み進めていきたい。
