ストレージエンジンの話 ~InnoDBのredo logをざっくり理解する~

こんにちは。id:shallow1729です。最近Database Reliability Engineerというお仕事を始めたのでデータベースの勉強をしたりMySQLソースコードを読んだりしています。仕事でMySQLが標準で用いているInnoDBソースコードを読む機会があったのでなんかアウトプットしたいなと思いつついきなりコアな話するのもなって思ったのでざっくりとストレージエンジンの話をしようかなと思います。とはいえストレージエンジンは本当にいろいろな仕事をしていて全部を書こうとするとものすごい事になりそうだった(+僕も分かってない部分が多い)ので、とりあえず第一回はredo logというやつを中心にストレージエンジンを追っていこうと思います。なるべく一般的なデータベースの設計の話を軸に置きつつInnoDBの場合の話もしていこうと思います。読者としてはMySQLのようなリレーショナルデータベースの利用経験があることは前提にしていますが前提として必要なのはそれくらいかなと思います。もしデータベースをもっと深く理解したいと思った方はCarnegie Mellon Universityの公開している講義がとても面白いのでそちらもぜひ見ていただけたらと思います。

www.youtube.com

以下この記事でMySQLの話をしている時はMySQL5.7.32をベースに話しています。また、僕もまだデータベースの勉強を始めて日が浅く、きちんとコードを追わずに書いている箇所もあるので誤りがあればご指摘いただけたらと思います。

ストレージエンジンの役割(の一部)

まずInnoDBなどのストレージエンジンの役割についてざっくりと解説します。データベースへの読み書きのクエリがデータベースに送られた時、データベースはまずSQLのparse、実行計画の作成などを行なったあとにディスクへデータを書き込んだりデータをディスクから読み出したりします。ストレージエンジンはHDDなどの不揮発性のストレージとメモリ(バッファープール)の管理を行い、上位のレイヤー(execution engine)にストレージへの書き込みのインターフェースを提供する仕組みを提供します。一般的にはOSのファイルシステムがディスクの情報をバッファープールに乗せたりバッファープールの情報をディスクに書き込んだりといった仕事を担当しているのですが、データベースの場合は独自の要件が様々あるのでより効率的な読み書きを提供するために独自にこの仕組みを用意しています。バッファープールとストレージのデータ構造についてですが、基本的には同じ(バッファープール上でB+Treeならストレージ上でもB+Treeで、ログはログ)という認識でいいと思います。バッファープールからデータを削除するタイミング、ストレージにデータを反映するタイミング、ストレージからデータをバッファープールに載せるタイミングを処理していると考えるといいかなと思います。ストレージエンジンの役割という意味だと並列実行時のデータのアクセス制御など他にも重要なものがありますが、今回の説明では割愛します。

f:id:shallow1729:20210418202225p:plain
clientのリクエストを返すまでの概観の図です。execution engineはSQLのparseや実行計画を行い、ストレージエンジンに読み書きを行います。ストレージエンジンは読み書きが効率よく行われるようストレージからバッファープールにデータを載せたりバッファープールのデータをストレージに反映させる処理を行います。

Disk Oriented Database

先ほどストレージエンジンはメモリとディスクの間のやりとりをすると説明しましたが、具体的に何をやりとりするかはデータベースの設計思想次第になります。MySQLはDisk Oriented Databaseというデータがメモリに乗り切らない事を前提に設計されたデータベースになるので、バッファープールがいっぱいにならないようにうまくリソースを管理する必要があります。そのため、データの永続性の観点では必ずしも必要ないデータ(例えばあとで説明するundo logなど)もディスクに書き込みが行われます。とはいえ全てをリクエストが来た時に書き込むとレスポンスタイムが悪くなるのでMySQLの場合はデータの永続性の観点で書き込まないといけないもの以外は非同期にバックグラウンドスレッドが書き込んでします。現代のようなメモリの潤沢な環境で開発をしていると永続化しないデータをディスクに書き込んだりしないと思うので、最初はディスクへの書き込みが永続化目的かそうでないかで混乱するかもです。

ちなみにメモリが潤沢なんだからそんな設計しなくてもメモリに乗り切る前提で設計すればもっと効率の良い設計ができるんじゃないか?と思うかもしれません。実際webサービスの開発で車バッファープールのサイズをデータが全部載り切るように調整すると思います。そのようなメモリにデータが全部乗り切る事を前提に設計されたデータベースはIn Memory Databaseと呼ばれていて、VoltDBなどいろいろあるようです。また、Amazon Auroraはあとで説明するredo logという最低限同期的に書き込まないといけないデータのみをバックエンドのKVSに送っているようですが、これもSQLを処理するサーバー自身の仕事からバックグラウンドスレッドの仕事をKVSに寄せる事で負荷分散をしているという事かなと理解しています。

