2022-08-31

しゃくとり法(尺取法)の適用範囲, 実装

しゃくとり法は主に競技プログラミングにおいてある条件を満たすような連続部分列 $[l,r) (0 \leq l \lt r \leq n)$ の個数を数えたり, 最大の長さを求めたり, 最小の長さを求めたりするのを $O(n)$ で行うアルゴリズムです. しゃくとり法の適用できる範囲と実装方法について考えてみました.

しゃくとり法とは

いま自然数 $n$ と連続部分列 $[l,r)$ に関するある条件 $P(l,r)$ が与えられているとします. インデックスは0-indexedで半開区間を考えているとします. しゃくとり法が適用可能な条件は次の二つのいずれかの場合です.

条件1: $P(l_1,r_1)$ が真のとき, $l1 \leq l2 \lt r2 \leq r1$ ならば $P(l_2,r_2)$ も真である.
条件2: $P(l_1,r_1)$ が真のとき, $0 \leq l2 \leq l1,r1 \leq r2 \leq n$ ならば $P(l_2,r_2)$ も真である.

すなわち条件1はある部分列が条件を満たすとき, その中の任意の部分列が条件を満たすということを意味しており, 条件2はある部分列が条件を満たすとき, それを含む任意の部分列が条件を満たすということを意味しています.

条件1と条件2は条件 $P(l,r)$ の真偽を入れ替えることで互いに移り変わるため, これを区別することに意味はないように見えますが, 条件1の場合では $P(l,r)$ を満たす部分列の最大の長さをしゃくとり法で求めることが可能で, 条件2の場合では $P(l,r)$ を満たす部分列の最小の長さをしゃくとり法で求めることが可能であるため, この区別には意味があります.

しかし, 条件1と条件2の両方の場合でしゃくとり法の実装も考え方もほとんど同じなので以下では条件1について説明してみます.

しゃくとり法の実装

以下のようなアルゴリズムで条件1を満たす連続部分列の数え上げ or 最大の長さをもとめることができます. これをしゃくとり法といいます.

int n; 

int count = 0; // 数
int max_length = 0; // 最大の長さ
int r = 0;
for (int l = 0; l < n; l++) {
    while (r < n && P(l,r+1)) {
        r++;
    }
    count += r - l;
    max_length = max(max_length, r - l);
    if (r == l)
        r++;
}

正当性を考えてみます. while ループでは $l$ を固定して条件を満たす限り r++ としています. while ループが終了したとき,

r = n (すなわち $P(l,n)$ は真)
r < n かつ $P(l,r)$ は真かつ $P(l,r+1)$ は偽である

のいずれかということがわかります. r = n なら (lを固定した時の)数え上げ, 最大の長さともに正しいことがわかります. r < n のときも $P(l,r+1)$ は偽であることから条件1より $r \lt x \leq n$ ならば $P(l,x)$ は常に偽であることがわかるのでこの場合も(lを固定した時の)数え上げ, 最大の長さともに正しいです.

さらにl+1としたとき,

r = n
r < n かつ $P(l,r)$ は真かつ $P(l,r+1)$ は偽である
$P(l,l+1)$ は偽かつr = l+1

という状態です. r = n ならば $l \lt l+1$ より $P(l+1,r)$ は真であるのでよいです. r < n かつ $P(l,r)$ は真かつ $P(l,r+1)$ は偽ならば $P(l+1,r-1)$ は必ず真であるのでこのrから始めても良いです. また $P(l,l+1)$ は偽かつr = l+1の場合も当然問題ないです. よって以上より正当性がわかりました.

またアルゴリズムで r は0からnまでインクリメントしかされないためwhileは合計で $O(n)$ 回しか回らないため, 計算量は $O(n)$ です.

これでOK?

これで一件落着な気がしますが, うえの計算量の仮定は $P(l,r)$ が $O(1)$ で計算できるという仮定に基づいていました. これは多くの場合嘘です.

そのため連続部分列 $[l,r)$ に関する情報を何らかの形で保持しておきl,rをインクリメントしたときにいい感じに情報を捨てたり, 取り込んだりできるようにしたいです. これは実は連続部分列 $[l,r)$ に関する情報が群で表されるときに可能です(多分?).

すなわち今まで $P(l,r)$ と書いていたものが次のように書けるとします.

Aを長さnのある群 $G$ の要素からなる配列とする. すると $f(l,r) = A[l] \cdot A[l+1] \cdot \dots \cdot A[r-1]$ なる関数を考えることができる. 群 $G$ の要素 $g \in G$ に対する条件 $P(g)$ があり, $P(l,r) = P(f(l,r))$

するとつぎのようなアルゴリズムでしゃくとり法を実装できます. ただし群の単位元を $1$ , 演算を $op(a,b)$ , 逆元を $1/a$ のように書きます.

int n;
vector<Grp> A(n); // なんか入力

