しゅみは人間の分析です

いらんことばかり考えます

週報 2022/04/24 データ構造の設計をまちがえた話

近況

なぜか江南スタイルのPVをみていた。曲もわかりやすくダンスもうまくて癖になる。特に序盤でPSYと男児が踊ってるところを気にいっている。

ヤクルト1000

睡眠がよくなるという噂のヤクルト1000を飲んでみた。
だが、数日続けても変わった感じはしない。中途覚醒はなくなったかも?これが各位の体験している現象なのだろうか。

この手のものは腸が荒れている人には効果が出やすいのかもしれない。野菜や発酵食品を食べてない人やストレスに晒され続けている人たち。
私の胃腸は特に不調だったわけでもないので、効果がわかりにくいのだろう。

おそらくヤクルト1000の効果を最大化するには食物繊維が必要だ。腸に菌を補充しても彼らの餌がないと意味がない。野菜を食べましょう。

体温とやる気

頭が回らないと思ったらたいてい体温が低い。特に鼓膜の体温=深部体温が低い。
鼓膜の温度は赤外線方式の体温計で測れる。耳にセンサーをつっこんでボタンを押すと1秒もかからずに計測される。

私の場合は37.0度あれば設計、実装やドキュメント執筆ができる。やる気が出ない、頭が回らないと思ったら36.7度くらいになっている。

体温を上げるにはお湯と運動がよい。出社していれば意味もなく歩きまわるのだが、家だとそれはできない。お湯を飲んで体温をあげるようにしている。もちろん淹れたてのコーヒーでもよい。

業務

1on1があったので自主的にふりかえりをしてみた。半年経ってみると何かしらは変わっているもので、以前よりも「勝手に動く」のができるようになっていた。

non117.hatenablog.com

以前書いたこの記事は「勝手に動く」課題を認識して書いたものだが、これが自然とできるようになり、板についてきた感じはする。

データ構造の設計をまちがえた話

このところアウトライナーをReact + TypeScriptで自作している。アウトライナーとは文章をJSONみたいなかたちで構造化するテキストエディタである。

テキストエディタなので「↑」「↓」によるカーソルの上下移動や「Tab」によるインデントを実装せねばならない。カーソル位置とインデント状態をどっかに保持しておく必要があった。

アウトラインとはどんなデータ構造なのだろうか?

例えばこんな見た目のテキストの集まりがあったとき、これらをどんなデータ構造に入れておくのか、を考える。

直観的に考えたら木構造だな、と思った。JSON木構造になっているし、アウトラインを書くときも親子関係を意識している。

じゃあこんな型をテキスト一つに対応させたらよいだろうか。

interface Node {
  id: string
  text: string
  parent: Node // 木構造としてはなくてもよいが親へのポインタもあると便利だった
  children: Node[]
}

しかもReactで Nodeレンダリングを表現するとなかなか気持ちのよい書き方ができた。

const NodeElem: React.FunctionComponent<Props> = ({ node }) => {
  return (
    <Text value={node.text} /> // onChange等省略してます
    {node.children.map(n => <NodeElem key={n.id} node={n} />)}
  )
}

いいじゃんエレガントじゃん、と思った。しかし表題のとおりこれは間違いだったのだ。

カーソル移動の実装が異常に難しくなる

「Tab」によるインデント機能は問題なかった。ごくふつうの木構造の操作として、ある Node を隣の Node の子にするだけである。

ところが、カーソル移動の実装で破綻した。例えばこんなアウトラインを考える。

eにカーソルがあるとき、「↑」が押されたらカーソルはdに移動しないといけない。
木構造の気持ちになるとaに移動させるのが楽なのだが、人間向けのUIとしてはdに移動してほしい。非合理的かもしれないが、既存のアウトライン実装もそうなっているし実際そうなっていたほうが使いやすい。

interface Node {
  id: string
  text: string
  parent: Node
  children: Node[]
}

dに移動する操作を実装するのはめんどくさい。a: Nodechildrenchildrenchildren のなかの末尾の Node を見つけないといけない。aの子孫がどんなに複雑な木になっていても子孫でもっとも若いNodeにカーソルを移動させる必要がある。

対策はある。葉ノードで双方向連結リストを作る方法が有名だ。

この手法はRDBMSのインデックスのデータ構造に使われている。B+ treeなインデックスに ORDER BY id LIMIT 10 みたいなクエリを投げると葉ノードの連結リストをたどってデータをとりだすことになる。クエリのチューニングをするときにインデックス木構造の気持ちになるのは大事なので覚えておくとよい。

とはいえこの最適化をすべきではない。いま作っているのはアウトライナーテキストエディタGUIであって、DBではない。

何より葉ノードの連結リストを作ると Nodeくんが複雑になってしまう。ただでさえ木構造のポインタつけかえはバグりやすいのに、これ以上ポインタを増やすなんて……。

データ構造がまちがっている

なにかがおかしい。そう確信した。おかしいのはおそらくデータ構造だ。
いまカーソルの上下移動を実装しようとしてコードがめちゃくちゃになった。ならばカーソル移動が楽になるようデータ構造を定義すればよろしい……。それって配列では?配列で要件を満たせるのでは?

インデント情報はdepthとして各 Node に持っておけばいいし、上下移動はNode[]のインデックスを一つ動かすだけである。超簡単。

アウトライナーではNode のいれかえも必要なのだが、これはバブルソートの要領でやればよい。バグらせない自信はないが木構造の操作よりマシである。

interface Node {
  id: string
  text: string
  depth: number
}
type Nodes = Node[]

ユースケースから考えよ

というわけで、アウトライナーに最適なデータ構造は木ではなく配列だった。最初の思いこみで酷い目にあってしまった。

教訓は「具体的なユースケースから逆算してデータ構造を設計すること」である。仕様をぱっとみてデータ構造を作るのではなく、どんな操作、どんなメソッドが必要なのかを洗い出して、操作しやすいデータ構造を作るのだ。

ちなみにこの原則はDynamoDB設計の鉄則でもある。AWSの担当者にDynamoDB設計のベストプラクティスを聞くと、まずこの話をされると思う。

まとめ

  • データ構造の設計で実装がシンプルになる
  • データ構造はユースケースから逆算して作る

Rule 5. Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.

Rob Pike's 5 Rules of Programming

同じことはRob Pike大先生も言っている。
大事なのはアルゴリズムではない。データ構造である。