独自でストレージエンジンを持つ理由

先ほどの説明でMySQLのようなDisk Oriented Databaseはバッファープールにデータが乗り切らない事を前提に設計されている事が分かりました。次に、なぜこのバッファープールの管理をOSのファイルシステムでなく独自に管理するのか?という事を説明します。

まず、同期的な書き込みとそうでないバッファープールを介した書き込みを使い分けることはOSのファイルシステムでも管理ができます。例えばfsyncを使えば同期的に書き込めます。

独自に管理しないといけないケースとしては、例えばバッファープールから消すデータを選ぶ処理があります。あとで詳しく説明するのですが、例えばinsertが行われた時にB+Treeにそのレコードを同期的にストレージに挿入する必要はcrash recoveryの観点では無いのですが、バッファープールから未反映のデータを削除すると再読み込みが大変になるのでフラグを立てて反映してから削除するようにする必要があります。また、なるべくアクセスされていないデータから順に削除しないとすぐに再読み込みが発生する可能性が高まるので、ホットなデータをうまく見分けてバッファープールの管理をする必要があります。また、where句などで複数のレコードにアクセスされる場合は次にアクセスされるレコード(実際はストレージエンジンはページというもう少し大きい単位で管理していますが、レコードと思ってもそこまでおかしくならないと思うので今回はレコードで統一します。)をバッファープールに先読みして乗せておくとパフォーマンスが上がります。こういった処理もB+Treeの事を知っていないとできないのでOSには難しい処理になります。このように、データベースの機能を理解しないとうまくバッファープールを管理できないのでストレージエンジンを独自に用意する必要が出てきます。

f:id:shallow1729:20210418205300p:plain
B+ Tree indexのサーチの図。次に読むデータを先読みしてBuffer poolに載せたいがどれが次のデータかはB+Treeを知っていないと分からない。

レコードのデータ配置

なんとなくストレージエンジンの仕事が把握できたかと思うので今回の主題のInnoDBredo logとundo logの話に行こうと思ったのですが、そのためにはレコードのデータをストレージ上でどう管理するかという話題も話した方がいい気がしたのでもう少し寄り道します。ストレージ上でのデータ配置を説明する理由は、ストレージのランダムアクセスが非常に遅くデータ配置がパフォーマンスに強く影響するためです。なので、三つほどデータ構成のモデルを紹介してメリットデメリットを考えます。かなり簡略化しているので詳細に興味がある場合はCMUの講義のChapter 3, Chapter 4をご参照ください。

まず一番簡単に思いつくのはレコードの情報をそのまま横に並べるようなデータ構造で、update時はこのレコードの値を修正する、select時はこの一連のデータを読み取るという形で実現できます。この配置はn-ary storage modelという構成で、レコード単位でのデータの読み取りが非常に簡単で、書き込みも単純に該当レコードを検索して更新すれば良いです。InnoDB含め広く採用されています。

次に紹介するのはDecomposition Storage Modelという構造で、これは複数のレコードについて同じカラムのデータを近い場所に配置しています。このデータ配置のメリットとしては、テーブル全体を集計するような集計系のワークロード(OLAP)に対して、集計に必要なカラムだけにアクセスする事ができる点があります。そのためGoogle BigQueryなどのデータウェアハウスで広く用いられています。n-ary modelではたとえ集計に使うカラムがレコードの中に一つであってもフルスキャンになってしまうのでこの点でDecomposition Storage Modelは優れています。一方で一レコードの複数のカラムをupdateしたい時にn-ary modelだと単に対象レコードを検索してupdateするだけだったのが、このモデルだとディスク上の離れたカラムに書き込みに行くのでランダムアクセスが発生してしまいます。なので、シンプルな書き込みが頻繁に発生するOLTPにはn-ary modelが採用されています。これはweb開発でMySQLのようなn-ary modelを採用しているデータベースを用いる理由の一つでもあります。

ここまで説明したn-ary modelとDecomposition Storage Modelは1レコードに対して一つのマスターデータがあって、update時はそのデータを上書きするようなモデルでした。最後に紹介するlog structured file organizationはupdate時に上書きするのではなくログを追加するようなモデルです。このモデルは頻繁に更新されるレコードについてはログがどんどんたまっていっていくので読み取り時は都度最初からリプレイする必要があってパフォーマンスが悪いです。しかし、メリットとしては複数のレコードを更新する時にたとえそれらがストレージ上は離れていてもランダムアクセスが発生しないので書き込みが高速になります。InnoDBなどのストレージエンジンではこの形式は読み取りが大変なのでデータを読みに行く時には使っていないのですが、実はinsertやupdateなどの書き込み系の処理が走る時にcrash recoveryできるようにする目的で同期的に書き込むのはここで説明したようなログの形式のデータ(redo log)になります。(正直書いていてredo logをlog structured file organizationと呼ぶのは不適切かもなと思いました。ここで伝えたかった事はレコードを構成するにはカラムのデータを書かなくてもログだけでも再構成できるよという事でした。以下では単にログ形式と表現します。)