Grp g = 1; // 単位元
int count = 0; // 数
int max_length = 0; // 最大の長さ
int r = 0;
for (int l = 0; l < n; g = op(1/A[l],g),l++) {
    while (r < n && P(op(g,A[r]))) {
        g = op(g,A[r]);
        r++;
    }
    count += r - l;
    max_length = max(max_length, r - l);
    if (r == l) {
        g = op(g,A[r]);
        r++;
    }
}

これが多くの場合にしゃくとり法が適用可能な場合だと思います(多分). たとえば以下の問題は次のような群と条件 $P$ を考えるとできます.
※ネタバレ注意

AOJ The Number of Windows
$G = (\mathbb{Z},+,0),P(g) = (g \leq x)$
Atcoder ABC032 C 列
$S[i] = 0$ であるものがある場合答えが明らかに $n$ になるのですべて $S[i] > 0$ としてよく. $G = (\mathbb{R}_{> 0},\times,1),P(g) = (x \leq K)$

いちおうライブラリみたいなのもつくりました. なんですが, しゃくとり法は貼るだけで解くみたいなことは厳しいと思っているので(これとか), 貼るというよりどのような場合に適用可能なのかとどうやって実装するかを理解しておくのが良いのではないかと思いました.

おわりに

しゃくとり法に苦手意識があったため, 適用できる条件と実装の仕方について考えてみました.

2022-03-21

データベースを設計する

今までもデータベースは触っていたのですが、データベースの設計についてはあまり知らなかったため、

gihyo.jp

を読んで実際にデータベースを設計してみました。データベース設計は概念データモデリング、論理データモデリング、物理データモデリングの3つの工程からなります。この3つを順にやっていくことにします。題材として「本好きのためのSNS」というアプリのためのデータベースをつくることにしてみます。

概念データモデリング

概念データモデリングとは

システム化の準備として、対象範囲にある業務プロセスと関連するデータ項目をすべて洗い出し、業務とデータ項目の関係をデータの集合体のレベルでモデル化すること

です。要するにシステムの対象となるデータとプロセスを明確にすることです。今回の例では次のようにしておきます。

f:id:hedwig1001:20220319164825p:plain — 概念データモデル

ER図のリレーションっぽく書いていますが、そこまで厳密な意味をもっては書いてないです。

論理データモデリング

論理データモデリングの目的は2つあり

信頼性の高いデータを格納する

将来にわたって一元的にデータを管理できること

です。一つ目の「信頼性の高いデータ」とはデータの不整合が発生しにくいデータの持ち方のことです。例えばある本の名前をbooksという本のデータを持つテーブルとreadというユーザがどの本を読んだか管理するテーブルの両方で管理していたとします。このとき本の名前を変えようと思ったときに 2箇所のデータを間違いなく変更しなければなりません。もしミスがあれば不整合が発生することになります。このような重複をなくすようにデータを持ちます。このような作業は「正規化」と呼ばれることがあります。

2つ目はルールの変更などに強い安定したデータ構造を作るということです。たとえば本のジャンルが一つの本につき一種類しか登録できないとします。しかしある都合で、一つの本に複数のジャンルを登録したくなりました。このようなルールの変更が起こってもできるだけデータベースの変更をせずに済むような構造にするということです。

正規化

とりあえず概念データモデリングが終わって次のような感じでデータを持とうと考えていました。

ユーザ

ユーザ(R)
PK	user_ID	整数
	username	文字列
	password	文字列

フレンド(R)
PK,FK	follower	整数
PK,FK	followee	整数

メッセージ

メッセージ(E)
PK	message_id	整数
FK	sender_id	整数
FK	receiver_id	整数
	content	文字列
	send_at	時刻

オープンメッセージ

オープンメッセージ(E)
PK	open_message_id	整数
FK	sender_id	整数
	content	文字列
	send_at	時刻

本(R)
PK	book_id	整数
FK	author_id	整数
FK	genre_id	整数

ユーザ本(E)
PK,FK	user_id	整数
PK,FK	book_id	整数
	thoughts(感想)	文字列
	read_at	日付

筆者(R)
PK	author_id	整数
	name	文字列

ジャンル(R)
PK	genre_id	整数
	name	文字列

ここから正規化を施していきます。プライマリーキーが一意となるようにするのが第一正規化です。これはプラマリーキーを考えながらつくると達成されてしまっていました。

つぎに複合キーに関する重複を排除します。複合キーのうちなかのあるキーを決めるとそれ以外のキーで一意に決まってしまうアトリビュートがある場合はそれを別のエンティティに分離します。これを第二正規化と言います。これもこのなかにはありません。

最後に非キー同士の重複を排除します。つまりある非キーがきまるとそれから一意に決まってしまうアトリビュートがある場合はそれを別のエンティティに分離します。これを第三正規化と言います。これもこの中にはありません。

