H5W3
当前位置:H5W3 > 其他技术问题 > 正文

【前端技术】Vue3 DOM Diff 鏍稿績绠楁硶瑙f瀽

image

瑙傛劅搴︼細馃専馃専馃専馃専馃専

鍙e懗锛氳荆鐐掕姳铔?/strong>

鐑归オ鏃堕棿锛?0min

鏈枃宸叉敹褰曞湪鍓嶇椋熷爞鍚屽悕浠撳簱Github github.com/Geekhyt锛屾杩庡厜涓撮鍫傦紝濡傛灉瑙夊緱閰掕彍杩樼畻鍙彛锛岃祻涓?Star 瀵归鍫傝€佹澘鏉ヨ鏄帿澶х殑榧撳姳銆?/blockquote>

鎯宠鎼炴槑鐧?Vue3 鐨?DOM Diff 鏍稿績绠楁硶锛屾垜浠浠庝竴閬?LeetCode 鐪熼璇磋捣銆?/p>

鎴戜滑鍏堟潵涓€璧疯璇婚锛?/p>

LeetCode 鐪熼 300. 鏈€闀夸笂鍗囧瓙搴忓垪

缁欏畾涓€涓棤搴忕殑鏁存暟鏁扮粍锛屾壘鍒板叾涓渶闀夸笂鍗囧瓙搴忓垪鐨勯暱搴︺€?/p>

绀轰緥锛?/p>

杈撳叆: [10,9,2,5,3,7,101,18]
杈撳嚭: 4
瑙i噴: 鏈€闀跨殑涓婂崌瀛愬簭鍒楁槸 [2,3,7,101]锛屽畠鐨勯暱搴︽槸 4銆?/blockquote>

璇存槑锛?/p>

  • 鍙兘浼氭湁澶氱鏈€闀夸笂鍗囧瓙搴忓垪鐨勭粍鍚堬紝浣犲彧闇€瑕佽緭鍑哄搴旂殑闀垮害鍗冲彲銆?/li>
  • 浣犵畻娉曠殑鏃堕棿澶嶆潅搴﹀簲璇ヤ负聽O(n2) 銆?/li>

杩涢樁: 浣犺兘灏嗙畻娉曠殑鏃堕棿澶嶆潅搴﹂檷浣庡埌聽O(nlogn) 鍚?

璇婚缁撴潫銆?/p>

浠€涔堟槸涓婂崌瀛愬簭鍒楋紵

棣栧厛锛屾垜浠渶瑕佸鍩烘湰鐨勬蹇佃繘琛屼簡瑙e拰鍖哄垎锛?/p>

  • 瀛愪覆锛氫竴瀹氭槸杩炵画鐨?/li>
  • 瀛愬簭鍒楋細瀛愬簭鍒椾笉瑕佹眰杩炵画 渚嬪锛歔6, 9, 12] 鏄?[1, 3, 6, 8, 9, 10, 12] 鐨勪竴涓瓙搴忓垪
  • 涓婂崌/閫掑瀛愬簭鍒楋細涓€瀹氭槸涓ユ牸涓婂崌/閫掑鐨勫瓙搴忓垪

娉ㄦ剰锛氬瓙搴忓垪涓厓绱犵殑鐩稿椤哄簭蹇呴』淇濇寔鍦ㄥ師濮嬫暟缁勪腑鐨勭浉瀵归『搴?/code>

棰樿В

鍔ㄦ€佽鍒?/h3>

鍏充簬鍔ㄦ€佽鍒掔殑鎬濇兂锛岃繕涓嶄簡瑙g殑鍚屽浠彲浠ョЩ姝ユ垜鐨勮繖绡囦笓鏍忓叆涓棬锛?a href="https://juejin.im/post/6844904190578278414" rel="nofollow">銆岀畻娉曟€濇兂銆嶅垎娌汇€佸姩鎬佽鍒掋€佸洖婧€佽椽蹇冧竴閿呯倴

鎴戜滑鍙互灏嗙姸鎬?dp[i] 瀹氫箟涓轰互 nums[i] 杩欎釜鏁扮粨灏?涓€瀹氬寘鎷?nums[i])鐨勬渶闀块€掑瀛愬簭鍒楃殑闀垮害锛屽苟灏?dp[i] 鍒濆鍖栦负 1锛屽洜涓烘瘡涓厓绱犻兘鏄竴涓崟鐙殑瀛愬簭鍒椼€?/p>