f:id:shallow1729:20210418214142p:plain
n-ary model, Decomposition Storage Model, log structured file organizationのそれぞれのデータ構成の図です。idnはレコードのユニークid、cnはカラムの種類です。n-ary modelはレコード単位でカラムのデータが近い配置で置かれています。Decomposition Storage Modelはレコードをまたがって同一カラムのデータが近い配置で置かれています。log structured file organizationではupdate時は変更したカラムの値のログを残し、delete時も削除を行わずログだけ残しています(ログの形式はイメージです。)

redo log

redo logは書き込み実行後の状態を残していくログで、障害復旧時にcommit済の内容をレコードに書き込むのに使えるログです。InnoDBはもう一つundo logというログも持っていて、こちらは変更前の値を残すログになります。こちらはトランザクションのrollbackの際や、MVCCという古いレコードの状態を参照したい時に用います。undo logについては別の記事で紹介します。

InnoDBredo logとレコードの関係

先ほどの説明でInnoDBがn-ary modelで構成されたレコードとログ形式(redo log)の二つのモデルを採用している事が分かりましたが、これらはどういう関係なのかについて解説していきます。

まず、基本的にレコードの読み取り時はredo logは参照しません。読み取り時はバッファープール上のレコードの形式で保管されたデータを読みにいきますし、書き込む時もバッファープール上のレコードを書き込みます。ここでバッファープールはメモリなのでディスクアクセスに比べてランダムアクセスの問題は特に気にしなくて大丈夫です。このように、基本的にはバッファープールの上の読み書きで完結するようにしています。ただ、書き込みをバッファープールだけで済ませて書き込み成功を返してしまうと、もしストレージに反映する前にデータベースがクラッシュしてしまうとそのデータは消えてしまいます。

f:id:shallow1729:20210419002616p:plain
insertをcommitした時にバッファープールにだけ書き込んで成功を通知したけど実はストレージに書き込む前にクラッシュした場合の図。バッファープールの青色の箇所が同期的に反映したレコードです。ユーザーは書き込みに成功したと思っていますがサーバーを再起動するとそのデータは消えてしまっています。

そのため同期的に何かしら書き込む必要があるのですが、InnoDBを含め一般にこれにはログ形式を用いています。このログを用いた手法をwrite ahead log(WAL)と呼ぶのですが、crash recoveryの観点で重要な事はログを書くというよりは間にワンクッション置く事の方が重要で、例えばログを使わない方法としては更新時は更新後のレコードをストレージの別の場所に書いて、書き込みが完了したら参照の向け先を変えるような方針も可能です。ログ形式は読み取りが大変なので障害からの復旧には時間がかかりそうですが、障害が滅多に起きないなら障害時のパフォーマンス上のデメリットより書き込み速度のメリットが大きそうです。以下の図でログのワンクッションを置く事で障害復旧できないデータが発生する事を防げる事を示します。

f:id:shallow1729:20210418230642p:plain
直接ストレージのレコードを書き込みに行った場合の図です。上から下の時系列でinsertしたデータをupdateしようとしており、updateをストレージに書き込む時にクラッシュが発生した場合を想定します。もし書き込み途中でクラッシュが発生すると書き込み中のデータは中途半端になる可能性があり、元のデータの情報もupdate後の値の情報も残っていないのでに変更する事もできない復旧できなくなってしまいます。
f:id:shallow1729:20210418231302p:plain
間にログを挟んだ場合の図です。ログの形式はいったん"end"で終わっていたら書き込み成功とします。図はログの書き込み中にクラッシュした場合になります。この場合レコードのデータはまだ触れられていない状態なのでログを単に捨ててしまえば良いです。ログの書き込みは同期的に行うのでユーザーはcommitの成功を受け取っていないのでこれで問題ないです。また、ログの書き込みは完了しているけどレコードへの反映が中途半端な状態の時はログを元にレコードを復元すればよくなります。

ちなみにredo logの書き込みのタイミングですが、基本的にinsertやupdate時にバッファープールに書き込まれて、transactionのcommit時にストレージに反映させるという感じです。*1注意点として、MySQLのユーザーの感覚だとtransactionを明示的にcommitするのは複数のテーブルにまたがってinsertする時などかと思いますが、MySQL的には一レコードのinsertであっても内部的にはtransactionの開始、insert(レコードやログをバッファープールに書き込む)、commit(ログをストレージに反映)という流れです。なぜcommit時までストレージへの反映を待つかというと、commitされていない場合はユーザーにまだデータが反映された事を約束しておらず、障害時は消えてもよい変更だからです。(ただしDisk Oriented Databaseなのでバッファープールの管理の一環でディスクに書き込まれるのはあると思います。その場合はむしろゴミ掃除になるはずです。)

