AtCoder Beginner Contest 215 D 問題 Coprime 2 の解説
はじめに
この記事では AtCoder Beginner Contest 215 D 問題 Coprime 2 を解く、計算量が悪いが AC する解法について書きます。
計算量の良い解法については公式解説を参照してください。
問題
長さ $N$ の正整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。
$M $ が与えられるので、$A$ のすべての要素 $A_i$ について $\gcd(A_i, k) = 1$ かどうか、を $k = 1, 2, \dots, M $ に対して判定してください。
制約: $ 1 \le N, M, A_i \le 10^5 $
解法
素因数分解を考えると「$\gcd(x, k) = 1$」と「$x$ のすべての素因数 $p$ について $\gcd(p, k) = 1$」が同値ですから、$A$ の代わりに $A_i$ の素因数を並べた列を考えても答えは同じです。これを $B$ としましょう。たとえば次のようになります。
- $ A = (\textcolor{#BA8066}{3}, \textcolor{#BAA966}{1}, \textcolor{#A1BA66}{9}, \textcolor{#66BA80}{5}, \textcolor{#66A1BA}{6}, \textcolor{#6677BA}{2}, \textcolor{#8066BA}{4}, \textcolor{#A966BA}{7}, \textcolor{#BA66A1}{8})$
- $ B = (\textcolor{#BA8066}{3}, \textcolor{#BAA966}{1}, \textcolor{#A1BA66}{3}, \textcolor{#A1BA66}{3}, \textcolor{#66BA80}{5}, \textcolor{#66A1BA}{2}, \textcolor{#66A1BA}{3}, \textcolor{#6677BA}{2}, \textcolor{#8066BA}{2}, \textcolor{#8066BA}{2}, \textcolor{#A966BA}{7}, \textcolor{#BA66A1}{2}, \textcolor{#BA66A1}{2}, \textcolor{#BA66A1}{2})$
さらに、明らかに、$B$ の重複する要素は無視できるので $B$ の長さはたかだか $10^5$ 以下の素数の個数と考えてよいです。具体的には 9592 です。
$k = 1, 2, \dots, M $ に対し「$B$ のすべての要素 $B_i$ について $\gcd(B_i, k) = 1$ かどうか」を考えます。いま $B_i$ は素数なので $\gcd(B_i, k) = 1 \Leftrightarrow B_i \nmid k$ です ($B_i \nmid k$ は、$B_i$ が $k$ を割り切らない、の意味です)。
計算量を見積もりましょう。
- 前半の $A$ から $B$ を求めるパートは、素因数分解を $N$ 回するため $O(N \sqrt{\max A})$ 時間
- 後半は各 $k$ に対し $B$ の要素を全部見ることになってもループ回数が $9592M \le 10^9$
したがって速い言語なら実行時間制限の 2 秒に間に合って AC できます。提出例: PyPy3 880ms
Rustで実装！ 作って学ぶRDBMSのしくみ を読んだ感想とメモ
はじめに
WEB+DB PRESS Vol.122 の特集『Rustで実装！ 作って学ぶRDBMSのしくみ』を読みました。
この特集は、出版社のサイトにも説明があるように、(実際の RDBMS に比べて) わずかな機能のみをサポートする小さな RDBMS を作りあげることで RDBMS の仕組みを知ろうという特集です。
説明が簡潔でソースコードの例示がたくさんあり読みやすかったです。ソースコードの全体 https://github.com/KOBA789/relly を見てみるとより理解が深まりそうです。
読むにあたって最低限必要な準備は
でしょうか。
以降は各章のメモです。
第 1 章: RDBMS を作ろう
- よくある RDBMS のアーキテクチャは、上から (RDBMS を使う側に近いところから) 、構文解析器/クエリプランナ&実行計画/クエリエクスキュータ/アクセスメソッド/バッファプールマネージャ/ディスクマネージャ
第 2 章: ディスクマネージャの実装
- ヒープファイル
- ディスクマネージャが読み書きするファイルのこと
- ディスクマネージャは「ページ」ごとにアクセスする
- ページ
- (Rust) New Type パターン
第 3 章: バッファプールマネージャの実装
- ディスクアクセス遅すぎ問題 (メモリアクセスに比べると)
- バッファプールマネージャは一度ディスクアクセスで得たページの内容を覚えておく (キャッシュする)
- 実は、ほとんどのファイルシステムにもキャッシュ機構がある
- バッファ: ページのデータ (ただのバイト列
[u8; 4096]) + α の情報 - バッファプール: バッファを並べたもの
- バッファプールがいっぱいになったとき、もう使われてないバッファのうち再利用しなさそうなバッファを捨てる
- Clock-sweep アルゴリズム: PostgreSQL で使われている
- 直近でたくさん貸し出していたバッファは捨てられにくくなっていそう
第 4 章: B+Tree の観察
- B-Tree: 平衡 N 分木のひとつ
- 実際はいろいろとバリエーションがある (B+Tree など)
- 木のリーフノードは (ひとつだけデータを持っているわけではなく)
Vec<(Key, Value)>のような感じで、さらにKeyの順に並ぶように保っている- 中間ノードは同じく
KeyでソートされていてVec<(Key, 子へのポインタ)>を持つ
- 中間ノードは同じく
- ほぼすべての RDBMS で B+Tree が使われている (!)
- key に対応する value を検索: 中間ノードではどの子に降りるべきかが二分探索で分かり、リーフノードでもやはり二分探索できる
- key-value のペアを挿入
- ひとつのノードをひとつのページに対応付けて使う
- 検索・挿入時にたどるノード数 (= ページ数) はたかだか木の高さ
第 5 章: テーブルの実装
- テーブル (行と列からなる) を B+Tree に格納する
- 各行のプライマリーキー列を B+Tree の key に、それ以外の列を value に
- プライマリーキー (複合キーもありうる) → B+Tree key のエンコード方法によってはソート順がこわれる
- かしこいエンコーディング: Memcomparable format (すごそう)
- もしくは、B+Tree の比較関数をカスタムできるようにする
- クエリエクスキュータ
- テーブルをプライマリーキーで検索するもの・列の値で行をフィルタするもの、など
- 実行計画
- クエリエクスキュータの組み合わせ方を示す
idがプライマリーキーだとしてSELECT * WHERE id >= 'w' AND first_name < 'Dave'の場合は、プライマリーキーで検索したあとfirst_nameでフィルタする、など
第 6 章: セカンダリインデックスの実装
Writing A Compiler In Go を読んだ感想
- はじめに
- Chapter 1: Compilers & Virtual Machines
- Chapter 2: Hello Bytecode!
- Chapter 3: Compiling Expressions
- Chapter 4: Conditionals
- Chapter 5: Keeping Track of Names
- Chapter 6: String, Array and Hash
- Chapter 7: Functions
- Chapter 8: Built-in Functions
- Chapter 9: Closures
- Chapter 10: Taking Time
はじめに
Writing A Compiler In Go を読みました。
Rust による実装例です。
他の方の書評としては
- https://cipepser.hatenablog.com/entry/go-compiler
- https://junchang1031.hatenablog.com/entry/2018/12/23/081222
などがあります。
Writing A Compiler In Go は Writing An Interpreter In Go (以降ではインタプリタ本と呼びます) の続編です。インタプリタ本のマクロ以外を把握していることが必要とされます。Go の知識に関してはインタプリタ本に出てきた範囲を押さえておけば十分です。
本文を読むだけにするか、読みつつ手を動かしてソースコードを書くかで読了時間がけっこう変わります。テストコードとその説明が豊富なので読んで理解するだけでも楽しめると思います。Chapter 7, Chapter 9 などは stack の状態変化を図に描きながら進めると読みやすいです。
Writing An Interpreter In Go は和訳『Go言語でつくるインタプリタ』が出ているので、いつか『Go言語でつくるコンパイラ』も出版されるといいなと思っています。
ここでは、各チャプターの感想を記録しておきます。
Chapter 1: Compilers & Virtual Machines
コンパイラと VM の説明。そういうチャプターなので仕方ないけどソースコードがほとんど出てこないのでつらい。
なんとなく聞いたことのあった「VM」をちょっと知れたのはよかった。virtual machine (VM) は real machine の CPU で言うところの fetch-decode-execute cycle (instruction cycle) をソフトウェア的に実装したもの、という説明だった。JavaScript による、足し算引き算のみをサポートする VM の実装例 (擬似コード?) があったのでイメージしやすかった。
コンパイラは、AST を受け取って VM の入力となる bytecode (bytecode instruction) を吐く。この bytecode はソース言語 Monkey Language に存在しない機能はサポートしなくてよい。たとえば、Monkey Language には for 文や浮動小数点数がないのでこれらは考えなくてよい、ということだと思う。一般のプログラミング言語 (→ AST) → bytecode のような変換をするわけではないため。
他にも、本書ではなぜ (レジスタマシン型ではなくて) スタックマシン型の VM をつくるの？ → 実装がラクというのが理由のひとつ。などが書いてあって、大事なチャプターではあると思う。
Chapter 2: Hello Bytecode!
一気に REPL 完成まで持っていく。
登場する Opcode が OpConstant, OpAdd のふたつだけなので operand width をよく分かってなくても大丈夫かも。本を読み進めれば分かってくる気がする。
ユニットテスト用の helper 関数とかを実装することもあり行数はけっこうかさむ。Go でやるなら外部 package を使って assert.Equal とかしたほうがいいと思う。
Chapter 3: Compiling Expressions
四則演算、大小比較などを追加する。このチャプターから、チャプターごとに PR を分けていた。
おもしろポイントとしては、Opcode の種類数節約のために OpGreaterThan だけ用意して OpLessThan は無いという点。(Monkey Language) → (bytecode での表現) の形で書くとイメージは↓の感じ。
a > b→[OpGreaterThan, a, b]a < b→[OpGreaterThan, b, a]
Chapter 4: Conditionals
if 式を追加する。
if 式では if 節と else 節の片方だけを通るようにする必要がある。それはそうですが……。
たとえば、下のようなコードが無限時間かかると困る。
if (true) { // do nothing } else { sleep(9999999); }
したがって instruction を前からひとつずつ見ていくだけではダメで、以下のようにジャンプを使うとうまくいく。
Chapter 5: Keeping Track of Names
変数の binding (let x = ...) を追加する。
compiler では hash map で変数を管理するが VM ではパフォーマンスのために配列へのインデックスアクセスで変数を参照する。コンパイル時 hash map に追加した変数の順番を覚えておく感じ。
Chapter 6: String, Array and Hash
String, Array, HashMap を追加する。
そんなに難しいところはない。
Opcode OpArray は array の要素数を表すオペランドをひとつ持つ。VM ではその数だけ stack から pop して array object をつくる。pop した順番そのままだと逆順なので reverse しておく。
hash map について、デバッグしやすくするために hash 化前のキーも持つほうがよかった。
Chapter 7: Functions
関数を追加する。
いちばん難しいチャプターだと思う。実際 70 ページもある。
local bindings を実現するにはいくつか方法があると言うが、本書では VM の stack に穴を開けてそこを利用する。よくあるやり方らしい。
関数を実行する際には vm.sp より上の領域を使う。
ローカル変数の参照は「その変数が関数内で何番目に現れたか」をコンパイル時に計算しておけば stack から読み出せる。
関数から抜ける (return する) ときは図の Local 2, Local 1, Function を順に pop して掃除するイメージ。実際は vm.sp を減らすだけ。
他には arguments の扱いも学ぶ。引数がふたつある関数呼び出しでは Arg 1, Arg 2 がそれぞれ上図の Local 1, Local 2 に対応する。これらの引数以外にもローカル変数があれば Local 3, Local 4, ... のようになる。
Chapter 8: Built-in Functions
ビルトイン関数を追加する。
前のチャプターを済ませていれば、とくに詰まるところはないと思う。
Chapter 9: Closures
closure を追加する。
chapter 7 で関数は完成したかと思いきや、実は次のような使い方はできなかった。(めちゃくちゃ紛らわしい挙動だけど chapter 7 時点では addTwo(3) が 6 を返す)
let newAdder = fn(a) { let adder = fn(b) { a + b }; return adder; }; let addTwo = newAdder(2); addTwo(3); // => 5
この問題は、adder の定義時に a が 2 であったことを adder に覚えさせて解決できる。
より一般には、関数と自由変数 (= その関数に現れる、parameter でもローカル変数でもない変数すべて) を組にして扱うことで解決できる。
Chapter 10: Taking Time
fib(35) を求めるコードの実行時間を interpreter と VM とで比較する。
3 倍速くなるらしい。自分は interpreter を実装していないので比較できてない。
ところで、自分で実装した VM で fib(35) を計算すると、本書の実装によるものより 2 倍遅かった。ヘルプ。