瀹氫箟鐘舵€佽浆绉绘柟绋嬶細

  • 褰撴垜浠亶鍘?nums[i] 鏃讹紝闇€瑕佸悓鏃跺姣斿凡缁忛亶鍘嗚繃鐨?nums[j]
  • 濡傛灉 nums[i] > nums[j]锛?code>nums[i]

灏卞彲浠ュ姞鍏ュ埌搴忓垪 nums[j] 鐨勬渶鍚庯紝闀垮害灏辨槸 dp[j] + 1

娉細(0 <= j < i) (nums[j] < nums[i])

const lengthOfLIS = function(nums) {
    let n = nums.length;
    if (n == 0) {
        return 0;
    }
    let dp = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp) 
}
  • 鏃堕棿澶嶆潅搴︼細O(n^2)
  • 绌洪棿澶嶆潅搴︼細O(n)

杩欓噷鎴戠敾浜嗕竴寮犲浘锛屼究浜庝綘鐞嗚В銆?br>

璐績 + 浜屽垎鏌ユ壘

鍏充簬璐績鍜屼簩鍒嗘煡鎵捐繕涓嶄簡瑙g殑鍚屽浠彲浠ョЩ姝ユ垜鐨勮繖涓ょ瘒涓撴爮鍏ヤ釜闂ㄣ€?/p>

杩欓噷鍐嶇粨鍚堟湰棰樼悊瑙d竴涓嬭椽蹇冩€濇兂锛屽悓鏍锋槸闀垮害涓?2 鐨勫簭鍒楋紝[1,2] 涓€瀹氭瘮 [1,4] 濂斤紝鍥犱负瀹冩洿鏈夋綔鍔涖€傛崲鍙ヨ瘽璇达紝鎴戜滑鎯宠缁勬垚鏈€闀跨殑閫掑瀛愬簭鍒楋紝
灏辫璁╄繖涓瓙搴忓垪涓笂鍗囩殑灏藉彲鑳界殑鎱紝杩欐牱鎵嶈兘鏇撮暱銆?/p>

鎴戜滑鍙互鍒涘缓涓€涓?tails 鏁扮粍锛岀敤鏉ヤ繚瀛樻渶闀块€掑瀛愬簭鍒楋紝濡傛灉褰撳墠閬嶅巻鐨?nums[i] 澶т簬 tails 鐨勬渶鍚庝竴涓厓绱?涔熷氨鏄?tails 涓殑鏈€澶у€?鏃讹紝鎴戜滑灏嗗叾杩藉姞鍒板悗闈㈠嵆鍙€傚惁鍒欑殑璇濓紝鎴戜滑灏辨煡鎵?tails 涓涓€涓ぇ浜?nums[i] 鐨勬暟骞舵浛鎹㈠畠銆傚洜涓烘槸鍗曡皟閫掑鐨勫簭鍒楋紝鎴戜滑鍙互浣跨敤浜屽垎鏌ユ壘锛屽皢鏃堕棿澶嶆潅搴﹂檷浣庡埌 O(logn) 銆?/p>

