您好,登錄后才能下訂單哦!
這篇文章主要講解了“結(jié)合React源碼如何快速掌握優(yōu)先隊(duì)列”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“結(jié)合React源碼如何快速掌握優(yōu)先隊(duì)列”吧!
優(yōu)先隊(duì)列是數(shù)據(jù)結(jié)構(gòu)中的基礎(chǔ)概念,與隊(duì)列先進(jìn)先出(FIFO)的出隊(duì)順序不同的是 ,它的出隊(duì)順序與元素的優(yōu)先級相關(guān)。
例如 React 的時(shí)間分片(React Fiber),它將渲染任務(wù)分了優(yōu)先級,出隊(duì)的順序與任務(wù)的“重要程度”存在關(guān)系,那么滿足這種情況的數(shù)據(jù)結(jié)構(gòu)就是 優(yōu)先隊(duì)列 。
插入:在優(yōu)先隊(duì)列中插入元素,并使隊(duì)列“有序”
刪除最大/最小值:刪除并返回最大/最小的元素,并使隊(duì)列“有序”
查找最大/最小關(guān)鍵字:查找最大/最小的值
優(yōu)先隊(duì)列可以由以上多種方式實(shí)現(xiàn),而優(yōu)先隊(duì)列的主要操作是插入和刪除,其中二叉搜索樹和二叉堆這兩項(xiàng)操作的時(shí)間復(fù)雜度均為 logn ,但二叉樹在多次刪除之后容易導(dǎo)致樹的傾斜,同時(shí)查找成本也高于二叉堆,所以最終二叉堆是比較符合實(shí)現(xiàn)優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。
在二叉堆中數(shù)組中,要保證每個(gè)元素都小于(大于)或等于另外兩個(gè)特定位置的元素。例如下圖的樹中,父節(jié)點(diǎn)總是小于或等于子節(jié)點(diǎn)。
對于二叉堆有如下性質(zhì):
節(jié)點(diǎn) k 的父節(jié)點(diǎn)下標(biāo)為 k / 2(向下取整)
已某節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹,該節(jié)點(diǎn)是這顆樹的極值
插入
二叉堆的插入非常簡單,只需要在二叉堆的最后添加要插入的內(nèi)容,并將其“上浮”到正確位置。
嘗試在上面的二叉堆中插入新元素 9,過程如下:
在尾部插入元素 9,與父節(jié)點(diǎn)進(jìn)行對比,有序性被破壞,與父元素替換位置。
替換成功后,繼續(xù)上一輪操作,與父節(jié)點(diǎn)進(jìn)行對比,仍然無法滿足有序性,繼續(xù)調(diào)換位置。
再次替換后符合。
程序框架
function push { * 在堆尾部添加元素 * 執(zhí)行上浮循環(huán) * 與父元素對比大小,將較大的放在父節(jié)點(diǎn)位置 return minItem }
實(shí)現(xiàn)
function push(heap: Heap, node: Node): void { const index = heap.length; heap.push(node); // 在堆尾部添加元素 siftUp(heap, node, index); // 進(jìn)行上浮操作 } function siftUp(heap, node, i) { let index = i; while (true) { const parentIndex = (index - 1) >>> 1; // 父節(jié)點(diǎn)位置: parentIndex = childIndex / 2 const parent = heap[parentIndex]; if (parent !== undefined && compare(parent, node) > 0) { // The parent is larger. Swap positions. heap[parentIndex] = node; heap[index] = parent; index = parentIndex; } else { // The parent is smaller. Exit. return; } } }
刪除
取出根節(jié)點(diǎn)的值對比插入稍微復(fù)雜一點(diǎn),歸納起來可以分為三步:
取出根節(jié)點(diǎn)的值
將最后一個(gè)元素與根節(jié)點(diǎn)進(jìn)行替換,并刪除最后一個(gè)元素
下沉
取出根節(jié)點(diǎn)。
將最后一個(gè)元素與根節(jié)點(diǎn)調(diào)換,并刪除。對比發(fā)現(xiàn)有序性被破壞,進(jìn)行對調(diào)。
完成刪除。
程序框架
function pop { * 設(shè)定 minItem 保存根節(jié)點(diǎn) * 取出最后一個(gè)節(jié)點(diǎn)與根節(jié)點(diǎn)替換,并刪除最后一個(gè)節(jié)點(diǎn) * 執(zhí)行下沉循環(huán) * 將根元素與左右子節(jié)點(diǎn)對比,挑選較小的與父節(jié)點(diǎn)替換位置 return minItem }
實(shí)現(xiàn)
export function pop(heap: Heap): Node | null { const first = heap[0]; // 取出根節(jié)點(diǎn) if (first !== undefined) { const last = heap.pop(); // 取出最后一位元素,并刪除 if (last !== first) { heap[0] = last; // 與根節(jié)點(diǎn)對調(diào) siftDown(heap, last, 0); // 下沉 } return first; } else { return null; } } function siftDown(heap, node, i) { let index = i; const length = heap.length; while (index < length) { const leftIndex = (index + 1) * 2 - 1; const left = heap[leftIndex]; const rightIndex = leftIndex + 1; const right = heap[rightIndex]; // If the left or right node is smaller, swap with the smaller of those. // 尋找左右兒子較小的那一個(gè)替換 if (left !== undefined && compare(left, node) < 0) { //左子節(jié)點(diǎn)小于根節(jié)點(diǎn) if (right !== undefined && compare(right, left) < 0) { heap[index] = right; heap[rightIndex] = node; index = rightIndex; } else { heap[index] = left; heap[leftIndex] = node; index = leftIndex; } } else if (right !== undefined && compare(right, node) < 0) { // 左子節(jié)點(diǎn)大于根節(jié)點(diǎn),右子節(jié)點(diǎn)小于根節(jié)點(diǎn) heap[index] = right; heap[rightIndex] = node; index = rightIndex; } else { // Neither child is smaller. Exit. return; } } }
以下是 react 源碼中 scheduler/src/SchedulerMinHeap.js 關(guān)于最小堆的完整實(shí)現(xiàn):
/** * Copyright (c) Facebook, Inc. and its affiliates. * * This source code is licensed under the MIT license found in the * LICENSE file in the root directory of this source tree. * * @flow strict */ // 定義最小堆極其元素,其中 sortIndex 為最小堆對比的 key,若 sortIndex 相同,則對比 id type Heap = Array<Node>; type Node = {| id: number, sortIndex: number, |}; // 入隊(duì)操作,在入隊(duì)完成之后進(jìn)行“上浮” export function push(heap: Heap, node: Node): void { const index = heap.length; heap.push(node); siftUp(heap, node, index); } // 查找最大值 export function peek(heap: Heap): Node | null { const first = heap[0]; return first === undefined ? null : first; } // 刪除并返回最大值 export function pop(heap: Heap): Node | null { const first = heap[0]; // 取出根節(jié)點(diǎn)(哨兵) if (first !== undefined) { const last = heap.pop(); // 取出最后一位元素,并刪除 if (last !== first) { // 頭尾并沒有對撞 heap[0] = last; // 與根節(jié)點(diǎn)對調(diào) siftDown(heap, last, 0); // 下沉 } return first; } else { return null; } } // 上浮,調(diào)整樹結(jié)構(gòu) function siftUp(heap, node, i) { let index = i; while (true) { const parentIndex = (index - 1) >>> 1; // 父節(jié)點(diǎn)位置: parentIndex = childIndex / 2,此處使用位操作,右移一位 const parent = heap[parentIndex]; if (parent !== undefined && compare(parent, node) > 0) { // 對比父節(jié)點(diǎn)和子元素的大小 // The parent is larger. Swap positions. heap[parentIndex] = node; // 若父節(jié)點(diǎn)較大,則更換位置 heap[index] = parent; index = parentIndex; } else { // The parent is smaller. Exit. return; } } } // 下沉,調(diào)整樹結(jié)構(gòu) function siftDown(heap, node, i) { let index = i; const length = heap.length; while (index < length) { const leftIndex = (index + 1) * 2 - 1; const left = heap[leftIndex]; const rightIndex = leftIndex + 1; const right = heap[rightIndex]; // If the left or right node is smaller, swap with the smaller of those. // 尋找左右兒子較小的那一個(gè)替換 if (left !== undefined && compare(left, node) < 0) { if (right !== undefined && compare(right, left) < 0) { // 左子節(jié)點(diǎn)小于根節(jié)點(diǎn) heap[index] = right; heap[rightIndex] = node; index = rightIndex; } else { heap[index] = left; heap[leftIndex] = node; index = leftIndex; } } else if (right !== undefined && compare(right, node) < 0) { // 左子節(jié)點(diǎn)大于根節(jié)點(diǎn),右子節(jié)點(diǎn)小于根節(jié)點(diǎn) heap[index] = right; heap[rightIndex] = node; index = rightIndex; } else { // Neither child is smaller. Exit. return; } } } function compare(a, b) { // Compare sort index first, then task id. const diff = a.sortIndex - b.sortIndex; return diff !== 0 ? diff : a.id - b.id; }
堆排序
利用最大/最小堆的特性,我們很容易就能實(shí)現(xiàn)對數(shù)組的排序,重復(fù)執(zhí)行 pop 就能進(jìn)行升序排列,如果要降序,使用最大堆即可,該操作時(shí)間復(fù)雜度為 nlogn 。
多叉堆
為了追求更優(yōu)的時(shí)間復(fù)雜度,我們可以將二叉堆改為多叉堆實(shí)現(xiàn),下圖為一個(gè)三叉堆:
與二叉堆不同的是對于含有 N 個(gè)元素的 d 叉堆(通常情況下 d >= 2),隨著 d 的增加,樹高 K = logdN 的斜率會(huì)下降,然而 d 越大,刪除操作的成本會(huì)更高。所以子元素不是越多越好,通常情況下三叉堆和四叉堆的應(yīng)用會(huì)比較常見。
在libev中有這么一段注釋 https://github.com/enki/libev/blob/master/ev.c#L2227,他提及了四叉樹相比二叉堆來說緩存更加友好。 根據(jù)benchmark,在 50000+ 個(gè) watchers 的場景下,四叉樹會(huì)有 5% 的性能優(yōu)勢。
/* * at the moment we allow libev the luxury of two heaps, * a small-code-size 2-heap one and a ~1.5kb larger 4-heap * which is more cache-efficient. * the difference is about 5% with 50000+ watchers. */
同樣 Go 語言中的定時(shí)器的 timersBucket 的數(shù)據(jù)結(jié)構(gòu)也采用了最小四叉堆。
感謝各位的閱讀,以上就是“結(jié)合React源碼如何快速掌握優(yōu)先隊(duì)列”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對結(jié)合React源碼如何快速掌握優(yōu)先隊(duì)列這一問題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。