ちなみに正常時にいつレコードに書き込んだデータをストレージに反映しているかというと、MySQLではpage cleaner threadというバックグラウンドスレッドが担当しているようです。(まだこの辺ちゃんと把握しきれてないのでバックグラウンドスレッドが間に合わなかったらどうなるかなど分かってないです。*2 )基本的にはバッファープールとストレージのデータは同一の形式なので普段はバッファープールのデータをそのままストレージに反映させる方向のはずです。redo logが用いられるのは本当にクラッシュ時と、おそらくクラッシュ時の復旧速度を上げるために最近のログまで反映しきるcheckpointの作成時ぐらいなんじゃないかなーと思います。以下に概略図を置きます。

f:id:shallow1729:20210418234028p:plain
データの書き込み時の反映のタイミングの図。青色は書き込みリクエスト時に同期的に書き込む場所で、緑色はバックグラウンドスレッドやリブート時などの同期的でないタイミングのものです。書き込みのリクエストがあった場合はBufferpoolのredo logとレコードはどちらも書き込まれ、redo logについてはストレージにsyncします。(正確にはsyncはコミットのタイミングを待ちます。)redo logを用いるのはcrash recoveryと、それを高速化するためのチェックポイントの作成時のみで、正常時はbackground threadでbufferpoolのレコードをストレージの領域に反映させます。ちなみにここではレコードとredo logのみしか書き込んでいませんが、実際にはundo logなど他にもいろいろ書き込んでいます。

最後に

今回はストレージエンジンの役割をredo logを中心にざっくりと見ていきました。redo logはcrash recoveryというデータベースの重要な機能の主役になります。次回はundo logというInnoDBが扱うもう一つのログを見ていきます。(実は本当に話したかったのはundo logで、redo logとundo logの役割は独立しているのでいきなりundo logの話を書いても良かったのですが、フォーマット的には対になっているしredo logの方が主役っぽい仕事をしているのでredo logを説明せずにundo logを説明する事に気が引けてしまいました。)ある程度基礎的な概念を出したらソースコード紹介的な記事も書いていきたいと思います。長々と書きましたが最後まで読んでくださってありがとうございました。データベースは非常に長い歴史があり、現在進行形で発展の進んでいる面白い分野なのでこの機会にぜひ興味をもっていただけたらと思います。以上です。

*1:追記: InnoDBではログバッファーとバッファープールは別で管理されているようなのでこの記述は間違いです。InnoDBアーキテクチャの図のurlを貼りましたので参照ください。

https://dev.mysql.com/doc/refman/8.0/en/innodb-architecture.html

*2:追記: 書き込みが多い時はログバッファーの方が普通先に枯渇するので、ログバッファーを見て必要に応じてdirty pageをflushするという挙動のようです。https://dev.mysql.com/doc/refman/5.6/ja/innodb-performance-adaptive_flushing.html

転職しました

別に退職/入社エントリーみたいなのを書くつもりは無かったんですけど、今後ここに何か書いた事が何か良くない方向に行った時に前の所属の人間の言葉として広まって迷惑かけたら嫌だなと思ってという感じで書いたエントリーです。1月いっぱいで退職しました。僕は前職に居た事を誇りに思っているので、今後とも僕が周りの人に自慢できるようこれからも高い技術力でインターネットコミュニティを支えてもらえると嬉しいです。僕は僕の目指す方向で精一杯頑張ります!

Atcoderで緑色になりました

8月に始めて半年で緑になれました。緑は大した事ないって声をたまに聞くのですが普通にプログラミングの実装能力を求められると思うので緑コーダーですって言われたら僕ならエンジニアとして信頼するだろうなと思いました。

f:id:shallow1729:20210110235713p:plain
https://atcoder.jp/users/shallow1729

とはいえ緑ってatcoderの中ではまだまだ序盤なので弱点がたくさんある状態なのかなとも思います。僕の場合全探索以外のグラフのアルゴリズムやセグメント木みたいな高度なデータ構造は使いこなせていないのが露骨な弱点だなって感じています。一方で自分のアルゴリズムやデータ構造の知識の範囲で解ける問題はそこそこ解けると感じているので自分の知識を元にアルゴリズムを組み立てる力とかはまあまああるのかなって思っています。

次は水色目指して頑張ります!

AtCoder Beginner Contest 186に参加しました!

結果

atcoder.jp