const lengthOfLIS = function(nums) {
    let len = nums.length;
    if (len <= 1) {
        return len;
    }
    let tails = [nums[0]];
    for (let i = 0; i < len; i++) {
        // 褰撳墠閬嶅巻鍏冪礌 nums[i] 澶т簬 鍓嶄竴涓€掑瀛愬簭鍒楃殑 灏惧厓绱犳椂锛岃拷鍔犲埌鍚庨潰鍗冲彲
        if (nums[i] > tails[tails.length - 1]) {
            tails.push(nums[i]);
        } else {
            // 鍚﹀垯锛屾煡鎵鹃€掑瀛愬簭鍒椾腑绗竴涓ぇ浜庡綋鍓嶅€肩殑鍏冪礌锛岀敤褰撳墠閬嶅巻鍏冪礌 nums[i] 鏇挎崲瀹?            // 閫掑搴忓垪锛屽彲浠ヤ娇鐢ㄤ簩鍒嗘煡鎵?            let left = 0;
            let right = tails.length - 1;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (tails[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tails[left] = nums[i];
        }
    }
    return tails.length;
};
  • 鏃堕棿澶嶆潅搴︼細O(nlogn)
  • 绌洪棿澶嶆潅搴︼細O(n)

杩欓噷鎴戠敾浜嗕竴寮犲浘锛屼究浜庝綘鐞嗚В銆?br>

娉ㄦ剰锛氳繖绉嶆柟寮忚鏇挎崲鍚庣粍鎴愮殑鏂版暟缁勪笉涓€瀹氭槸瑙f硶涓€涓纭粨鏋滅殑鏁扮粍锛屼絾闀垮害鏄竴鏍风殑锛屼笉褰卞搷鎴戜滑瀵规棰樻眰瑙c€?/code>

姣斿杩欑鎯呭喌锛?code>[1,4,5,2,3,7,0]

  • tails = [1]
  • tails = [1,4]
  • tails = [1,4,5]
  • tails = [1,2,5]
  • tails = [1,2,3]
  • tails = [1,2,3,7]
  • tails = [0,2,3,7]

鎴戜滑鍙互鐪嬪埌鏈€鍚?tails 鐨勯暱搴︽槸姝g‘鐨勶紝浣嗘槸閲岄潰鐨勫€间笉姝g‘锛屽洜涓烘渶鍚庝竴姝ョ殑鏇挎崲鐮村潖浜嗗瓙搴忓垪鐨勬€ц川銆?/p>

Vue3 DOM Diff 鏍稿績绠楁硶

鎼炴竻妤氫簡鏈€闀块€掑瀛愬簭鍒楄繖閬撶畻娉曢锛屾垜浠啀鏉ョ湅 Vue3 鐨?DOM Diff 鏍稿績绠楁硶灏辩畝鍗曠殑澶氫簡銆?/p>

鎴戠煡閬撲綘宸茬粡杩笉鍙婂緟浜嗭紝浣嗘槸杩欓噷杩樻槸瑕佹彃涓€鍙ワ紝濡傛灉浣犺繕涓嶄簡瑙?React 浠ュ強 Vue2 鐨?DOM Diff 绠楁硶鍙互绉绘杩欎釜閾炬帴杩涜瀛︿範锛屽惊搴忔笎杩涚殑瀛︿範鍙互璁╀綘鏇村ソ鐨勭悊瑙c€?/p>

鍥炴潵鍚庢垜浠€濊€冧竴涓棶棰橈細Diff 绠楁硶鐨勭洰鐨勬槸浠€涔堬紵

涓轰簡鍑忓皯 DOM 鎿嶄綔鐨勬€ц兘寮€閿€锛屾垜浠灏藉彲鑳界殑澶嶇敤 DOM 鍏冪礌銆傛墍浠ユ垜浠渶瑕佸垽鏂嚭鏄惁鏈夎妭鐐归渶瑕佺Щ鍔紝搴旇濡備綍绉诲姩浠ュ強鎵惧嚭閭d簺闇€瑕佽娣诲姞鎴栧垹闄ょ殑鑺傜偣銆?/strong>

濂戒簡锛岃繘鍏ユ湰鏂囩殑姝i锛孷ue3 DOM Diff 鏍稿績绠楁硶銆?/p>

棣栧厛鎴戜滑瑕佹悶娓呮锛屾牳蹇冪畻娉曠殑鐨勪綅缃€傛牳蹇冪畻娉曞叾瀹炴槸褰撴柊鏃?children 閮芥槸澶氫釜瀛愯妭鐐圭殑鏃跺€欐墠浼氳Е鍙戙€?/p>

涓嬮潰杩欐浠g爜灏辨槸 Vue3 鐨?DOM Diff 鏍稿績绠楁硶锛屾垜鍔犱笂浜嗗湪婧愮爜涓殑璺緞锛屾柟渚夸綘鏌ユ壘銆?/p>

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice()
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j
        result.push(i)
        continue
      }
      u = 0
      v = result.length - 1
      while (u < v) {
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i
      }
    }
  }
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

getSequence 鐨勪綔鐢ㄥ氨鏄壘鍒伴偅浜涗笉闇€瑕佺Щ鍔ㄧ殑鍏冪礌锛屽湪閬嶅巻鐨勮繃绋嬩腑锛屾垜浠彲浠ョ洿鎺ヨ烦杩囦笉杩涜鍏朵粬鎿嶄綔銆?/p>

鍏跺疄杩欎釜绠楁硶鐨勬牳蹇冩€濇兂灏辨槸鎴戜滑涓婇潰璁插埌鐨勬眰瑙f渶闀块€掑瀛愬簭鍒楃殑绗簩绉嶈В娉曪紝璐績 + 浜屽垎鏌ユ壘娉曘€傝繖涔熸槸涓轰粈涔堜笉鐫€鎬ヨ瀹冪殑鍘熷洜锛屽洜涓哄鏋滀綘鐪嬫噦浜嗕笂闈㈢殑 LeetCode 棰樿В锛屼綘灏卞凡缁忔帉鎻′簡 Vue3 鐨?DOM Diff 鏍稿績绠楁硶鐨勬€濇兂鍟︺€?/p>