software designの記事を一回全部読んでから実際にデータベースを設計したらどうなるんだろうとおもってやってみましたが、読んだ知識にすでに影響を受けて正規化してしまっているような気がします。

何はともあれ、正規化してから作成したER図が以下です。

f:id:hedwig1001:20220319183329p:plain — ER図1

つぎに最適化を行うのですが、扱うエンティティの数がそれほど多くなく、すべてのエンティティを同時に正規化してしまったので飛ばします。

ビジネスルール検証

システム上のルールに従っているかを確認するのがビジネスルール検証です。ここで一つの本に一種類のジャンルしかつけられるようになっていないことに気づきました。「一つの本に複数のジャンルをつけられるようにする」というルールとこれは矛盾します(このルールは概念データモデリングで決めておくべき)。そのため books_genres のような多対多のテーブルを用意することにしました。

安定性検証

つぎに将来の変化に対して強いデータ構造にするのが安定性検証です。ここではプライマリーキーの安定性検証をしたいと思います。たとえば「ユーザ本」のエンティティを見ると、user_id,book_id で複合キーとしています。これではたとえば同じ本を2回読んだことを登録することはできません。これにはほかの read_id といったPKを新たに作って user_id,book_id を非キーとすることで対応できます。

これらの作業の後に綺麗に作り直したER図が以下になります。

f:id:hedwig1001:20220319185059p:plain — ER図2

これをもとに物理データモデリングを進めていきます。

物理データモデリング

物理データモデリングの目的は

データ構造の安定性を保ちながらRDBMSに実装できる「動くデータベース」にすること

です。まず論理データモデリングで作成した図を用いてCRUD図を書きます。これを書くことでプロセスとデータの関係性が目に見えてわかるようになります。

	User	Book	Author	Genre	Read	Follow	Message	OpenMessage
ユーザ登録	C
ユーザログイン	R
ユーザ画面作成					R	R	R	R
ユーザ消す	D				D	D	D	D
読んだ本を登録	U	C	C	C	C
読んだ本の情報を更新	U	U	U	U	U
本を検索		R	R	R
10年経過		D	D	D
フレンド追加						C
フレンド削除						D
メッセージ送信							C
オープンメッセージ送信								C

ユーザ画面作成のところが少しざつですが、上のような感じになります。上の図ですべてのエンティティにC,Dがあることなどを確認します。また、イベントエンティティとリソースエンティティに分けて、プロセスを上からイベントエンティティを左から発生順に並び替えてCが左上から右下に並んでいくことを確認します。

	Read	Follow	Message	OpenMessage	User	Book	Author	Genre
ユーザ登録					C
ユーザログイン					R
読んだ本を登録	C				U	C	C	C
読んだ本の情報を更新	U				U	U	U	U
本を検索						R	R	R
フレンド追加		C			U
フレンド削除		D
メッセージ送信			C		U
オープンメッセージ送信				C	U
ユーザ画面作成	R	R	R	R
10年経過						D	D	D
ユーザ消す	D	D	D	D	D

テーブル設計

つぎにテーブルを実際に設計していきます。これにはテーブル名、カラム名、データ型、制約、インデックスをどのようにするか決める作業が含まれます。ここでは必須項目にNOT NULL制約、また同じジャンルが複数登録されることを防ぐための一意性制約などをつけました。またER図のリレーションに沿って外部キー制約をつけます。UPDATE時の挙動やDELETE時の挙動を決める ON UPDATE ~, ON DELETE ~ は基本的に依存リレーションならば CASCADE, 非依存ならば RESTRICT を指定します。

これらのことを行なってできたのが以下です。

CREATE TABLE users (
    user_id INTEGER PRIMARY KEY,
    username VARCHAR(64) NOT NULL,
    password VARCHAR(128) NOT NULL
);

CREATE TABLE authors (
    author_id INTEGER PRIMARY KEY,
    name VARCHAR(64) NOT NULL UNIQUE
);

CREATE TABLE genres (
    genre_id INTEGER PRIMARY KEY,
    name VARCHAR(128) NOT NULL UNIQUE
);

CREATE TABLE books (
    book_id INTEGER PRIMARY KEY,
    author_id INTEGER NOT NULL,
    name VARCHAR(128) NOT NULL UNIQUE,
    FOREIGN KEY (author_id) REFERENCES authors(author_id) ON DELETE CASCADE
);

CREATE TABLE books_genres (
    book_id INTEGER NOT NULL,
    genre_id INTEGER NOT NULL,
    PRIMARY KEY(book_id,genre_id),
    FOREIGN KEY (book_id) REFERENCES books(book_id) ON DELETE CASCADE,
    FOREIGN KEY (genre_id) REFERENCES genres(genre_id) ON DELETE CASCADE
);