ABCDの四問解けました。E解けそうだったので悔しい...

振り返り

Cまでは一瞬でした。

C - Unlucky 7 は8進数だとpythonはそういうメソッドがあるので脳死で解けてしまいましたね...今後のために任意のn進数への変換は何かライブラリ作っておきたいなって気持ちになりました。

D - Sum of difference は実装は簡単だけど頭使わないといけない系だから解けた時は自分に対して頭いい!って言ってたけど参加者の中では別に解けたの早かったわけじゃないんだなって分かってびっくりしました。つくづく思うんですけどプログラミングコンテストやってる人みんなむっちゃ頭いいですよね。

E - Throne今朝ぼーっと見てたサイトの記事とまんま一緒っぽそうでした。気づいてはいたんですけど中身読んで理解するのに時間がかかったのと、modでの割り算、除数が素数の場合にしか対応してなかったからそっちの対応してたら時間が足りませんでした。パッと直せたら良かったんですけどねー。人のコード理解するのが遅いのも問題だしライブラリが充実していないのも問題ですね。後者は時間をかければ解決するのでまあいいんですけど、前者はなんかうまい方法論見つけたいなー。最近Code Readingという本を読み始めたからうまくやっていきたいです。

Fはまだ見てないです。

良かった事

Atcoder初心者が成績アップに繋がったと感じた考え方の工夫 - shallowな暮らし で問題の解き方に困った時の考え方をまとめたんですけど、D問題はうまく生かされましたね。特に「簡略化した問題を考える」っていう方針が今回は効いてて、ソートされてたら絶対値取れて簡単だねって思いついて、良く考えたら普通にソートしたらええやんってなった感じでした。ちょっと前までだと何もできずに時間を溶かしてた気がします。仕事も含めてですけど最近はどちらかというと考え方とか概念的理解みたいな抽象的な根っこの部分よりは具体的な知識がボトルネックになってきていると感じているので、しばらくは知識をつける方にフォーカスしたいなって思っています。今の自分が昔見た本とかを読み返すとどう感じるか、みたいなのが今から楽しみです。

そんなわけで、とりあえず今回も点数には反映されなかったけど成長を実感できたのでまあよかったかなって思います。次こそE問題解きたい...!!!

Atcoder初心者が成績アップに繋がったと感じた考え方の工夫

こんにちは。id:shallow1729です!この記事ははてなエンジニア Advent Calendar 2020の7日目の記事です。

qiita.com

昨日はid:stefafafanさんで「iTerm2の機能を使いこなして日頃の作業の効率をあげたい2020」でした!

stefafafan.hatenablog.com

iTerm2僕も使ってるはずなんですけど知らない機能がいっぱいでした。

はじめに

この記事は半年ほど前から参加していたAtcoderというプログラミングコンテストを振り返って、特に成績アップに繋がった問題を解く時の思考方法の工夫について書いたものです。まだ始めて4ヶ月ほどで十分に参加できていないのでまだ茶色ですが、ここ三回はパフォーマンスが一気に上がって、Atcoder Begineer Contest(以下ABC)の問題ならD問題までは安定して解けるようになってきましたし、E問題も方針はうまく選べるようになってきました。まだまだ初心者ですが、工夫が成長に繋がった事がすごく嬉しかったので試した事をいろいろ書いてみようと思います。なお、この記事ではABC181からABC184の問題のネタバレも入っているのでそういうのが嫌な人はブラウザバックしてもらえたらと思います。

f:id:shallow1729:20201206011424p:plain
https://atcoder.jp/users/shallow1729/history

アルゴリズムの勉強

メインの考え方の話の前にアルゴリズムの知識に関する話から入ります。プログラミングコンテストに参加するとなるとアルゴリズムの知識が結構いると思っていたのですが、少なくとも僕が参加していたABCのD問題ぐらいまでだと、自分の実装の計算量を見積もるなどの基本的なアルゴリズムの解析やメモ化を使った高速化はできる必要がありますが、名前のあるアルゴリズムの実装についての知識はそれほど多くは求められていないような印象です。計算量の見積もりが重要な理由は、コンテストの制限時間は結構短いので、明らかに間に合わなそうな実装の時はパフォーマンス改善を考えたり、逆に不必要にパフォーマンスチューニングをして実装コストを増やさないなどの判断を素早くできる必要があるからです。経験上はO(10^ 7)あたりがギリギリ間に合うか間に合わないかという感覚なのでそういうイメージで設計をすると良い気がします。ただ、もう少しテクニカルなアルゴリズムの知識についていうと、スタックやキュー、グラフの全探索あたりは頻繁に出てくるので実装に慣れておく必要があるかなと思います。あと、場合の数を求める問題などで出てくるでかい素数で割った余りを答えよみたいな奴対策でmod計算用のライブラリは事前に用意しておいたほうがいいと思います。modの計算というのはこちらで紹介されているようなやつです。

