企业官网建设流程全解析

吴川手机网站建设公司,南京建站公司哪家好,西安移动网站建设,公司网站建设包含的内容Vue 版本#xff1a;以 vue3.x 代码为参考#xff0c;主要梳理 diff 算法的核心流程。 Vue 3 的 diff 算法借鉴了纯文本 diff 算法的思想#xff0c;参考了 viv 和 inferno 框架的实现#xff0c;只对需要处理的节点本身进行 diff 操作。通过预处理和最长递增子序列#x…Vue 版本以vue3.x代码为参考主要梳理 diff 算法的核心流程。Vue 3 的 diff 算法借鉴了纯文本 diff 算法的思想参考了 viv 和 inferno 框架的实现只对需要处理的节点本身进行 diff 操作。通过预处理和最长递增子序列LIS算法Vue 3 能够显著减少不必要的 DOM 操作提升渲染性能。核心策略先头后尾找公共新增删除看剩余中间乱序靠 Map 映射 最长递增子序列Diff 算法流程1. 同步头部节点Sync from Start从前往后比较新旧节点列表跳过相同的节点直到遇到第一个不同的节点。比较c1[i]和c2[i]如果相同则继续后移i遇到不同节点时停止此时i即为需要处理的起始位置示例旧列表(a b) c 新列表(a b) d e 结果i 2跳过前两个相同节点2. 同步尾部节点Sync from End从后往前比较新旧节点列表跳过相同的节点直到遇到第一个不同的节点。比较c1[e1]和c2[e2]如果相同则继续前移e1和e2遇到不同节点时停止此时e1和e2即为需要处理的结束位置示例旧列表a (b c) 新列表d e (b c) 结果e1 0, e2 1跳过后两个相同节点3. 处理新增节点Common Sequence Mount如果i e1 i e2说明新列表中有新增节点需要挂载这些节点。示例旧列表(a b) 新列表c (a b) 情况i 0, e1 -1, e2 0 操作在位置 0 处新增节点 c4. 处理删除节点Common Sequence Unmount如果i e2 i e1说明旧列表中有多余节点需要卸载这些节点。示例旧列表a (b c) 新列表(b c) 情况i 0, e1 0, e2 -1 操作删除节点 a5. 处理乱序节点Unknown Sequence如果上述情况都不满足说明中间部分存在乱序需要执行移动和更新操作。处理流程建立 key 到索引的映射遍历新节点列表建立key - newIndex的映射表方便快速查找旧节点在新列表中的位置。遍历旧节点建立新索引到旧索引的映射查找每个旧节点在新节点列表中的位置。建立newIndexToOldIndexMap数组记录新节点索引对应的旧节点索引偏移 10 表示新增节点。通过比较newIndex和maxNewIndexSoFar判断节点是否需要移动。计算最长递增子序列如果检测到节点移动使用 LIS 算法找出不需要移动的节点序列。执行移动和挂载操作从后往前遍历新节点列表。如果节点不在 LIS 中执行移动操作。如果节点是新增的newIndexToOldIndexMap[i] 0执行挂载操作。示例旧列表[i ... e1 1]: a b [c d e] f g 新列表[i ... e2 1]: a b [e d c h] f g 情况i 2, e1 4, e2 5 操作处理中间乱序部分 [c d e] - [e d c h]最长递增子序列LIS算法300. 最长递增子序列 - 力扣LeetCode最长递增子序列算法是 Vue 3 diff 算法的核心优化找出不需要移动的节点序列实现最小化 DOM 操作。算法原理核心思想贪心算法 二分查找 回溯列表算法创建一个数组result用于记录递增序列的索引下标通过贪心策略和二分查找找到局部最优解然后通过回溯指针数组还原出真正的递增子序列。算法步骤详解示例数组[1, 30, 100, 200, 300, 50, 60]第一步贪心查找递增序列预设初始索引result [0]对应值 1贪心策略比较 30 1符合递增result[1] 1对应值 30比较 100 30符合递增result[2] 2对应值 100依次类推直到 300此时result [0, 1, 2, 3, 4]遇到不满足递增的元素比较 50 300不满足递增通过二分查找在有序递增数组result中找到首个比 50 大的数的索引位置这里找到的是索引 2对应值 100将result[2]替换为 50 的索引 5即[0, 1, 2, 3, 4]变为[0, 1, 5, 3, 4]同样处理 60最终得到[0, 1, 5, 6, 4]问题此时的结果并不满足原有数组的递增子序列索引值并非递增局部最优解导致全局最优解出现偏差。50 和 60 跑到了 300 前面违反了序列的原则。第二步回溯修正解决方案给每个当前队列中的索引添加指向前置节点的指针即代码里的p数组。在完成遍历后使用指针从尾部开始回溯还原出真正的递增子序列。前置指针和当前arr存储的索引位置对应代表当前arr索引的值指向的前置索引在遍历过程中p前置索引列表中数值 50 和 100 的前置指针都指向 30回溯过程从后往前遍历result进行回溯首先是索引 4对应值 300其p的前置指针为索引 3对应值 200所以修正为 3索引 3对应值 200的前置为索引 2对应值 100修正为 2这里把result中的索引 5对应值 50顶替掉继续下去100 30 1最终修正为[0, 1, 2, 3, 4]而非局部贪心得到的[0, 1, 5, 6, 4]最终结果[0, 1, 2, 3, 4]对应值[1, 30, 100, 200, 300]而非[1, 30, 50, 60, 300]符合递增子序列的原则。代码实现// https://en.wikipedia.org/wiki/Longest_increasing_subsequencefunctiongetSequence(arr:number[]):number[]{// 从原有数组拷贝出支持回溯的指针数组constparr.slice()// 定义数组索引存储结果constresult[0]leti,j,u,v,cconstlenarr.length// 1. 遍历第一次递增子序列查找for(i0;ilen;i){// 获取当前数组项constarrIarr[i]// arrI 为 0 表示新增节点无需参与后续步骤if(arrI!0){// 获取最后一个索引jresult[result.length-1]// 假如最后一个索引值 当前数组项符合递增子序列逻辑if(arr[j]arrI){// 定义当前索引的前置指针指向最后一个值p[i]j// 存入当前索引下标result.push(i)// 结束本次判断continue}// 假如最后一个索引值 当前数组项条件不满足// 二分查找找到最近满足的项u0vresult.length-1while(uv){c(uv)1// 假如当前c处索引值的数组项 当前数组项往后找因为要找到最近最小于的项才行if(arr[result[c]]arrI){uc1}else{// 假如当前c处索引值的数组项 当前数组项往前找vc}}// 假如找到的u处索引数组项 当前项且 u 0即有完成二分查找过程if(arrIarr[result[u]]){if(u0){// 定义当前索引的前置指针指向前一个值p[i]result[u-1]}// 在当前索引处插入索引项完成递增子序列处理result[u]i}}}// 2. 第二次遍历根据指针列表回溯结果uresult.length vresult[u-1]while(u--0){// 从头往尾部将序列还原为正常的递增子序列结果result[u]v vp[v]}// 返回结果returnresult}Diff 算法主要实现constpatchKeyedChildren(c1:VNode[],c2:VNodeArrayChildren,container:RendererElement,parentAnchor:RendererNode|null,parentComponent:ComponentInternalInstance|null,parentSuspense:SuspenseBoundary|null,namespace:ElementNamespace,slotScopeIds:string[]|null,optimized:boolean,){leti0constl2c2.length// 获取结束索引// e1 是 oldVNodese2 是 newVNodelete1c1.length-1// prev ending indexlete2l2-1// next ending index// 1. sync from start// (a b) c// (a b) d e// 首次循环从前往后比较直到出现节点不一致while(ie1ie2){constn1c1[i]constn2(c2[i]optimized?cloneIfMounted(c2[i]asVNode):normalizeVNode(c2[i]))if(isSameVNodeType(n1,n2)){patch(n1,n2,container,null,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)}else{break}i}// 2. sync from end// a (b c)// d e (b c)// 第二次循环从后往前比较直到出现节点不一致while(ie1ie2){constn1c1[e1]constn2(c2[e2]optimized?cloneIfMounted(c2[e2]asVNode):normalizeVNode(c2[e2]))if(isSameVNodeType(n1,n2)){patch(n1,n2,container,null,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)}else{break}e1--e2--}// 3. common sequence mount// (a b)// c (a b)// i 0, e1 -1, e2 0// 假如 i oldEnd i newEnd证明有节点需要新增if(ie1){if(ie2){constnextPose21constanchornextPosl2?(c2[nextPos]asVNode).el:parentAnchorwhile(ie2){patch(null,(c2[i]optimized?cloneIfMounted(c2[i]asVNode):normalizeVNode(c2[i])),container,anchor,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)i}}}// 4. common sequence unmount// a (b c)// (b c)// i 0, e1 0, e2 -1// 假如 i newEnd i oldEnd证明有节点需要删除elseif(ie2){while(ie1){unmount(c1[i],parentComponent,parentSuspense,true)i}}// 5. unknown sequence// [i ... e1 1]: a b [c d e] f g// [i ... e2 1]: a b [e d c h] f g// i 2, e1 4, e2 5else{// 定义新的开始坐标consts1i// prev starting indexconsts2i// next starting index newStart// 5.1 build key:index map for newChildren// 建立在新节点中的列表索引后续遍历旧节点时通过 key 快速查找旧节点在新节点中的位置constkeyToNewIndexMap:MapPropertyKey,numbernewMap()for(is2;ie2;i){// 建立前后节点的索引关系constnextChild(c2[i]optimized?cloneIfMounted(c2[i]asVNode):normalizeVNode(c2[i]))if(nextChild.key!null){keyToNewIndexMap.set(nextChild.key,i)}}// 5.2 loop through old children left to be patched and try to patch// matching nodes remove nodes that are no longer present// 遍历旧节点列表部分进行复用和删除letjletpatched0// 获取需要 patch 的节点数量consttoBePatchede2-s21letmovedfalse// used to track whether any node has movedletmaxNewIndexSoFar0// works as MapnewIndex, oldIndex// Note that oldIndex is offset by 1// and oldIndex 0 is a special value indicating the new node has// no corresponding old node.// used for determining longest stable subsequence// 初始化新索引到旧索引的映射数组constnewIndexToOldIndexMapnewArray(toBePatched)for(i0;itoBePatched;i)newIndexToOldIndexMap[i]0for(is1;ie1;i){constprevChildc1[i]// 已经超过 patch 范围说明节点可以被移除证明新节点处理完旧的卸载if(patchedtoBePatched){// all new children have been patched so this can only be a removalunmount(prevChild,parentComponent,parentSuspense,true)continue}letnewIndex// 查找旧节点在新节点中的索引位置if(prevChild.key!null){newIndexkeyToNewIndexMap.get(prevChild.key)}else{// 若没有key尝试定位相同且无key的节点索引// key-less node, try to locate a key-less node of the same typefor(js2;je2;j){if(newIndexToOldIndexMap[j-s2]0isSameVNodeType(prevChild,c2[j]asVNode)){newIndexjbreak}}}// 若新节点不存在合适的索引那么卸载对应节点if(newIndexundefined){unmount(prevChild,parentComponent,parentSuspense,true)}else{// 记录新列表LIS部分的相对索引偏移10表示新增节点newIndexToOldIndexMap[newIndex-s2]i1if(newIndexmaxNewIndexSoFar){// 更新最大索引maxNewIndexSoFarnewIndex}else{movedtrue// 假如 最大索引代表节点需要移动}// 完成节点复用操作patch(prevChild,c2[newIndex]asVNode,container,null,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)patched}}// 5.3 move and mount// generate longest stable subsequence only when nodes have movedconstincreasingNewIndexSequencemoved// 递增子序列处理位置?getSequence(newIndexToOldIndexMap):EMPTY_ARR// 从列表末尾开始遍历// 倒序遍历可以利用「下一个节点的 el 作为锚点」// 避免移动节点后影响后续节点的锚点位置保证 DOM 操作的正确性。jincreasingNewIndexSequence.length-1// looping backwards so that we can use last patched node as anchorfor(itoBePatched-1;i0;i--){constnextIndexs2iconstnextChildc2[nextIndex]asVNodeconstanchorVNodec2[nextIndex1]asVNodeconstanchornextIndex1l2?// #13559, fallback to el placeholder for unresolved async componentanchorVNode.el||anchorVNode.placeholder:parentAnchor// 为 0 代表新增节点if(newIndexToOldIndexMap[i]0){// mount newpatch(null,nextChild,container,anchor,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)}elseif(moved){// move if:// There is no stable subsequence (e.g. a reverse)// OR current node is not among the stable sequence// 不在最长递增子序列中说明节点需要移动if(j0||i!increasingNewIndexSequence[j]){move(nextChild,container,anchor,MoveType.REORDER)}else{// 在 LIS 中无需移动j--}}}}}快速 diff 算法优势预处理优化先处理头部和尾部的相同节点然后快速缩小需要 diff 的范围减少不必要的比较操作。最长递增子序列优化通过 LIS 算法找出不需要移动的节点完成后只移动真正需要移动的节点最小化 DOM 操作次数。Key 映射优化建立 key 到索引的映射表实现 O(1) 节点查找避免嵌套循环查找 O(n²) 复杂度。倒序遍历优化在处理节点移动时从后往前遍历可以利用下一个节点的 DOM 元素作为锚点避免移动节点后影响后续节点的锚点位置保证 DOM 操作的正确性。思考1. Vue 3 的 快速diff 算法相比 Vue 2 双端 diff 有哪些改进Vue 3 引入了最长递增子序列算法和 patchFlag 能够更精确地识别不需要移动的节点和静态节点在复杂列表场景下能够减少更多的 DOM 操作。2. 为什么需要回溯指针数组贪心算法在寻找递增子序列时可能会用较小的值替换较大的值导致结果不满足真正的递增子序列通过回溯指针数组可以从尾部开始还原出真正的递增子序列保证算法过程准确。3. 为什么倒序遍历新节点列表倒序遍历可以利用下一个节点的 DOM 元素作为锚点避免移动节点后影响后续节点的锚点位置如果是正序遍历移动节点后可能会改变后续节点的锚点导致 DOM 操作错误。总结Diff 算法流程Vue 3 的 diff 算法分为五个步骤同步头部节点、同步尾部节点、处理新增节点、处理删除节点、处理乱序节点。通过预处理快速缩小范围然后通过 key 映射和 LIS 算法处理复杂的节点移动场景。最长递增子序列算法使用贪心算法 二分查找 回溯列表的方式找出不需要移动的节点序列。通过贪心策略和二分查找找到局部最优解然后通过回溯指针数组还原出真正的递增子序列最小化 DOM 操作次数。关键优化通过预处理优化快速缩小范围LIS 算法精确识别不需要移动的节点key 映射实现 O(1) 查找参考内容vuejs/core - patchKeyedChildrenLongest Increasing Subsequence - WikipediaVue 设计与实现 - 第 11 章 快速 Diff 算法