WEB+DB PRESS Vol.91 「データ構造の基礎知識」 を読んだ

4 年くらい振りに読み返してみた。
WEB+DB PRESS Vol.91
AtCoder をやっていて、どんなデータ構造を使うと計算量を減らせるかという知識は身についたが、そのデータ構造の中身についてはよく分かってないなということで、この本を思い出した。 まさに今知りたいこととドンピシャの内容でたくさん学びがあった。
特にハッシュテーブル(連想配列)の構造は知らなかったので学びが大きかった。なぜキーを指定して値を取得するのが O(1) で出来るのか説明できるようになった。
逆に以前読んだときの記憶がなく、何を学んだのか不明なのが悲しくなった... 4 年前にこの内容を理解できていたらもっとまともなエンジニアになっていただろう。

内容

配列、連結リスト、ハッシュテーブル、二分探索木、B 木 の順で説明されている。
連結リスト、ハッシュテーブル、二分探索木については Ruby での実装例も載っていて、動かしながら確認できるのが分かりやすい。私は Go で書いてみた。
https://github.com/hxrxchang/data-structure-go

ジェネリクスの勉強のいい機会にもなった。二分探索木で値の比較をするので比較演算が可能であることを保証する型定義をどうやるか悩んで、constraints.Ordered の存在を初めて知れた。

追記: (2024-02-15)
Ordered は 標準の cmp pakcage に入っていた。 https://pkg.go.dev/cmp#Ordered

以下に解説されていたデータ構造を簡単に説明する。

配列

• ランダムアクセスが O(1)でできる。
• 要素の追加や削除に O(N)かかる。
  • これは競プロをやっていているので、よく分かっていた。
  • 追加の場合(末尾追加でも)、追加しようとするメモリ領域が他で使われている可能性があるので、配列全体を別の領域にコピーする必要があるというのは確かにと思った。
  • 競プロで使っている Python の list は、末尾への追加は O(1) できるはずだがと思ったが、純粋な配列ではなくて、本文でも説明があった Java の ArrayList 相当の物なのだろうか。

連結リスト

配列と対照的に、

• ランダムアクセスが O(N)
• 要素の追加や削除が配列より効率的に行える
  • 今回の実装方法だと先頭への追加が O(1)
  • 末尾への追加は O(N)
  • だが、要素同士のメモリは隣り合う必要はなく参照できればよいので、配列のように全体を別のメモリ領域移すみたいなことは必要ない。

ハッシュテーブル

一番学びがあった。なぜ O(1) で欲しい値を取れるかドヤ顔で説明できるようになった。
以下のような構造になっている.

• 任意の数の連結リストを持った配列を作る
• key, value を追加する際に key をハッシュ化し、↑ の配列の要素数で割った余りとなるインデックスの連結リストに、key と value を追加する
• key でプロパティを取得する際も key をハッシュ化することで、どのインデックスに保存されているかが O(1)で分かる
• インデックスがわかった後に連結リストを探索することになるが、よしななタイミングで rehash という処理をすることで、連結リストが大きくなりすぎないようにする
  • rahash とは、連結リストを保持する配列の要素数を増やして各 key, value を入れ直す処理をすること

rehash の実装が載ってなかったのでまだ実装できていないのだが、これから追加したい。
Ruby での実装は key, value をタプルで保存していたが、これはハッシュテーブルを実装している最中に hash を使うのは変だからだろうか。 Go にはタプルがないので Key string, Value T の struct を保存することにした。ハッシュテーブルに相当するのは Go だと map なので、struct を使うのは問題ないとした。

二分探索木

• O(logN)でどのノードにもアクセスできそうだが、バランスが悪い木になると O(N)かかる。

B 木、B+木

いきなり難易度が上がる。B 木のサンプルコードがなくて実装まではできていないが、挿入の度にどうやって木を更新していくかはなんとなく分かった。
B+木は、木をルートから探索せずともリーフノードに全部のデータが詰まっているくらいしか理解できていない。しばらく積んでいたWEB+DB PRESS Vol.122 Rust で実装！作って学ぶ RDBMS のしくみ でも触れられているのでそちらでも学んでみたい。

まとめ

改めて読み返してとてもいい内容だった。しんぺいさんの分かりやすく説明する力はやはりすごい。
こういった低レイヤーよりの内容に興味を持ったり、理解できたりするのに競プロが役立っていると感じた。

基礎的なデータ構造の実装に、Go だと構造体やスライスを所与のものとして使ったが、ではそれらはどう実装すればいいのかというのはコンパイラを知れば分かるのだろうか。
プログラミング言語を作るにあたり、どこまで別の言語で実装して、どこからその言語自身で実装できるのかみたいなことを知りたいと思った。

ということで、WEB+DB PRESS Vol.91　大変おすすめです。