drken1215.hatenablog.com これだけは持っておかないと方針があってる回答でもTLEになってしまったりするので。。。

E問題になると整数問題で使うアルゴリズムや二分探索、Union-Find Treeなど、もう少しアルゴリズムの知識を必要とする問題も出てくる印象なので勉強はやっとくに越した事は無いと思います。ただ、知識があるのと実際に知識を使えるようになる事の間は結構あると感じているので、知識があれば問題が解けるかというとそうでは無いと思います。

数学的な問題解決の思考方法

今回メインで書きたかったのは数学の問題を解く時によくやるような試行錯誤のテクニックです。数学の勉強ってもちろん覚えないといけないことがたくさんありますけど、大事なのはそれをうまく使って問題を解くところというのは受験などを経験した人は分かるんじゃないかなと思います。そこの能力って才能として見られがちですが、案外訓練で改善できるものだと思っています。実際数学の問題解決の方法についてはいくつか本があって、有名な本だとG.Polyaの「いかにして問題をとくか」があると思います。今回はそういう試行錯誤の技術について、実際の問題を解いた時の思考の流れと一緒に説明できたらなと思います。

実験する

見慣れない問題や方針に困る問題を見たらとりあえず手を動かしてみましょう。いくつか試してみるとアイデアが思いつく事があると思います。

atcoder.jp

なんか難しそうな問題ですね。難しそうな問題はとりあえず手を動かしてみましょう。(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)で三手になってしまいます。こんな感じで実験をすると最大でも三手でクリアできると分かってくるんじゃないかなと思います。あとは一手か二手か三手かを判定する方法を考えるという形になります。(この場合分け難しかったんですよね。。。今後の反省点です。。。)

atcoder.jp

全ての都市間について移動ができるようなグラフの問題に見えます。グラフの問題として全探索を行っても解けるかなと思いますが、実際に経路を並べてみるともっと単純なパターンが見えてきます。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で用意されているのでそれを使ってしまえば良いという感じです。これを紹介した理由として、実験する時は元の問題の文章に引っ張られずにフラットに見ると良いよと伝えたかったからでした。もちろん問題文から得られるイメージは解決に役立つ事もありますが、変にバイアスになって重要な性質を見落としたりする事もあるので要注意です。

逆から考える

問題の道筋が見えない時はゴールから逆算するという戦略が有効です。

atcoder.jp

この問題は各人iについてS_iからT_iまでの間P_iリットル水を使おうとした時に使おうとする水の量がWを超える瞬間があるか?という事に答える問題です。NとTが 最大で 2 \times 10^ 5なので単純に時刻ごとに全件を足してると間に合わなさそうです。この問題に答えるために各時刻で使われる水の量の総和さえあれば良さそうです。ある時刻に使われる水の量の総和は「その一つ前の時刻に使われている水の量」+「その時刻に使い始める水の量」-「その時刻に使うのをやめる水の量」で求められます。つまり、この問題を解くためにはこれらの情報を準備すればいい事がわかります。「その時刻に使い始める水の量」は時刻 tの関数として A(t)=\sum_{S_i=t} P_iで初期化の時に計算できる。「その時刻に使うのをやめる水の量」についても同様ですね。「一つ前の時刻に使われている水の量」は初期値0で時間発展の中で都度計算されるものなので特別な準備は不要です。このようにすると計算時間が間に合うようになります。大事なのは問題を解くのに必要なデータ構造を先に考えて、それをもらった入力から作れるか?と考えた点です。ゴールから考えた事で実装までの流れが見えやすくなりました。

簡略化した問題を考える

複雑な問題をそのまま解くのではなくて、それをもう少し簡単な問題にした時に解けるかを考えてそこから考えるという奴です。

