私は最近、根本的な部分に注目しています。そこで、より複雑で重要な知識のポイントについて話すシリーズを作りたいと思います。学習は大きな山のようなもので、山に登ることだけが、違う景色を見るため、より深い経験をするためなのです。今日は、より重要なVueの仮想DOMとVueの差分アルゴリズムについてお話します。
仮想 DOM
仮想DOMは、実際にツリーの基礎として、オブジェクトの属性は、ノードを記述するために、JavaScriptのオブジェクトであり、キャッシュの真ん中にjsと実際のdomに相当する、domの差分アルゴリズムの使用は、それによってパフォーマンスを向上させる、不要なdomの操作を避けるために。もちろん、アルゴリズムが最適解ではない場合もあります。2つのノードがdomツリーを移動するために後で説明するような、発生する可能性のある実用的な状況の多くに対応する必要があるためです。
仮想DOMと組み合わせてvueのデータの状態管理に関する最後のいくつかの記事を理解しやすく、vueでは一般的に要素の状態の変更を通じて、サブスクライバは、コンパイルおよびレンダリングの変更の状態に応じて、基本的な実装は、単純に3つのステップのプロセスとして理解することができます：
- 1、ドムツリーの構造をJavaScriptのオブジェクト構造で表現し、このツリーを使って実際のドムツリーを構築し、ブラウザのページに挿入します。
- 2、状態が変更された場合、つまり、状態を変更するには、vueは、ツリーオブジェクトのツリーを再構築し、この新しく構築されたツリーと比較するための古いツリーを使用して、2つのツリーの違いを記録します。
- 3.ステップ1で構築された実ドムツリーに、2で記録された差分を再適用することで、ビューが更新されます。
例: テンプレートに記述されたul>liリストがあります：
<ul id='list'>
<li class='item1'>Item 1</li>
<li class='item2'>Item 2</li>
<li class='item3' style='font-size: 20px'>Item 3</li>
</ul>
parseは、正規表現とその他の方法を用いて、テンプレートのディレクティブ、class、style、その他のデータを解析し、ASTを形成するので、ul> liは次のように解析されます。
// jsDOM構造をシミュレートする
var element = {
tagName: 'ul', // ノード ラベル名
props: { // DOMdiffの属性は、以下のキーと値のペアでオブジェクトに格納される。
class: 'item',
id: 'list'
},
children: [ // このノードの子ノード
{tagName: 'li', props: {class: 'item1'}, children: "Item 1"},
{tagName: 'li', props: {class: 'item2'}, children: "Item 2"},
{tagName: 'li', props: {class: 'item3', style: 'font-size: 20px'}, children: "Item 3"},
]
}
最適化プロセスは、実際にはちょうど後者の差分アルゴリズムを最適化することです、あなたはこのプロセスを追加しない場合、ノードの各層は、また、仮想DOMの元の本質に反している、不必要なリソースの計算と無駄の結果、再び取得する必要がある部分には変更がない場合でも、比較を行う必要があります。したがって、コンパイルプロセスでは、vueは、静的なノードをマークするためのイニシアチブを取る、私はページが変更されていないか、またはノードの状態によって影響されないの一部であることを理解しています。たとえば、ulノードは、関係なく、ulは常に変更されないので、このコンパイルプロセスでは、タグを再生するulすることができますどのようにliの変更の。その後の更新は、ビューインターフェイスを更新するときに、パッチプロセスは、直接これらの静的なノードをスキップして、このラベルを参照してください。
最後に、AST は generate によってレンダー関数文字列に変換され、その結果、レンダー文字列と staticRenderFns 文字列が得られます。ASTを取得すると、vueにはelement ASTと呼ばれる内部コードジェネレータがあり、その名前が示すように、generate関数はパースされたASTオブジェクトを取得し、ASTツリーを再帰的に調べ、異なるASTノードに対して異なるメソッドを作成し、それらを組み合わせて実行可能なJavaScript文字列に結合し、後で呼び出されるのを待ちます。最終的には次のようになります：
function _render() {
with (this) {
return __h__(
'ul',
{staticClass: "list"},
[
" ",
__h__('li', {class: item}, [String((msg))]),
" ",
__h__('li', {class: item}, [String((msg))]),
"",
__h__('li', {class: item}, [String((msg))]),
""
]
)
};
}
興味のある学生は、src/compiler/index.jsにあるソースコードを参照してください。
export const createCompiler = createCompilerCreator(function baseCompile (
template: string,
options: CompilerOptions
): CompiledResult {
// 1.parse抽象構文木は、テンプレート文字列から抽象構文木に変換される。
const ast = parse(template.trim(), options)
// 2.optimizeASTの静的ノードラベル付けを使用した、完全な簡易版のdiffアルゴリズム
if (options.optimize !== false) {
optimize(ast, options)
}
// 3.generatediffアルゴリズムの完全簡略版である抽象構文木は、レンダー関数のコード文字列を生成する。
const code = generate(ast, options)
return {
ast,
render: code.render,
staticRenderFns: code.staticRenderFns
}
})
diffアルゴリズムとキーの役割
diffアルゴリズムは、時間複雑度がO(n^3)であるため、最初は実際には「使えない」ものです。ドムツリーに1000個のノードがあるとすると、最初はtree1を走査し、2回目はtree2を走査し、最後にソートして新しいツリーに結合する必要があります。つまり、この1000個のノードを1000^3 = 1億回計算する必要があり、これは非常に大きな計算なので、このアルゴリズムは基本的に使用されません。
後の設計者は、時間複雑性をO(n^3)からO(n)に変更する方法を考え出しました。ここからがdiffアルゴリズムの出番であり、通常理解されている知識の一部です：
- 1.同じレベルでのみ比較し、レベル間では比較しません。
- 2、タグが同じではない、直接再構成を削除し、もはや深さの比較
- 3、タグとキー、両方が同じである、それは深さの比較ではなく、同じノードであると見なされます。
これは、木をレベルごとに探索するのではなく、同じレベルの木のノードを比較するという単純な差分なので、時間の複雑さはO(n)だけです。
Virtual DOMでは、状態が変化したときにvueが新しいオブジェクトツリーを再構築し、新しく構築されたツリーと古いツリーを比較する方法について説明します。この処理はpatchと呼ばれ、vueとreactのコアとなるアルゴリズムですが、理解するのが難しいです。diffが古いVNodeと新しいVNodeの違いをどのように比較するのかを理解するために、簡単なグラフを見てみましょう。
シナリオ1：移動の更新と削除
シナリオ2：新規削除
diffアルゴリズムの実践の簡単な理解で。この部分はまだ比較的複雑なので、よりよく理解してもらうために。次のステップでは、diffアルゴリズムがどのように深さ優先探索を実行し、差分を記録するかを擬似コードを使って分析します。 VueのVDOMのdiffアルゴリズムは拝借しているので、まずはsnabbdomのExampleから始めると良いでしょう！
vueでは、まず新旧のツリーが深さ優先でトラバースされ、各ノードが一意にラベル付けされます。トラバース中、ノードがトラバースされるたびに新しいツリーと比較され、違いがあればオブジェクトに記録されます。
/* 2つのツリー（古いツリーと新しいツリー）を受け取るdiff関数を作成する。*/
function diff (oldTree, newTree) {
var index = 0 //点がマークされたとき
var patches = {} //各ノードの差分を記録するためのオブジェクト
dfsWalk(oldTree, newTree, index, patches) // 2つの木の深さ優先探索
return patches //異なるレコードを返す
}
function dfsWalk (oldNode, newNode, index, patches) {
var currentPatch = [] // oldNodeとnewNodeの差分を記録する配列を定義する。
if (newNode === null) {
// 並べ替えが実行されると、実際のDOMノードは削除されるので、ここでノードを調整する必要はない！
} else if (_.isString(oldNode) && _.isString(newNode)) {
// oldNode、newNodeが文字列オブジェクトか文字列値かを判定する
if (newNode !== oldNode) {
//ノードの差分は直接配列に格納される
currentPatch.push({ type: patch.TEXT, content: newNode })
}
} else if (oldNode.tagName === newNode.tagName && oldNode.key === newNode.key) {
// ノードは同じだが、diffは古いノードのpropsとchildrenを区別する。
// diff小道具の処理
var propsPatches = diffProps(oldNode, newNode)
if (propsPatches) {
currentPatch.push({ type: patch.PROPS, props: propsPatches })
}
// diffignore'フラグがある場合、diffは子ノードを無視する。
if (!isIgnoreChildren(newNode)) {
diffChildren(
oldNode.children,
newNode.children,
index,
patches,
currentPatch
)
}
} else {
// ノードが同じでない場合、古いノードを新しいノードに置き換える。
currentPatch.push({ type: patch.REPLACE, node: newNode })
}
}
function isIgnoreChildren (node) {
return (node.props && node.props.hasOwnProperty('ignore'))
}
/* 子ノードの処理 diffChildren関数*/
function diffChildren (oldChildren, newChildren, index, patches, currentPatch) {
var diffs = listDiff(oldChildren, newChildren, 'key')
newChildren = diffs.children
if (diffs.moves.length) {
var reorderPatch = { type: patch.REORDER, moves: diffs.moves }
currentPatch.push(reorderPatch)
}
var leftNode = null
var currentNodeIndex = index
oldChildren.forEach(function (child, i) {
var newChild = newChildren[i]
currentNodeIndex = (leftNode && leftNode.count) // ノードの同一性を計算する
? currentNodeIndex + leftNode.count + 1
: currentNodeIndex + 1
dfsWalk(child, newChild, currentNodeIndex, patches) // 子ノードを深く走査する
leftNode = child
})
}
/* 子ノードのプロップを扱う diffProps関数*/
function diffProps (oldNode, newNode) {
var count = 0
var oldProps = oldNode.props
var newProps = newNode.props
var key, value
var propsPatches = {}
// Find out different properties
for (key in oldProps) {
value = oldProps[key]
if (newProps[key] !== value) {
count++
propsPatches[key] = newProps[key]
}
}
// Find out new property
for (key in newProps) {
value = newProps[key]
if (!oldProps.hasOwnProperty(key)) {
count++
propsPatches[key] = newProps[key]
}
}
// If properties all are identical
if (count === 0) {
return null
}
return propsPatches
}
// diff関数を公開する
module.exports = diff
ご興味があれば、diffの簡易版もご覧ください。