CREATE TABLE reads (
    read_id INTEGER PRIMARY KEY,
    user_id INTEGER NOT NULL,
    book_id INTEGER NOT NULL,
    thoughts VARCHAR(1024),
    read_at DATE NOT NULL,
    FOREIGN KEY (user_id) REFERENCES users(user_id) ON DELETE CASCADE,
    FOREIGN KEY (book_id) REFERENCES books(book_id) ON DELETE CASCADE
);

CREATE TABLE follows (
    follower_id INTEGER NOT NULL,
    followee_id INTEGER NOT NULL,
    PRIMARY KEY(follower_id,followee_id),
    CHECK (followee_id <> follower_id),
    FOREIGN KEY (follower_id) REFERENCES users(user_id) ON DELETE CASCADE,
    FOREIGN KEY (followee_id) REFERENCES users(user_id) ON DELETE CASCADE
);

CREATE TABLE messages (
    message_id INTEGER PRIMARY KEY,
    sender_id INTEGER NOT NULL,
    receiver_id INTEGER NOT NULL,
    content VARCHAR(1024) NOT NULL,
    send_at TIMESTAMP WITH TIME ZONE NOT NULL,
    FOREIGN KEY (sender_id) REFERENCES users(user_id) ON DELETE CASCADE,
    FOREIGN KEY (receiver_id) REFERENCES users(user_id) ON DELETE CASCADE
);

CREATE TABLE open_messages (
    message_id INTEGER PRIMARY KEY,
    sender_id INTEGER NOT NULL,
    content VARCHAR(1024) NOT NULL,
    send_at TIMESTAMP WITH TIME ZONE NOT NULL,
    FOREIGN KEY (sender_id) REFERENCES users(user_id) ON DELETE CASCADE
);

-- view
CREATE VIEW book_author (
    book_id,
    book_name,
    author_name
) AS 
SELECT
    b.book_id,
    b.name AS book_name,
    (SELECT a.name FROM authors AS a WHERE a.author_id = b.author_id) AS author_name
FROM books AS b;

最後のビューはよく使うと考えられるため追加しました。

インデックス設計

次にインデックス設計を行います。(ここではインデックスはB木インデックスということにします)。RDBMSにインデックスをつけるメリット、デメリットとしては

メリット

WHERE句で特定のデータに絞るようなSELECTなどで高速化できることが期待できる。

デメリット

インデックスは定義しても使われない場合があり、ディスクが無駄になる
更新、削除の際のコストは大きくなる。

があります。そのためインデックスをどこにつけるか/つけないかは効率化の上で考えるべきことですし、実際に効果があるかは実際のデータの分布などをみて決めないといけません。

ところで別の本*2にはインデックス作成の方針として

外部キー制約で参照されているすべての列にインデックスをつける。

といったことが書いてありました。なぜなら親行を消すときにかならず子行を参照するようになっているかららしいです。また外部キー制約がつくところで JOIN することが多いということもあるのではないかと思っています。

そこで実際に上のようにインデックスをつけることでクエリの実行時間に変化があるかをみてみたいと思います。上のテーブルとそれにインデックスとして

CREATE INDEX books_01 ON books (author_id);
CREATE INDEX books_genres_01 ON books_genres (book_id);
CREATE INDEX books_genres_02 ON books_genres (genre_id);
CREATE INDEX reads_01 ON reads (user_id);
CREATE INDEX reads_02 ON reads (book_id);
CREATE INDEX follows_01 ON follows (follower_id);
CREATE INDEX follows_02 ON follows (followee_id);
CREATE INDEX messages_01 ON messages (sender_id);
CREATE INDEX messages_02 ON messages (receiver_id);
CREATE INDEX open_messages_01 ON open_messages (sender_id);

を追加したものを比較してみます。テストデータとして約3万件の SELECT と INSERT 文を別に実行してみて time コマンドで実行時間(ディスクI/Oの待ちをみるため, real)を5回計測して平均を取ります。色々ファイル書き込みとかのオーバーヘッド込みですが簡易的なものということということで許してください。

実行環境は

MacBook Air (Retina, 13-inch, 2018),1.6 GHz デュアルコア Intel Core i5
PostgreSQL 13.3

です。詳細なコードはこちらを参照してください。結果は以下のようになりました。

	1回目/s	2回目/s	3回目/s	4回目/s	5回目/s	平均/s
インデックスなし(`INSERT`)	6.705	10.332	11.074	8.228	11.562	9.5802
インデックスなし(`SELECT`)	4.225	4.570	4.259	4.579	7.063	4.8752
インデックスあり(`INSERT`)	10.657	7.979	7.129	9.352	10.667	9.1568
インデックスあり(`SELECT`)	3.879	2.862	2.933	3.087	2.983	3.1488

ばらつきはすこしあるようですが、SELECT ではインデックスありの方が平均的に早いように見えます。INSERT では差は小さいもののインデックス有りの方が少し早いです。検定などをして厳密に評価したわけではないですが、外部キーを参照している列にインデックスをつけることの効果はたしかに感じることができます。

