みんなのデータ構造 / Pat Morin

新年度始まって桜の満開の便りを聞き、なんとも落ち着かない今日この頃です.

前にも書きましたが情報系の学問を全く学ばずに今の職につきました.

そんなため、ソースコードを読んでいくうちにデータ構造の知識が必要だなぁ、
と最近思いまして、遅まきながらこの本読み始めました.

この本の読み方

本の冒頭の訳者まえがきにこの本の読み方が書かれてます.

ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
本書の内容がだいたいわかるようになれば良いエンジニアになれる。
わからない部分は飛ばして良い。

とあります, 納得です.
特に最後の部分はなんか気が楽になります…数式結構多いですからね…

数学的背景

この本では結構数式が使われているため、最初の部分で必要な数式についてしっかり説明があるのがうれしいです. 数学の勉強さぼってきてますから(笑)

指数、対数、階乗の復習.

特にうれしいのがアルゴリズムの説明で出てくる

\[ O(\log n) \]

とかいう表記があります.

それが漸近記法、あるいはビッグ記法と呼ばれるもので、ある関数 \[ f(n) \] について次のように定義される関数の集合 \[O (f(n) \] を考えると、

\[ O(f(n)) = \left\{ \begin{array}{l} g(n): ある c > 0 と n_0 が存在し, \\ 任意の n \geq n_0 について g(n) \leq c\cdot f(n) を満たす \end{array} \right \} \]

n が十分に大きいときに \[ c \cdot f(n) \] の方が上に来るような関数 \[ g(n) \] を集めたもの.

…というような今までなんとなく読んでいた数式の定義もしっかり説明しています.
これはありがたいです. …といってもまだまだちゃんと理解してないですが…

ただ、先の訳者のまえがきにある通り、ここの数式の説明を読み飛ばしても大丈夫です.

そしてある程度理解した後に読み飛ばしたところを再度読めばさらに理解が深まる、というしっかりした構成になっている一冊です.

この本で取り扱うデータ構造

この本で取り扱う内容の依存関係が冒頭に説明されてます.

配列やリストはよく使いますが、一番知りたかった二分木に多くのページを割いています.
ソートについて言及しているのはとても良いです.

ハッシュテーブル、スキップテーブルの解説があるものありがたい.

そして、この図にはありませんが、最後にグラフ理論の解説があるのはちゃんと勉強してこなかった私にとってはとても助かります.

各章の最後に演習問題があって自分の理解の程度を知ることもできます.

この本を読もうと思ったきっかけは…

先にも書きましたが配列やリスト構造はよく使うデータ構造なので理解してるつもりでした.

二分木は名前は知ってましたが、まぁ実際には使うことないだろう、と高をくくってました.

ところが、先日カーネルソースの一部, netfilter のカーネルモジュールのソースを読む機会があって

static unsigned int
count_tree(struct net *net,
	   struct nf_conncount_data *data,
	   const u32 *key,
	   const struct nf_conntrack_tuple *tuple,
	   const struct nf_conntrack_zone *zone)
{
	struct rb_root *root;
	struct rb_node *parent;
	struct nf_conncount_rb *rbconn;
	unsigned int hash;
	u8 keylen = data->keylen;

	hash = jhash2(key, data->keylen, conncount_rnd) % CONNCOUNT_SLOTS;
	root = &data->root[hash];

	parent = rcu_dereference_raw(root->rb_node);
	while (parent) {
		int diff;

		rbconn = rb_entry(parent, struct nf_conncount_rb, node);

このコードでrbというのは Red–black tree 赤黒木の略というのを恥ずかしながら初めて知りました…

こりゃ赤黒木わからないとまずいなぁ…と思いましてこの本を読み始めた…ということです

技術書出版ラムダノート

出版元は、いま一番勢いのある技術書出版会社のひとつであるラムダノート.

先日取り上げたこの本もラムダノートから出版されてます. これだけIPv6のまとまった内容を出せるのはラムダノート以外にはないと思います.

n月刊ラムダノートと言う名の不定期で出している本もかなり濃厚な内容で、これとても助かってます. Vol.1, No.1号なんてTCPの再送制御機構が特集されてて涙モノです.

こんな内容を日本語で読めるなんてすばらしい. 今は亡きUnix Magazine だったらとりあげそうですが、それ以外どこも取り上げないようなニッチな、でも必要な情報が読めるのは貴重です.

今回取り上げた本以外にもラムダノートから出版された本には注目していきます.