修行の場

知人が言っていました。これは修行だと。

基本的なデータ構造のちょっとした整理

データ構造、一般的な用途、MLとの関係を表にまとめました。

データ構造 一般的な用途 MLとの関係
配列 末尾追加によるデータ追加が主。ランダムアクセスしたい場合 大規模データ(単体PC)
連結リスト 末尾先頭追加によるデータ追加が主。 大規模データ(単体PC)
Red-Black Tree キーによる順序付き連想配列 大規模データ(単体PC)
Hash Table キーによる順序なし連想配列 大規模データ(単体PC)
Heap Tree 優先度つきキュー(取り出し、入れるの計算時間制約が同程度) データ配置アーキテクチャ
B Tree インデックスの管理 大規模データ(単体PC)、データ配置アーキテクチャ

学習データ管理のアーキテクチャを考える場合や、単体PCでMLのモデルを開発していく場合などは、これらのデータ構造を状況に合わせて使い分けられる必要があります。 特に単体PCでモデルを作る状況はインフラに載せる前の実験的な作業でしょうから、 実行速度が試行錯誤の速度に大きな影響を与えるはずで、重要です。

個々のデータ構造のまとめ

  • 配列:末尾追加削除はO(1)。任意の位置のランダムアクセスO(1)。任意の位置の追加削除が遅い。
  • 連結リスト:先頭末尾の追加削除はO(1), 任意の位置のランダムアクセスO(n)、インデックスによる任意の位置削除はO(n)だが、ポインタがあれば任意の位置の削除はO(1)
  • Red-Black Tree: 追加削除検索がO(logn)。最悪時間も。キーによる順序付け
  • Hash Table: 追加削除検索がO(1), 最悪時間はO(n)
  • Heap Tree: 最小要素の取り出しO(logn), 要素の追加削除更新(logn)
  • B Tree: 追加削除検索がO(logn)、底はノードのサイズ。実際のメモリアクセス数はノードサイズが大きいと常に大きくなる。

例えば、Qt5のリストではUIの表示とリスト内容の変化への対応をするために、リスト内容は連結リストで管理されています。それにより、イテレーション速度はO(n)と配列と比べると多くなく、リストのポインタによる要素の削除はO(1)、任意のポインタのあとへの挿入はO(1)となることがわかります。 例えば、要素をクリックするとクリックされた要素が手に入るので、その要素の下に新しい要素を追加するなどといったことができます。

まとめ

データ構造を理解することとMLの関係が少しだけわかりました。