おわりに

データベース設計はむずかしいし、奥が深い作業であるとわかりました。データモデリングチェックリストにはもっと多くの確認すべき項目があって、実用に耐えうるデータベースをつくるのはたいへんなのだろうと感じました。

*1:図はdraw.ioで作成しました。以降の図も同様です。

*2:https://www.oreilly.co.jp/books/9784873119588/

2022-03-15

Cコンパイラを自作してセルフホストしました

タイトル通りなのですが、CでCのコンパイラを書いてとりあえずセルフホストできるところまでできたのでブログにこれまでやったこととかを残しておこうと思います。作ったものは以下のリンクから見れます。

github.com

どうやって作ったか

これをつくろうと思ったきっかけとして、まず低レイヤを知りたい人のためのCコンパイラ作成入門があります。このサイト自体は未完成らしいのですが、初めのほうでコンパイラ作成の基本的な部分(トークナイズ、パース、コード生成)についてわかりやすく解説しており、コンパイラにそれほど詳しくなくてもコンパイラを作り始めることができます。

このサイトの最初の方で自分のコンパイラが正しく計算結果を出力するのを目にして、さらに段々機能を付け加えていくとだんだんC言語に近づいていくのがとてもおもしろかったため、楽しくつづけることができました。

蛇足ですが(コンパイラ作成とは直接は関係ないですが)、この本で推奨されているインクリメンタルな開発の仕方は常に完成した状態で開発を進めることができるのでいきなりハードルがあがるということがなくてよかったです。

上に書いたように、このサイトでは途中でおわっています。この時点ではまだセルフホストはできないため、セルフホストするためにはさらに機能を追加する必要があります。さらに機能を追加する際には

The syntax of C in Backus-Naur form を見て, 追加したい機能に対応するBNFを確認して
Compiler Explorerでその機能はどのような使い方が許されるのかを確認して
実際にコードを書く

ということを繰り返していきました。ちなみにセルフホストまでに必要な機能としては(自分の場合は)

構造体定義 .,->
++var,--var,var++,var--
void,bool
break,continue
switch ~ case ~ default ~
enum
charのリテラル, エスケープシーケンス
%,<<,>>,|,&,||,&&,! と三項演算子
+=,-=,*= 系
typedef
可変長引数
(簡単な)キャスト

などでした。ちなみに今のところマクロ展開とリンクはサポートしていないため

gccにマクロ展開してもらう
マクロ展開したものを自分のコンパイラでコンパイルする
それらをgccでリンクしてもらう

のようにしてセルフホストしました。また最適化等は全く行っていません。

f:id:hedwig1001:20220315102938p:plain — セルフホストしてhcc2とhcc3が同じであることを確認した

面白かったポイント

なんといっても自分の書いたコードでコンパイルできるものが増えていくのを見るのがとても面白いです。はじめはただの計算しかできなかったのにfor文, 配列, 構造体などと追加していくとコンパイルできるコードが増えて、だんだん自分のコンパイラが成長しているのを感じることができます。成長過程をリンクで貼っておきます。

セルフホストできたときの感動もひとしおでした。

つらかったポイント

セグフォ

これはCで書くなら仕方ないかもしれないですが, ヌルポインタにアクセスしようとするとセグフォします。できるだけそれは防ぎたいのでエラー処理はしますが、完全に防ぐことはできないためセグフォすることがあります。そのためエラー出力を適当な箇所に入れて、セグフォしても「ここまでは正しく動いているはず」ということがわかるようにしました。

またコンパイラを書いているのでセグフォは自分の書いたコンパイラがコンパイルしたアセンブリを実行しようとした時も起こる可能性があります。こうなったらまずアセンブリを見てどこでセグフォしているか確認します。これでわかればokですがわからない場合はgdbで実行してどの行でセグフォしているか確かめてコードを修正していました。

可変長引数

構造体やenumの追加も比較的スムーズにできたのですが、可変長引数の実装にすこし苦戦しました。そもそも va_list,va_start とかは stdarg.h で定義されていると思っていたのですが、これらの実態は __builtin_hogehoge というやつらでこれはコンパイラが実装するものだとわかりました。なのでこれらを実装しなければなりません。そのために

などを参考にしました。これらをみてもよくわからないところは前述のCompiler Explorerをつかってアセンブリを実際に出力してみて、どうなっているか確かめたりしました。vfprintf() を使っているので gcc と互換性があるように実装する必要もあると思います。

また関数呼び出しで引数の数が6個以下(すべて整数orポインタ)だと引数はレジスタにセットするのですが、6個より多いとスタックにpushします。自分のコードでは7個以上の引数を持つ関数呼び出しがあったため、これもサポートしました(可変長とは関係なかった)。

知見

コンパイラ作成の過程でいろんなことを知りました。