涓嶈繃锛屾兂瑕佹悶鎳傛瘡涓€琛屼唬鐮佺殑缁嗚妭锛岃繕闇€鏀惧埌 Vue3 鏁翠釜 DOM Diff 鐨勪笂涓嬫枃涓幓鎵嶈銆傝€屼笖闇€瑕佹敞鎰忕殑鏄紝涓婇潰浠g爜涓殑 getSequence 鏂规硶鐨勮繑鍥炲€间笌 LeetCode 棰樹腑鎵€瑕佹眰鐨勮繑鍥炲€间笉鍚岋紝getSequence 杩斿洖鐨勬槸鏈€闀块€掑瀛愬簭鍒楃殑绱㈠紩銆備笂鏂囨垜浠浘鎻愬埌杩囷紝浣跨敤璐績 + 浜屽垎鏌ユ壘鏇挎崲鐨勬柟寮忓瓨鍦ㄤ竴浜?Bug锛屽彲鑳戒細瀵艰嚧缁撴灉涓嶆纭€俈ue3 鎶婅繖涓棶棰樿В鍐虫帀浜嗭紝涓嬮潰鎴戜滑鏉ヤ竴璧风湅涓€涓嬪畠鏄浣曡В鍐崇殑銆?/p>

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice() // 鎷疯礉涓€涓暟缁?p
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    // 鎺掗櫎绛変簬 0 鐨勬儏鍐?    if (arrI !== 0) {
      j = result[result.length - 1]
      // 涓庢渶鍚庝竴椤硅繘琛屾瘮杈?      if (arr[j] < arrI) { 
        p[i] = j // 鏈€鍚庝竴椤逛笌 p 瀵瑰簲鐨勭储寮曡繘琛屽搴?        result.push(i)
        continue
      }
      // arrI 姣?arr[j] 灏忥紝浣跨敤浜屽垎鏌ユ壘鎵惧埌鍚庢浛鎹㈠畠
      // 瀹氫箟浜屽垎鏌ユ壘鍖洪棿
      u = 0
      v = result.length - 1
      // 寮€鍚簩鍒嗘煡鎵?      while (u < v) {
        // 鍙栨暣寰楀埌褰撳墠浣嶇疆
        c = ((u + v) / 2) | 0
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      // 姣旇緝 => 鏇挎崲
      if (arrI < arr[result[u]]) {
        if (u > 0) { 
          p[i] = result[u - 1]  // 姝g‘鐨勭粨鏋?        }
        result[u] = i // 鏈夊彲鑳芥浛鎹細瀵艰嚧缁撴灉涓嶆纭紝闇€瑕佷竴涓柊鏁扮粍 p 璁板綍姝g‘鐨勭粨鏋?      }
    }
  }
  u = result.length
  v = result[u - 1]
  // 鍊掑彊鍥炴函 鐢?p 瑕嗙洊 result 杩涜€屾壘鍒版渶缁堟纭殑绱㈠紩
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

Vue3 閫氳繃鎷疯礉涓€涓暟缁勶紝鐢ㄦ潵瀛樺偍姝g‘鐨勭粨鏋滐紝鐒跺悗閫氳繃鍥炴函璧嬪€肩殑鏂瑰紡瑙e喅浜嗚椽蹇?+ 浜屽垎鏌ユ壘鏇挎崲鏂瑰紡鍙兘閫犳垚鐨勫€间笉姝g‘鐨勯棶棰樸€?/p>

浠ヤ笂灏辨槸 Vue3 DOM Diff 鐨勬牳蹇冪畻娉曢儴鍒嗗暒锛屾杩庡厜涓村墠绔鍫傦紝瀹㈠畼鎮ㄦ參璧帮綖

鉂わ笍鐖卞績涓夎繛鍑?/h2>

1.濡傛灉浣犺寰楅鍫傞厭鑿滆繕鍚堣儍鍙o紝灏辩偣涓禐鏀寔涓嬪惂锛屼綘鐨?strong>璧?/strong>鏄垜鏈€澶х殑鍔ㄥ姏銆?/p>

2.鍏虫敞鍏紬鍙峰墠绔鍫傦紝鍚冨ソ姣忎竴椤块キ锛?/strong>

3.鐐硅禐銆佽瘎璁恒€佽浆鍙?=== 鍌洿锛?/p>

本文地址:H5W3 » 【前端技术】Vue3 DOM Diff 鏍稿績绠楁硶瑙f瀽

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址