Algoritma diff ialah algoritma cekap yang membandingkan nod pokok pada tahap yang sama, mengelakkan keperluan untuk mencari dan melintasi pokok lapisan demi lapisan. Jadi berapa banyak yang anda tahu tentang algoritma diff? Artikel berikut akan memberi anda analisis mendalam tentang algoritma perbezaan vue2. Saya harap ia akan membantu anda!
Saya telah lama melihat kod sumber Vue 2 Dari menggunakan aliran hingga kini menggunakan TypeScript, saya akan membuka kod sumbernya dan melihat setiap masa, tetapi setiap kali saya hanya melihat bahagian permulaan data, iaitu peringkat beforeMount saya tidak berhati-hati tentang cara menjana VNode (Visual Dom Node, yang juga boleh dipanggil secara langsung vdom) dan. bagaimana untuk membandingkan VNode (perbezaan) semasa mengemas kini komponen Untuk penyelidikan, saya hanya tahu bahawa algoritma pembezaan berganda digunakan untuk cara permulaan dan pengakhiran dua kali ini, saya tidak pernah melihatnya. jadi saya mengambil kesempatan untuk menulis artikel untuk mengkajinya dengan teliti kali ini. Jika isinya salah, saya harap anda boleh membantu saya menunjukkannya, terima kasih banyak-banyak~
Pada pemahaman saya, diff merujuk kepada differences, iaitu, mengira perbezaan antara kandungan lama dan baharu ; algoritma perbezaan dalam Vue dengan cepat membandingkan tatasusunan nod VNod yang baru dan lama melalui mudah dan cekap kaedah Perbezaan antara adalah supaya mengemas kini kandungan halaman dengan operasi dom yang minimum. [Cadangan berkaitan: tutorial video vuejs, pembangunan bahagian hadapan web]
Pada masa ini terdapat dua prasyarat yang diperlukan:
Perbandingan ialah tatasusunan VNode
Terdapat dua set tatasusunan VNode lama dan baharu
pada masa yang sama, jadi. ia biasanya hanya berlaku apabila data dikemas kini Apabila kandungan halaman perlu dikemas kini, laksanakan , iaitu renderWatcher.run().
Seperti yang dinyatakan di atas, apa yang dibandingkan dalam diff ialah VNode, bukan nod dom sebenar Saya percaya mengapa VNode digunakan? Sudah jelas, biar saya terangkan secara ringkas, bukan?~
Terdapat kira-kira dua sebab untuk menggunakan VNode dalam Vue:
VNode direka sebagai pereka bentuk rangka kerja mengikut kepada keperluan rangka kerja Objek JavaScript itu sendiri mempunyai sifat yang lebih ringkas daripada nod dom sebenar dan tiada pertanyaan dom diperlukan semasa operasi, yang boleh mengoptimumkan penggunaan prestasi semasa pengiraan
Pautan ini daripada VNode kepada dom sebenar Proses pemaparan boleh diproses secara berbeza mengikut platform yang berbeza (web, applet WeChat) untuk menjana elemen dom sebenar yang disesuaikan dengan setiap platform
Semasa proses diff, data nod lama dan baharu akan dilalui Sebagai perbandingan, menggunakan VNode boleh membawa peningkatan prestasi yang hebat.
Dalam halaman web, nod dom sebenar wujud dalam bentuk pokok, dan nod akar semuanya , untuk memastikan bahawa nod maya adalah konsisten dengan nod dom sebenar, VNode juga menggunakan struktur pokok.
Jika semua nod VNode perlu dibandingkan apabila komponen dikemas kini, kedua-dua set nod lama dan baharu perlu dilalui secara mendalam dan dibandingkan, yang akan menyebabkan banyak overhed prestasi ; oleh itu, secara lalai dalam Vue Perbandingan nod pada tahap yang sama, iaitu Jika tahap pepohon VNode lama dan baharu adalah berbeza, kandungan tahap tambahan akan dibuat terus atau dibuang, dan hanya operasi perbezaan akan dilakukan pada tahap yang sama.
Secara amnya, operasi diff biasanya berlaku dalam v-for gelung atau objek nod yang mempunyai v-if/v-else dijana secara dinamik component seperti dan (nod statik umumnya tidak berubah, Ia adalah sangat pantas jika dibandingkan), dan proses ini adalah untuk mengemas kini dom, jadi dalam kod sumber, nama kaedah yang sepadan dengan proses ini ialah updateChildren, terletak di src/core/vdom/patch.ts. Seperti yang ditunjukkan di bawah:
Berikut ialah semakan proses penciptaan dan kemas kini contoh komponen Vue:
Pertama daripada semua,
beforeCreatePada peringkatcreated, pemprosesan utama ialah data dan status serta beberapa peristiwa dan kaedah asasKemudian, kaedah
$mount(vm.$options.el)akan dipanggil untuk memasuki penciptaan dan pemasanganVnodedan peringkat dom, iaitu antarabeforeMountdanmounted(sama seperti di sini apabila komponen dikemas kini)
$mountpada prototaip akan ditulis semula dalamplatforms/web/runtime-with-compiler.ts, dan pelaksanaan asal adalah dalamplatforms/web/runtime/index.tsdalam kaedah pelaksanaan asal, kaedahmountComponentsebenarnya dipanggil untuk dilaksanakanrender; dan dalamwebdi bawahruntime-with-compiler, modul kompilasi rentetan templat ditambah, yang akan menghuraikan dan menyusunoptionsdalamtemplatedan menukarnya menjadi fungsi Bind kepadaoptions.renderdalam
mountComponentDi dalam fungsi, mentakrifkan kaedah pemaparanupdateComponent = () => (vm._update(vm._render())dan membuat contohbeforedengan konfigurasiwatcher( Iaitu,renderWatcher), dengan mentakrifkan objek pemerhatianwatchsebagai kaedahupdateComponentyang baru ditakrifkan untuk melaksanakan pemaparan komponen pertama dan pengumpulan kebergantungan pencetus , konfigurasibeforehanya mengkonfigurasi kaedah fungsi cangkukbeforeMount/beforeUpdatepencetus ; ini juga sebab mengapa nod dom sebenar tidak boleh diperolehi dalam peringkatbeforeMountdan nod dom lama diperoleh dalam peringkatbeforeUpdatetakrif kaedah dan kaedah
_update> Di bawah fail yang sama, intinya ialahmountComponentmembaca (nod dom lama) dan$el(VNod lama) dalam contoh komponen dan_vnodedijana oleh fungsi_render()untuk melaksanakan operasivnodepatchFungsi pertama membandingkan sama ada
patchmempunyai nod lama , ia mestilah komponen baharu, yang akan dibuat dan dipaparkan secara langsung jika ia mempunyai nod lama, , kemudian bandingkan nod lama dan baharu melalui ,patchVnodedan jika nod lama dan baharu adalah konsisten dan kedua-duanya mempunyai nod anak, masukkan logik teraschildren-diffkemas kini perbandingan nod anakupdateChildren, Kaedah ini juga yang sering kita panggil Algoritmadiff
lwn. : , kaedah menambah nod sameNode(a, b), kaedah mengalih keluar nod addVnodes Sudah tentu, walaupun selepas removeVnodes menilai bahawa VNod adalah konsisten, ia akan tetap digunakan sameNode Menjalankan perbandingan mendalam kandungan sesuatu. tunggal VNode lama dan baharu untuk mengesahkan sama ada data dalaman perlu dikemas kini. patchVnode
Bandingkan sama ada nod lama dan baharu adalah sama.
Dalam kaedah ini, perkara pertama yang perlu dibandingkan ialah sama ada a dan b adalah sama Inilah sebabnya Vue menyatakan dalam dokumen bahawa nod dinamik seperti key mesti ditetapkan v-for、v-if、v-else. untuk mengenal pasti keunikan, jika key wujud dan sama, anda hanya perlu membandingkan sama ada perubahan dalaman telah berlaku, yang secara amnya boleh mengurangkan banyak operasi DOM jika ia tidak ditetapkan, elemen nod yang sepadan akan; langsung dimusnahkan dan dibina semula. key
undefined
elemen induk tatasusunan nod semasa, elemen parentElm pada kedudukan yang ditentukan, refElm vnodes tatasusunan nod maya baharu , baharu nod Kedudukan permulaan elemen yang dimasukkan tatasusunan, startIdx indeks akhir elemen yang dimasukkan tatasusunan nod baharu, endIdx baris gilir nod maya yang akan dimasukkan. Fungsi insertedVnodeQueue
merentasi tatasusunan bermula dari startIdx hingga vnodes kedudukan endIdx, dan kemudian panggil untuk mencipta dan memasukkan createElm yang sepadan sebelum refElm pula elemen. vnodes[idx]
komponen dalam vnodes[idx] ini dan Component juga akan dipanggil untuk mencipta contoh komponen yang sepadan. createComponent
Oleh kerana keseluruhan
VNodedan dom adalah struktur pokok, jadi selepas perbandingan pada tahap yang sama, pemprosesan VNode dan dom yang lebih mendalam di bawah tahap semasa perlu diproses .
Bertentangan dengan addVnodes, kaedah ini digunakan untuk mengalih keluar nod VNode.
Memandangkan kaedah ini hanya mengalih keluar, ia hanya memerlukan tiga parameter: vnodes Tatasusunan nod maya lama , startIdx indeks mula, endIdx indeks penamat. Fungsi
secara dalaman akan merentasi tatasusunan startIdx bermula dari vnodes sehingga kedudukan endIdx Jika vnodes[idx] bukan undefined, ia akan berdasarkan Atribut tag. Pemprosesan terbilang:
tag, menunjukkan bahawa ia adalah elemen atau komponen dan kandungan perlu vnodes[idx] diproses secara rekursif , mencetuskan remove hooks 与 destroy hooks
tag wujud, menunjukkan bahawa ia ialah nod teks biasa Anda boleh terus mengalih keluar nod daripada dom Kaedah perbandingan lengkap sebenar dan kemas kini dom untuk perbandingan nod.
Dalam kaedah ini, ia terutamanya termasuk sembilan pertimbangan parameter utama, dan sepadan dengan logik pemprosesan yang berbeza:
VNod lama dan baharu adalah kongruen , Ini bermakna tiada perubahan, Keluar terus
Jika VNode baharu mempunyai pengikatan dom sebenar dan set nod yang perlu dikemas kini ialah tatasusunan, salin VNode semasa ke kedudukan koleksi yang ditentukan
Jika nod lama ialah komponen tak segerak dan belum selesai dimuatkan, keluar terus , jika tidak, nod yang baharu akan melalui fungsi hydrate VNode ditukar menjadi dom sebenar untuk pemaparan; dalam kedua-dua kes, keluar dari fungsi
jika yang lama dan baharu nod ialah kedua-duanya nod statik dan key adalah sama, atau jika nod yang ditentukan oleh isOnce tidak dikemas kini, ia akan terus menggunakan semula contoh komponen nod lama dan keluar daripada fungsi
Jika nod VNode baharu mempunyai atribut data dan dikonfigurasikan dengan fungsi cangkuk prepatch, laksanakan pemberitahuan prepatch(oldVnode, vnode) untuk masuk fasa perbandingan nod. Secara amnya, langkah ini akan mengkonfigurasi pengoptimuman prestasi
Jika VNode baharu mempunyai atribut data dan secara rekursif menukar vnod contoh subkomponen nod, jika label masih tersedia, fungsi cangkuk cbs dikonfigurasikan dalam objek fungsi panggil balik dan update dikonfigurasikan dalam fungsi data 🎜> Cangkuk update
Jika yang baharu VNode bukan nod teks, ia akan memasuki peringkat perbandingan teras :
children kaedah untuk membandingkan nod anak updateChildren
text
(ia adalah nod teks), bandingkan kandungan teks nod lama dan baharu untuk melihat sama ada ia konsisten, jika tidak, kemas kini kandungan teks text
yang dikonfigurasikan dalam data nod baharu untuk memberitahu nod bahawa kemas kini telah selesai postpatch
dilakukan dalam fasa kemas kini nod yang sama sebagai patchVnode Bandingkan kandungan baharu dengan kandungan lama, dan kemas kini kandungan yang sepadan jika terdapat perubahan jika terdapat nod anak, lakukan perbandingan dan kemas kini setiap nod anak "secara rekursif" .
perbandingan dan kemas kini tatasusunan nod anak ialah logik teras perbezaan dan juga merupakan salah satu soalan yang sering disebut semasa temu bual.
Sekarang, mari kita masuk ke dalam analisis kaedah~updateChildren
updateChildrenBandingkan perbezaan elemen dua tatasusunan objek berdasarkan tatasusunan baharu Apakah kaedahnya?
Secara umumnya, kita boleh terus melintasi dua tatasusunanmelalui brute force bermaksud untuk mencari susunan dan perbezaan setiap elemen dalam tatasusunan, iaitu algoritma beza mudah .
Iaitu,merentasi tatasusunan nod baharu, merentasi tatasusunan nod lama sekali lagi dalam setiap kitaran untuk membandingkan sama ada kedua-dua nod itu konsisten dan menentukan sama ada nod baharu itu ditambah, dialih keluar atau dialihkan melalui hasil perbandingan Keseluruhan proses memerlukan m*n perbandingan, jadi kerumitan masa lalai adalah Hidup.
Kaedah perbandingan ini sangat intensif prestasi semasa sejumlah besar kemas kini nod, jadi Vue 2 mengoptimumkannya dan menukarnya kepada 双端对比算法, iaitu 双端 diff.
Seperti namanya, berakhir dua bermaksud bermula dari kedua-dua hujung dan melintasi ke tengah untuk perbandingan algoritma.
Dalam 双端 diff, ia dibahagikan kepada lima situasi perbandingan:
Kepala lama dan baharu adalah sama
Ekor lama dan baru adalah sama
Kepala lama sama dengan ekor baru
Ekor lama ialah sama dengan kepala baru
Empat tidak sama antara satu sama lain
Antaranya, empat yang pertama adalah situasi ideal, manakala yang kelima ialah situasi perbandingan yang paling rumit.
dinilai sama, iaitu
sameVnode(a, b)sama dengantrue
Mari kita analisanya melalui situasi pratetap.
Untuk menunjukkan lima situasi di atas pada masa yang sama, saya pratetap tatasusunan nod baharu dan lama berikut:
oldChildren dalam susunan nod awal, ia mengandungi 7 nod daripada 1 hingga 7 secara keseluruhannewChildren selepas dikocok, ia juga mempunyai 7 nod, tetapi dibandingkan dengan Nod lama dikurangkan dengan satu vnode 3 dan satu ditambah vnode 8
Sebelum membuat perbandingan, anda perlu mentakrifkan indeks dua hujung. daripada dua set nod:
let oldStartIdx = 0 let oldEndIdx = oldCh.length - 1 let oldStartVnode = oldCh[0] let oldEndVnode = oldCh[oldEndIdx] let newStartIdx = 0 let newEndIdx = newCh.length - 1 let newStartVnode = newCh[0] let newEndVnode = newCh[newEndIdx]
menyalin kod sumber, dengan
oldChialaholdChildrendalam gambar dannewChialahnewChildren
Kemudian, kami mentakrifkan perbandingan traversal Keadaan berhenti operasi :
while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx)
Keadaan berhenti di sini ialah Asalkan sama ada nod lama atau baru traversal tatasusunan tamat, traversal akan berhenti serta-merta .
Status nod pada masa ini adalah seperti berikut:
Untuk memastikan tatasusunan nod lama dan baharu tidak akan melakukan perbandingan yang tidak sah semasa perbandingan, dan akan mengecualikan data dahulu di mana bahagian permulaan dan akhir tatasusunan nod lama Undefined adalah berterusan dan mempunyai nilai .
if (isUndef(oldStartVnode)) {
oldStartVnode = oldCh[++oldStartIdx]
} else if (isUndef(oldEndVnode)) {
oldEndVnode = oldCh[--oldEndIdx]
Sudah tentu ini tidak berlaku dalam contoh kita dan boleh diabaikan.
Pada masa ini, ia bersamaan dengan dua indeks permulaan nod lama dan baru tatasusunan. Nod yang ditunjuk oleh ialah Pada asasnya konsisten , kemudian patchVnode akan dipanggil untuk melakukan perbandingan mendalam dan kemas kini dom bagi dua vnod, dan dua indeks permulaan akan menjadi bergerak ke belakang . Iaitu:
if (sameVnode(oldStartVnode, newStartVnode)) {
patchVnode(
oldStartVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
oldStartVnode = oldCh[++oldStartIdx]
newStartVnode = newCh[++newStartIdx]
}Perubahan nod dan indeks pada masa ini adalah seperti yang ditunjukkan dalam rajah:
adalah serupa dengan kesamaan nod kepala , juga dipanggil untuk membandingkan dua nod ekor dan mengemas kini dom , kemudian menggerakkan dua indeks hujung ke hadapan patchVnode.
if (sameVnode(oldEndVnode, newEndVnode)) {
patchVnode(
oldEndVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
)
oldEndVnode = oldCh[--oldEndIdx]
newEndVnode = newCh[--newEndIdx]
}
, dan dipanggil dengan cara yang sama untuk memproses dua nod. patchVnodeTetapi perbezaan daripada kedua-dua di atas ialah dalam kes ini, nod
, jadi pada masa ini ia masih akan menjadi selepas tamat. Masukkan semula patchVnode nod kepala lama ke dalam nodeOps.insertBefore selepas nod ekor lama semasa melalui . Kemudian, indeks permulaan
.
Anda mungkin mempunyai soalan apabila anda melihat ini, mengapatatasusunan nod lamadialihkan ke sini kerana terdapat atribut dalam nod vnod, yang mana akan menunjuk ke Nod dom sebenar yang sepadan dengan vnod, jadi menggerakkan tatasusunan nod lama di sini sebenarnya mengalihkan urutan nod dom sebenar
elmdan ambil perhatian bahawa ini ialah nod ekor semasa indeks ditukar, tidak ada Ia mestilah terakhir tatasusunan nod asal.
即：
if (sameVnode(oldStartVnode, newEndVnode)) {
patchVnode(
oldStartVnode,
newEndVnode,
insertedVnodeQueue,
newCh,
newEndIdx
)
canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
oldStartVnode = oldCh[++oldStartIdx]
newEndVnode = newCh[--newEndIdx]
}此时状态如下：
这里与上面的 旧头等于新尾 类似，一样要涉及到节点对比和移动，只是调整的索引不同。此时 旧节点的 末尾索引 前移、新节点的 起始索引 后移，当然了，这里的 dom 移动对应的 vnode 操作是 将旧节点数组的末尾索引对应的 vnode 插入到旧节点数组 起始索引对应的 vnode 之前。
if (sameVnode(oldEndVnode, newStartVnode)) {
patchVnode(
oldEndVnode,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
oldEndVnode = oldCh[--oldEndIdx]
newStartVnode = newCh[++newStartIdx]
}此时状态如下：
在以上情况都处理之后，就来到了四个节点互相都不相等的情况，这种情况也是 最复杂的情况。
当经过了上面几种处理之后，此时的 索引与对应的 vnode 状态如下：
可以看到四个索引对应的 vnode 分别是：vnode 3、vnode 5、 vnode 4、vnode 8，这几个肯定是不一样的。
此时也就意味着 双端对比结束。
后面的节点对比则是 将旧节点数组剩余的 vnode （oldStartIdx 到 oldEndIdx 之间的节点）进行一次遍历，生成由 vnode.key 作为键，idx 索引作为值的对象 oldKeyToIdx，然后 遍历新节点数组的剩余 vnode（newStartIdx 到 newEndIdx 之间的节点），根据新的节点的 key 在 oldKeyToIdx 进行查找。此时的每个新节点的查找结果只有两种情况：
找到了对应的索引，那么会通过 sameVNode 对两个节点进行对比：
patchVnode 进行深层对比和 dom 更新，将 oldKeyToIdx 中对应的索引 idxInOld 对应的节点插入到 oldStartIdx 对应的 vnode 之前；并且，这里会将 旧节点数组中 idxInOld 对应的元素设置为 undefinedcreateElm 重新创建一个新的 dom 节点并将 新的 vnode 插入到对应的位置没有找到对应的索引，则直接 createElm 创建新的 dom 节点并将新的 vnode 插入到对应位置
注：这里 只有找到了旧节点并且新旧节点一样才会将旧节点数组中
idxInOld中的元素置为undefined。
最后，会将 新节点数组的 起始索引 向后移动。
if (isUndef(oldKeyToIdx)) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
idxInOld = isDef(newStartVnode.key)
? oldKeyToIdx[newStartVnode.key]
: findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
if (isUndef(idxInOld)) {
// New element
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
} else {
vnodeToMove = oldCh[idxInOld]
if (sameVnode(vnodeToMove, newStartVnode)) {
patchVnode(
vnodeToMove,
newStartVnode,
insertedVnodeQueue,
newCh,
newStartIdx
)
oldCh[idxInOld] = undefined
canMove &&
nodeOps.insertBefore(
parentElm,
vnodeToMove.elm,
oldStartVnode.elm
)
} else {
// same key but different element. treat as new element
createElm(
newStartVnode,
insertedVnodeQueue,
parentElm,
oldStartVnode.elm,
false,
newCh,
newStartIdx
)
}
}
newStartVnode = newCh[++newStartIdx]
}大致逻辑如下图：
经过上面的处理之后，根据判断条件也不难看出，遍历结束之后 新旧节点数组都刚好没有剩余元素 是很难出现的，当且仅当遍历过程中每次新头尾节点总能和旧头尾节点中总能有两个新旧节点相同时才会发生，只要有一个节点发生改变或者顺序发生大幅调整，最后 都会有一个节点数组起始索引和末尾索引无法闭合。
那么此时就需要对剩余元素进行处理：
即：
Vue 2 的 diff 算法相对于简单 diff 算法来说，通过 双端对比与生成索引 map 两种方式 减少了简单算法中的多次循环操作，新旧数组均只需要进行一次遍历即可将所有节点进行对比。
Perbandingan dua hujung akan melakukan empat perbandingan dan pergerakan masing-masing, dan prestasinya bukanlah penyelesaian yang optimum Oleh itu, Vue 3 memperkenalkan Peningkatan Terpanjang Terpanjang untuk menggantikan perbandingan dua hujung. . , manakala selebihnya masih ditukar menjadi peta indeks untuk menggunakan pengembangan ruang untuk mengurangkan kerumitan masa, dengan itu meningkatkan lagi prestasi pengkomputeran.
Sudah tentu, nod dom sebenar elm yang sepadan dengan vnode tidak ditunjukkan dalam rajah artikel ini. Hubungan mudah alih antara kedua-duanya mungkin menyebabkan salah faham Reka Bentuk dan Pelaksanaan".
Proses keseluruhan adalah seperti berikut:
(Belajar perkongsian video: tutorial pengenalan vuejs, Video Asas Pengaturcaraan)
Atas ialah kandungan terperinci Fahami dengan cepat algoritma perbezaan Vue2 (penjelasan grafik terperinci). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
![Pertempuran sebenar Vue3 bahagian hadapan [projek vue tulisan tangan]](https://img.php.cn/upload/course/000/000/068/639b12e98e0b5441.png)
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