C言語について詳しくなった

コンパイラをつくるにあたって, どういう書き方が許されてどういう書き方が許されないのかを考えることになります。そのため, C言語についての知識が増えます。たとえば

int a=1,b=2;
a,b = b,a;

という書き方はCでは合法なのですが, これはPythonの時のように a,b をスワップするという意味にはなりません。Cではexpression(正確にはassign)をカンマ区切りで何回か並べたものをexpressionとしています(くわしくは The syntax of C in Backus-Naur form を参照してください)。そのため上のコードは a; b = b; a; を並べたものと同じです。なのでスワップではなく a,b の値は変化しないということになります。

またCの構文解析がしにくいというのも身をもって実感しました。たとえば

int a;
int f(int x) { ...

の二つを考えると int f(.. のカッコにくるまで変数の定義をしているのか, それとも関数の定義をしているのかわかりません。できるだけ最初の1文字を読んだ時点でなにをパースしようとしているのかはわかると楽です。Pythonは def ... ですし, Goは var ... ,func ... ですし Rustも let ..., fn ... でこれが考慮されているらしいことがわかります。Cは昔の言語なのでしょうがないですが, Goは構文解析しやすいようにつくられているという話もなるほどなと納得できました。

アセンブリをかけるようになる。

あまりアセンブリを書いたことがなかったため, 実践的低レイヤプログラミングをみてちょっと勉強してから始めたのですが, コンパイラを作っていく過程でアセンブリを生成することになるのでアセンブリの知識がつきます。

結局アセンブリは

データを動かすmov
計算する add,sub,cmp
ジャンプする je,jmp

の3種類がほとんどで、これらを組み合わせてプログラムは動いているのだなとわかりました。

f:id:hedwig1001:20220315111103p:plain — アセンブリを見てデバッグ!

プログラムが実行される様子が(なんとなく)わかる

関数呼び出し, どのように配列アクセスしているのか, 構造体はどのようにメモリ上にのっているのか, 構造体の->は何をしているのか, 参照を渡すとはどういうことか, ポインタとはなんなのか, etc. についてきちんと理解することができます。理解しないとコンパイラが書けないので。いままでブラックボックス化していたものをひとつづつ明らかにしていく感じがありました。

いまはまだ何に役に立つかはわかりませんが, 省メモリなプログラムを書いたり, 効率の良いプログラムを書いたりするのに役立てられれば良いなと思っています。

展望

セルフホストはしましたが, 実はまだ結構サポートしていない機能や中途半端な実装になっているところがあります。

structの引数, 値渡し, 初期化式
const-expressionをコンパイル時にきちんと評価する
unsigned系
short,long,_Bool
staticの関数をファイルスコープにする
enum,typedef,local variableの同じスコープで同じ識別子となるものを宣言できないようにする。
関数ポインタの型をきちんと実装する。
#define #include とかのマクロ展開
浮動小数点数

などです。これらの機能も追加していけたら良いなと思っています。

おわりに

コンパイラ作成は面白いと思うので, 低レイヤを知りたい人のためのCコンパイラ作成入門読んでやってみてください!

2022-02-20

TCP/IPをGoで自作しました。

タイトルにある通りですが、TCP/IPのプロトコルスタックをGoで実装しました。デバイス, IP, ARP ...などと実装してとりあえずTCPの最低限の機能までは実装したため、ここに書いておこうと思います。つくったものは以下になります。

github.com

経緯

大学の授業やhttpあたりを勉強しているとTCP/IPという単語が登場します。マスタリングTCP/IPを一通り読みましたが、実装することでわかることは多いだろうということで実装してみました。実装に当たっては

3月に開催したプロトコルスタック自作キャンプの講義資料を公開しました。1週間でTCP/IPのプロトコルスタックを自作してUDPやTCPで通信するアプリケーションを動かすという内容で300ページくらいのスライドです。これがあれば一人で自作できますよ！ #KLabExpertCamp https://t.co/4sUTh2MAk6
— YAMAMOTO Masaya (@pandax381) 2021年4月20日

を参考にさせていただきました。Cで実装するかGoで実装するか迷いましたが、Goにもっと慣れたいというのとchannel,goroutineを使っていい感じに並行処理してみたいということでGoで書くことにしました。

ちなみにまったく5日では終わらず、約2週間ほどかけて実装しました。実装していく中で知らなかったGoの便利なライブラリや、Linuxのデバイス周りのこと、デバイスやプロトコルの抽象化の方法などネットワークとは直接関係ない部分についても知見が得られました。

実装したもの

デバイスからEthernet, IPv4,ARP,ICMP,UDP,ICMPなどの主要なプロトコルの機能の一部を実装しました。デバイスなどの下のレイヤから実装していきました。最終的にTCPでthree-way hand shakeができたときは「あのthree-way hand shakeができた...」と感動を覚えました。

f:id:hedwig1001:20220220151954p:plain — three-way hand shake

しかし、現状では「TCPはヘッダのオプションを無視している、IPフラグメンテーションに対応していない」などの問題があり、実装すべきところはまだあるかなという感じです。

知見、苦労したところ

デバイスまわり

まず最初の関門がデバイス周りでした。デバイスとしてはLinuxのtapデバイスを用いています。tapデバイスについて書かれた本家のドキュメントはおそらく https://www.kernel.org/doc/Documentation/networking/tuntap.txtです。これと Man page of NETDEVICEを参考にしつつ、Goのsyscallパッケージを使ってlinuxのシステムコールをよぶことで実装します。

より具体的には ifreq 構造体をつくって適切なシステムコールを読んで、その情報を取り出すということを行います。この辺のデバイスやシステムコールを触ったことがなかったため苦労しました。tapデバイスを理解するためには Linux bridge、Tapインタフェースとは - passacagliaや自作プロトコルスタック（全体像の理解〜ARPリプライ） - おしぼりの日常を読みました。とくに前者の記事でtapデバイスとはそもそもなにか、後者の記事でデバイスの具体的な動作について理解が深まったような気がします。

binaryパッケージ

ネットワークを勉強したことある方はご存知だと思いますが、ネットワークを流れるパケットはビッグエンディアン、多くのハードウェアはリトルエンディアンで動きます。これは32bitや16bitの数をどのような順で並べるかという話です。このバイトオーダーの変換にGoの binary パッケージが有用でした。下位プロトコルのペイロードをヘッダにパースする際に「ビッグエンディアン -> リトルエンディアン」と変換する必要があるのですが、TCPヘッダ構造体のフィールドをヘッダの上から順に並ぶようにしておき、

var hdr TCPHeader
r := bytes.NewReader(payload)
err := binary.Read(r, binary.BigEndian, &hdr)

とすることで実現できます。逆にヘッダ->バイト列の変換も簡単です。「ヘッダ <-> データ」の変換はよくでてくるので便利でした。

TCP

TCPの実装が大変でした。TCP/IP プロトコルスタックを自作した - kawasin73のブログのブログを見て、僕もRFC793を読んでみることにしました。RFC793は91ページあったのですが、21ページ以降のFUNCTIONAL SPECIFICATION以降を中心に読み、58ページ以降のEvent Processingを実装していくという感じでした。

TCPはデータが送られたことを確認するためにシーケンス番号を持ちます。シーケンス番号はTCPの送ったペイロードのバイトサイズ分だけ大きくなります。実はそれだけでなく、SYNとFINを送った時にもシーケンス番号が1だけ増えます。これはSYNとFINが再送されたり、きちんとACKが返ってくることを保証するためです。これは26ページに書いてあります。

FINがあったときにシーケンス番号を増やすというこの仕様をきちんと読めていなかったためうまく動かず、micropsの方を見てバグに気づきました。仕様は隅から隅まで読まなければ正しく実装できないのだということを実感できました。

おわりに

TCP/IPをGoで実装して、デバイス、ネットワーク、Goについての知識が得られました。一石三鳥くらいあると思うので面白そうだと思った方はぜひやってみてはどうでしょうか。

2022-02-04

mainからgoroutineの終了を通知する

下で書いたやり方でもできるけど同じことはcontext.Contextを用いて行った方が筋が良いらしい

main関数にあるgoroutineが終了したことを通知するにはsync.WaitGroup()を使えば良いです。しかし, maiinからあるgoroutineに終了通知をするには同様にはできないため, 別の方法を使う必要があります。doneという終了通知チャンネルを用意してそれをつかうことで実現できます。

package main

import (
    "fmt"
    "time"
)

func protocol(ch chan int, done chan struct{}) {
    for {
        select {
        case a := <-ch:
            // aをパケットだと思って処理
            fmt.Println(a)
        case <-done:
            fmt.Println("done")
            return
        default:
            continue
        }
    }
}

func main() {
    ch := make(chan int, 10)
    done := make(chan struct{})

    // 通信開始
    go protocol(ch, done)

    for i := 0; i < 7; i++ {
        ch <- i // パケットがネットワークを通じて届く
        time.Sleep(time.Second)
    }

    // 通信終了
    close(done)
}

select 文の中身がa := <- chと<-doneで入れ替わらないようにしましょう。

2021-10-03

prmlを実装しました

機械学習

なんで実装したのか
よかったこと
展望
終わりに

prml(Pattern Recognition and Machine Learning)をpythonで実装しました。パターン認識と機械学習, 通称prmlはベイズ的な機械学習の教科書として有名ですがこの本に載っているアルゴリズムを実装しました。gitリポジトリにあります。まだ完璧にすべて実装したわけではないですが、とりあえず 14章まで一通り実装し終わり、区切りがいいのでブログ記事を書きます。

f:id:hedwig1001:20211003152319p:plain — rvmでの予測

なんで実装したのか

prmlを一通り読み演習問題も文中で示されているものは解いたもののやっぱり実装してほんとうにうまくいくのかとか試してみたかったからです。 prmlは有名な本なので先人たちがいろいろと実装していますがそれを見るだけでは意味がないので自分で実装しようと思いました。

よかったこと

意味がわからなかったところがわかるようになった

ハイブリッドモンテカルロのところやRVMなどの理解が深まりました。前にprmlを読んでいたときは結局ハイブリッドモンテカルロってどうやってサンプリングするんだ??となっていましたが実装するという観点で読み直すことでサンプリングの仕方や周辺の数学的なことの理解が深まりました。

またRVMは本当に予測に必要なデータ点がトレーニングデータの10%ぐらいになっていて感動します。

numpyの仕様にすこし慣れた

numpyのブロードキャストとかの仕組みをいまいち理解していなかったんですが、この実装をしていく上でブロードキャストがどういうふうに動くかがとてもわかるようになってきました。ほかにも axis とか4次元とかになると微妙に慣れづらいところも理解が進みました。

その他副次的なこと

sphinxでdocumentをつくったり, docstringの書き方やライセンスの種類などをほんのちょっとだけですが知ることができました。

f:id:hedwig1001:20211003152831p:plain — ハイブリッドモンテカルロによるサンプリング

展望

ニューラルネットワークの章はまだ十分ではないと思うのでそのあたりといろいろとうまくいっていない実装があるのでそのあたりを直したいです(EP法, ロジスティック回帰の混合モデル　など)。

終わりに

ちょっと数学的に面白いと思ったところや工夫ポイントは別の記事に書こうかなと思っています。

2021-05-25

Shopee参加記2

kaggle

shopeeの上位解法の自分用まとめ

GitHub - hedwig100/kaggle-shopee: kaggleのshopeeコンペのレポジトリ

↑自分のリポジトリ

1位

Shopee - Price Match Guarantee | Kaggle

モデルのスコアの伸びより, embeddingsを後処理した方がスコアが伸びた.
eca_nfnet_f1とbertをもちいてarcfaceをつかった
大きいマージンの方が良かったが大きすぎると収束しなかったため, だんだんマージンを大きくした.
最後の重みそうだけ学習率を大きくすると収束するようになったし, Cvもよくなった.
テキスト, 画像のみでそれぞれ類似度を測るのと, テキストと画像の類似度の和で類似度を測った.
Iterative Neighbor Blending(類似度の重みをつけた辺をはってグラフを作り, 類似度が近いもの同士が同じグループに分けられるようにグラフを作り替える. -> またテキストと画像の類似度から近いものを見つける -> を繰り返す.) が効いた.
cutmixが0.1くらい効いた
augmentationはhorizontal flipしかしていない.
後処理のINBが一番重要らしい.

3位

いい感じのモデルを使ってembeddingをつくって近傍をつくる.
そのembeddingsの距離や周りの点の密度などを特徴としてcatboostでpairwiseに同じ製品かどうか判定する.
つまり embeddings -> catboost -> 同じかどうか判定　ということをした.
embeddingを作るモデルをtriplet lossでfine tuningした.

4位

infoldなものもvalidation setとして用いた(leakしてるけど)
image,bert,tfidfをつかった
Query Expansionをした. これも近傍をグラフみたいに探索することらしい.
GeM = Generalized-mean poolingのことらしい.

5位

Shopee - Price Match Guarantee | Kaggle

6位

www.kaggle.com

imgとtextのfeatureをつくってからlinearしたのが効いた.
img,text,concatの三つのembeddingsをつかった
一つではなくてかならず2つ以上は同じ商品だと判定するようにした.
単位が合わないものは取り除いた.
学習率をfcとbert(本体)で変えた.
少なくとも2つは同じものが存在するは確かにってなった.
ことなる学習率を使うのは重要らしい.

8位

Shopee - Price Match Guarantee | Kaggle

$\alpha$ QEとDBAというものを使った.

18位

https://www.kaggle.com/c/shopee-product-matching/discussion/237972

近傍の数の分布をtrainとtestで合わせるというところがなるほどとなった.

ほかにも読んだが長いので割愛.

感想

Bert,nfnetあたりは入賞者はほとんど全員使っていた.
学習率の調整が必要なのは初めて知った.
post processが大事だった.
グラフみたいな構造に注目するのはたしかに正しかったが, 深く考えずに全結合にするだけでは意味がなかった.
クラスターみたいな構造に注目するのは大事だったらしい.
同じ商品だと予測したものが一つもない時に2個目を見つけるのは重要だったっぽい.
QEとかDBAとかそういうことはぜんぜんdiscussionでは言われてなかった気がするけどそういう知識はどこから手に入れているんだろう.