atcoder.jp 例えばこの問題はN人の児童と身長の変わる一人の先生でペアの身長差が最小になるような組み合わせを作るという問題です。この問題だと「先生の身長が変わる」というのは明らかに問題を難しくしています。なので、いったん先生の身長は変わらないと仮定して自由度の少し減った問題を考えます。そうすると小学校でよくやるように背の順で並んでペアを組むという戦略が多分思いつきやすくなると思います。N人の児童を背の順にソートして隣同士をペアにすればいいという基本方針が思いついた段階で、先生の身長が変わるという条件を持ってきます。この問題は先生の身長のパターンを全て試した中でペアの身長差が最小の答えを求めればいいとわかりますね。この問題を解くために考える必要がある事は二つで、一つは先生の身長が決まった場合にペアを決めるという事、もう一つはペアが決まった時に合計をどのように求めたらいいかという問題があります。前者についてはソートされた配列の中での自分の場所を決める問題なので二分探索が使えそうです。後者のペアが決まった時に合計をどのように求めたらいいかについてですが、児童のペアの作り方は先生とペアになるか、前の人とペアになるか、後ろの人とペアになるかになります。例えばもともと前の児童とペアになっていた児童の間に先生が割り込んできた場合、その児童は後ろの児童とペアを組むことになります。同様にそこから後ろの児童は全員ペアが前の人から後ろの人に変わります。なので、ペアの身長差の総和は先生より前のペアについての総和と先生と児童のペアの身長差と先生と児童のペアから後ろのペアの身長差の総和の三つで計算できるようになります。先生と児童のペア以外は事前に前のペアと組む場合と後ろのペアと組む場合について累積和を作っておけば定数時間で総和を計算できますね。難しい問題に見えますがステップを分割して一つ一つの段階をよく考えればきっと解けるんじゃないかなと思います。

最後に

というわけで今回は僕が成績アップに繋がったと感じたプログラミングコンテストの問題を解くための考え方の工夫をまとめてみました。一番伝えたかったのは数学の問題を解くイメージでプログラミングの問題を解くと筋道を立てやすいよというところです。プログラミングと数学の関連はよく強調される一方で個人的にはなかなか実感を持てなかったのですが、今回試行錯誤をする中でなんとなく分かってきたような気がします。とはいえ僕もまだまだ解けない問題多いので、もっと試行錯誤して今後もプログラミングコンテスト楽しめたらなと思います。

明日はid:kouki_danさんです!よろしくお願いします!!

AtCoder Beginner Contest 175に参加しました! + 最近やってたこと

タイトルの通り先週末はAtCoder Beginner Contest 175に参加しましたー。 ABCの三問しか解けなくて悔しかったけどパフォーマンスは1119なので緑ぐらいのパフォーマンスにはなりました! f:id:shallow1729:20200817221949p:plain C問題を開始20分で解けて気分良くD問題に行けたのですが、結局Dをうまく通せずに終わってしまいました。

atcoder.jp D問題、Kの範囲に対してNがむっちゃ小さい+飛び先が自分自身でない事から循環しうる事がまず分かって、一周した時に0より大きいかで場合分けが必要なのもなんとなく分かってパフォーマンス的にもO(N2)程度で済みそうやしいけるかなと思ったものの、これ結構大変じゃない??ってなって解くのにひよってしまいました。Dなんだからもっと簡単なのあるでしょ?とか思って20分ぐらい悩んでも思いつかないから諦めて循環見つけようってなりました。多分一般には循環は深さ優先探索で見つけるんだと思うんですけど、グラフアルゴリズムはまだあまり勉強してない状態だったのでこの前趣味で書いたFloydのうさぎとかめのアルゴリズムを使いました。 Floydのうさぎとかめのアルゴリズムは動画でたまたま知って面白かったのでその時に実装しました。

www.youtube.com

でも今思うと循環を難しく考えすぎですね。 今回の場合なら循環の開始地点と開始地点は一致すると考えていいので、単に開始地点をメモって、開始地点に戻ってくるまでfor文を回すだけで十分ですね。

f:id:shallow1729:20200817223446p:plain
左は開始地点と循環の開始地点が異なる場合、右は開始地点と循環の開始地点が一致する場合

で、一周させた時にスコアが0より大きいなら何周もさせればどんどん大きいスコアにする事ができます。一方で0より小さいなら何周もさせる意味は無いので一周させる中でベストの値を返せば良いです。ここまでは制限時間内に思いついてそこそこ通るものができたのですが、いくつか通らないまま終わってしまいました。何で引っかかっていたかというと一周のスコアが0より大きい場合に先に周れるだけ周ってからあまりを足してたんですけど、それが良くなかったんですよね。

4 40
3 1 4 2
1000 2000 4000 -6000

↑みたいな入力の時って10周させるよりも9周して残りいい感じのところでやめた方がいいスコアになるんですよね。なので周るだけ周ってからあまりを進むのではなく、一周回るまでの範囲で連続する長さをいろいろとって、残りの値で周れるだけ回った中で一番いいスコアをとるのが実際はいい戦略になります。こういうの結構教育的ですね。端数をあまり雑に扱うと痛い目をみるんだなーって思ったので次からの教訓にします。Eからは見てないです。正確にはEはチラ見してそっ閉じしました。問題にはなんか見覚えあると思いつつ全然分からなかったので諦めました。

前のABC174から二週間あって、その間はほとんどCとDの問題を解いていました。全探索とか合同式を使う問題をパッと解けたいなーと思ってその辺を勉強していました。2値の全探索ならbit演算でシュッとかけると思うんですけど3値以上のめんどくさいやつの時の実装がなんかうまく書けないなーってなってました。一回アドリブで再帰を使って実装したんですけど、こちらの記事にきれいにまとまってるように考えて書くとすごくいい感じになりました。

