動的な木構造のレンダリングとは

こういうやつです。

ユーザーが自由に新しい要素を追加したり (例えば D の下に G という要素を追加する etc), 既存の要素を削除したりする (例えば B 要素を消すと B, C, D が消える) 機能を react-redux を使って実現することが目的です。
最近 react-redux を使ってアプリを作ろうとしている中でこういうことがやりたくなったのがきっかけです。

注意: 実装のアイデアは書いていますが, 実際に動くコードは書いていません。上記の GitHub の実装は参考になると思いますが, すでに色々追加しているため, 読み解くのは難しいかもしれません。

アイデア

Redux

せっかく react-redux を使っているので, 木構造の動きについては Redux 側に管理してもらいます。どういう風にデータを管理すればいいかをまず考えましょう。
レンダリングする要素 (Element とします) のそれぞれに id をつけます。Redux 側では, Element 同士がどのように木構造をなしているかを覚えておくデータ構造 (elementTree とします) と, 各 Element をレンダリングする際に必要な情報をまとめた Map (elementContentMap とします) を用意します。
例えば,

elementTree.get(1) = [2, 3]
elementContentMap.get(1) = "Hello"

という風に設定していたら, Element の id が 1 のものは id が 2, 3 の要素を子供に持っていて, 実際にレンダリングするときは "Hello" という文字列をレンダリングすれば良いということが管理されています。実際のアプリケーションを作る際は, elementContentMap の中身がもっと複雑になっているかもしれませんが, それは連想配列を使うことでうまく対処できます。

このデータ構造を使って要素の追加, 削除に対応できるのかを簡単に見てみましょう。

ADD

要素の追加では, 「どの要素の下に追加するか」, 「どういうコンテンツを追加するか」, 「どういう id を割り当てるか」の情報が必要になります。それぞれを parentId, content, id とすると, 必要な作業は

nextState.elementTree.get(parentId).push(id);
nextState.elementContentMap.get(id) = content;
nextState.elementTree.get(id) = [];

です(多分)。

DELETE

要素の削除では, 「どの id の要素を消すか」の情報が必要になります。この情報を id とすると, 必要な作業は, 以下の通りです(こっちは実装が結構多いです)。
- id 以下の部分木の content を全て削除する (elementContentMap の操作)。
- id 以下の部分木の情報を全て削除する (elementTree の操作)。
- id の親要素の子供情報から id を削除する (elementTree の操作)。

id 以下の部分木の id を全て取得する, という操作は, 深さ優先探索を使うと簡単です。知らない人は以下のリンクを見てみましょう。
https://qiita.com/drken/items/4a7869c5e304883f539b

これで Redux 側は準備が情報を送る準備ができました。Redux 側で一番大事なアイデアは, 「レンダリングするための情報」と「木の情報を覚えておくための Element 同士の関係」を id によって分離しておく, ということです。

React

React 側は, Redux から各要素がいい感じに情報を受け取ってレンダリングをします。レンダリング関数は content と子供要素の id を持っているはずですが, 自分自身のレンダリングは content を持っているからいいとして, 子供要素は id だけでどうやってレンダリングするのか, というのが難しいところです(少なくとも僕はこれでしばらく悩みました)。

解決策は, React の Component と Container の 2 つで再帰的な構造にすることです。アイデアを簡単にコードにします。

ElementComponent.js


const ElementComponent = ({id, content, childrenIds}) => {
return (
<div>
    <div>{content}</div>
    {childrenIds.map((id) => (<ElementContainer id={id}>))}
</div>
)

ポイントは, Component の子供レンダリングの際に Component 自身を再帰させるのではなく, Container を呼び出しているところです。次に Container 側を見てみます。

ElementContainer.js


const mapStateToProps = (state, ownProps) => ({
    id: ownProps.id,
    content: state.elementContentMap.get(ownProps.id),
    childrenIds: state.elementTreeMap.get(ownProps.id)
});
const mapDispatchToProps = dispatch => ({
    ...
});

export default connect(
    mapStateToProps,
    mapDispatchToProps
)(ElementComponent)

Container 側は id だけを引数として content を引き出せるような構造になっています。このような再帰構造を作ることで, 動的な木構造をレンダリングすることができます。

計算量

注: ここは結構適当に想像で書いています。間違っていたら教えて欲しいです。

redux を使っている時点で, データ更新に O(N) かかるのは仕方なさそうな気がします。React の偉いところは, 以前の仮想 DOM と比べてどれだけ更新しないといけないのか, というのを賢く計算できるところだそうなので, 毎回 Redux が状態を覚えるために O(N) の計算量を使っていることは気にせず, レンダリングをきちんと行った時に仮想 DOM にどれだけ変更を加えなければならないかにのみ焦点を合わせます(聞くところによると, そこが一番時間のかかるところらしいのでここに焦点を合わせることは妥当だと思われます)。
参考 -> https://qiita.com/risagon/items/019942c60e9c3e6c05a5

ADD

ある要素を追加した場合に変化する DOM は, 追加した id の親要素だけなので, 計算量は O(1) か O(C) (C は親要素が持っていた子供要素の数) なんじゃないかと思います。

DELETE

削除指定した要素以下の部分木の要素が全て消えるので, 部分木のサイズを S として O(S) の計算量はかかります。削除指定した要素の親の子供要素も変化するので, 子供要素の数 C を追加した O(S+C) の計算量がかかるのかもしれません。

React-Redux で動的な木構造をレンダリングする

動的な木構造のレンダリングとは

アイデア

Redux

ADD

DELETE

React

計算量

ADD

DELETE