drken1215.hatenablog.com

あとは「アルゴリズムイントロダクション」とか「離散数学への招待」みたいな本を読んでました。まだちゃんと勉強できてないんですけどマトロイドとかいうやつむっちゃかっこよくないですか!?凸関数の一般化みたいな感じっぽいですね。凸関数、最適化がスムーズにいくのがイメージつくと思うんですけどそれをもっと抽象化する事で貪欲法が使えるかを判断できるって感じですよね。ちょーかっこいい!!なんか面白そうだからちゃんと勉強したいですね!!

あとはなんか急にどうやってグラフって描画されるんだろう?ってのが気になってコンピューターグラフィクスのラスタライズのアルゴリズムを調べたりしてました。アルゴリズムの勉強、なんか自分の肌に合ってる気がしているのでもっと深くやっていきたいです。

AtCorderに初めて参加した!!

あんまり人に読ませる文章ではないです。

感想: 楽しかった!!!

前職はプログラミングコンテストが盛んな会社だった。黄色とか大会での優勝経験がある人とかが何人もいて、みんなすごいなーと思いつつ、自分の仕事はアルゴリズムがそれほど陽に出てこなかったし、しかも非情報系から未経験でエンジニアになった事もあって他に勉強する事が山ほどあったからちょっと遠くから見ている感じになっていた。あと、正直アルゴリズムを学ぶという事の意味がよく分からなかったというのもある。アルゴリズムを見てるとよく思いつくなーと思いつつ自分が思いつけるだろうか?みたいな悩みがあった。僕は物理学がすごく好きで、なぜかというと運動方程式マクスウェル方程式みたいな少数の知識だけで多くの問題を解けるからだ。それはシンプルで綺麗という個人的な美的感覚にあってたのもあるし、記憶力や発想力がそれほど無くてもできるから自分に合っていたというのもある。それに比べるとアルゴリズムはなんとなく場当たり的な発想のように見える部分が多かった。結局最初に勉強した時はソートアルゴリズムとかグラフアルゴリズムみたいなのの教科書的な話に一通り目を通して終わってしまった。

アルゴリズムに興味を持ったきっかけは数年前に買って以来ずっと本棚に眠っていた「アルゴリズムイントロダクション」を一ヶ月ほど前に読んだ時だった。分割統治法の説明の中で出てきたマスター法による計算時間の見積もりのところがすごく面白かった。それまで分割統治法が使えるかをケースバイケースでやっていたのが、ある程度一般化された数学で考えられる事を知った。あとは動的計画法や貪欲法が適用できるかに関する考察も面白かった。こういう知識をうまく自分の中で整理できたら自分でもアルゴリズムを設計できるかなって思って、なのでアルゴリズム設計の指針についていろいろ仮説を立てて、どういう手法を使えば良いか分からない実際の問題で試して仮説を検証してみたいなと思った。

そういう訳でAtCoderの問題を挑戦しようという感じで「AtCoder Beginner Contest 174」に挑戦してみた。一応過去問をいくつかは解いてて、D~Fで一問解けるかなぐらいにはなってきたので4問答えるのを目標にした。結果としてはABDの三問解けた。C難しかった...Eは解けるようになりたいなー...

Aはまあプログラミング慣れてる人ならすぐだと思う。Bは分子シミュレーションの研究していた頃に100億回ぐらい書いたので一瞬だった。Cはなんていうか、整数から逃げ続けたツケという感じがする。試験中に鳩の巣原理で2と5が無ければ11111...はKで割れるのを証明できるのを知ってすげーって思ったけどデカい数字を割るのが良くなくてTLEになってしまった。最近だとmodは高校で習うんだろうか?数学オリンピックとかだと普通に出てくるから国際的には習うもんなのかな?僕は結局大学含めて出会う事なく学生時代を終えてしまいました。次は間違えないようにする。Dはなんか実験してこれで行けそうかなって感じでやったら行けた。解けたのはいいけどなんか思いつきに頼ってしまった感じで良くない...。Eは簡単そうに見えて全然思いつかなかった。解説読んで二分探索なるほどねーってなった。なんかうまく考え方の中に組み込めそうな気がするからあとでしっかりめに考察する。Fはなんかこの前セグメント木作ったからそのまま使えそうならやってみるかという感じだったけどなんかうまくできなかった。慣れない事するもんじゃない。解説眺めた感じセグメント木ですらなさそう。

という事で初挑戦は700点でした。難しかったけどやっぱこういうのは勉強した事をゲーム感覚で試せていいなって思った。次は4問解きたい。