成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

讀懂immutable-js中的Map數(shù)據(jù)結(jié)構(gòu)

jone5679 / 530人閱讀

摘要：一向量字典樹字典樹，一種用空間換取時(shí)間的樹形數(shù)據(jù)結(jié)構(gòu)，主要特點(diǎn)是利用字符串的公共前綴來挺升查詢性能。還有最終的數(shù)組表示的真實(shí)存儲(chǔ)的鍵值，存儲(chǔ)了，存儲(chǔ)了。這其中還有一種節(jié)點(diǎn)進(jìn)行了沖突的處理。

本文受深入探究Immutable.js的實(shí)現(xiàn)機(jī)制這篇文章啟發(fā)，結(jié)合自己對Map源碼的解讀，談?wù)勎覍mmutable-js中map數(shù)據(jù)結(jié)構(gòu)的理解，若有不正確的地方，歡迎指正。

一、Vector Trie 向量字典樹

Trie 字典樹，一種用空間換取時(shí)間的樹形數(shù)據(jù)結(jié)構(gòu)，主要特點(diǎn)是利用字符串的公共前綴來挺升查詢性能。比如一組字符串 ["abc","ab","bd","dda"] 它的字典樹結(jié)構(gòu)如下：

紅色節(jié)點(diǎn)代表按查找路徑下來可以組成一個(gè)單詞，這樣在查找是否存在"abc"時(shí)，每個(gè)字符逐個(gè)進(jìn)行對比，時(shí)間復(fù)雜度為O(len) = 3，len為要查找的字符串的長度，而按照一般逐個(gè)對比的方式，時(shí)間復(fù)雜度為O(lenxn) = 4x3 = 12，n為字符串的個(gè)數(shù)，顯然字典樹的方式效率更高。

Vector Trie 是在 Trie 的基礎(chǔ)上實(shí)現(xiàn)了以向量數(shù)組的形式進(jìn)行數(shù)據(jù)分組存儲(chǔ)，每一個(gè)被存儲(chǔ)的值所對應(yīng)的key都映射為數(shù)組的下標(biāo)。
比如這樣的數(shù)據(jù)結(jié)構(gòu) {‘000’: ‘banana’, ‘001’: ‘grape’, ‘010’: ‘lemon’, ‘011’: ‘orange’, ‘100’: ‘a(chǎn)pple’}，每個(gè)key映射為數(shù)組的索引值，這樣生成簡單的兩位數(shù)組的Vector Trie是這樣子的：

二、位分區(qū)

我們可以將key映射為數(shù)字，然后再對應(yīng)到數(shù)組中，比如一個(gè)key為 8899 映射為 5 個(gè)長度（即5進(jìn)制）的數(shù)字是241044, 那么他要生成深度為6的數(shù)據(jù)結(jié)構(gòu)，每一層的索引就是每位的數(shù)字，這樣對每個(gè)索引都要進(jìn)行數(shù)學(xué)計(jì)算，而immutable-js中使用了效率更高的位運(yùn)算來生成索引，將數(shù)據(jù)進(jìn)行分區(qū)。比如，8899 映射為二進(jìn)制位：10001011000011，1代表此位有數(shù)據(jù)，0代表沒有數(shù)據(jù)。這樣如果每層的數(shù)組長度是7，第一層的存儲(chǔ)情況可以直接位運(yùn)算 8899 >> 7 得到 1000101（69），第二層 8899 & 127 (Math.pow(2, 7) - 1) 得到 1000011 (67)。
位運(yùn)算可以很方便得到每位是否存儲(chǔ)值的情況，計(jì)算速度也要比數(shù)學(xué)運(yùn)算快很多。

三、Map中做了什么操作

Map中有主要的這幾種節(jié)點(diǎn)類型：ArrayMapNode，ValueNode，BitmapIndexedNode，HashArrayMapNode。在每次set時(shí)，節(jié)點(diǎn)類型會(huì)在這幾個(gè)之間轉(zhuǎn)換。還有最終的entry數(shù)組表示的真實(shí)存儲(chǔ)的鍵值，entry[0]存儲(chǔ)了key，entry[1]存儲(chǔ)了value。ValueNode可以看作葉子節(jié)點(diǎn)，存儲(chǔ)了entry值。
首先，如果存儲(chǔ)的鍵值對不大于8，那么生成entry直接存儲(chǔ)在ArrayMapNode數(shù)組中，ArrayMapNode作為_root節(jié)點(diǎn)返回，再繼續(xù)存儲(chǔ)值，會(huì)調(diào)用_root的update方法，也就是ArrayMapNode的update方法，如果存儲(chǔ)的數(shù)量大于8，會(huì)創(chuàng)建ValueNode，并調(diào)用它的update方法，在這里會(huì)進(jìn)行一個(gè)mergeIntoNode操作，即如果有相同索引到此處的節(jié)點(diǎn)，那么要進(jìn)行一次合并操作，合并后會(huì)生成BitmapIndexedNode。
BitmapIndexedNode是經(jīng)過壓縮處理的層，最多存儲(chǔ)16個(gè)長度的內(nèi)容，bitmap屬性就表示了這個(gè)層的存儲(chǔ)情況。比如值為1935909891它的存儲(chǔ)情況是"1110011011000111010010000000011"，最多32位，不足的話，相當(dāng)于高位補(bǔ)0。去除0后，1的數(shù)量就是這層實(shí)際存儲(chǔ)的個(gè)數(shù)。為什么說它經(jīng)過壓縮呢，因?yàn)檫@個(gè)bitmap表示了這層的存儲(chǔ)情況，是長度為32的數(shù)組的每位的存儲(chǔ)情況，但這層實(shí)際存儲(chǔ)的數(shù)量最多只是它的一半，為了減少空間占用和查找效率，就沒必要記錄不存儲(chǔ)的位了，那就有疑問了，那直接往數(shù)組里存儲(chǔ)就行了，要bitmap有什么用，我們繼續(xù)往下看，再新增數(shù)據(jù)，使BitmapIndexedNode這層的數(shù)據(jù)量超過16，此時(shí)就會(huì)進(jìn)行一次轉(zhuǎn)換expandNodes展開節(jié)點(diǎn)操作，將這層的結(jié)構(gòu)轉(zhuǎn)為HashArrayMapNode，這是一個(gè)長度為32的數(shù)組，此時(shí)，bitmap記錄的位存儲(chǔ)情況就是把之前的數(shù)據(jù)一個(gè)一個(gè)放到32位數(shù)組里對應(yīng)的地方，沒有值的地方就是undefined。
再往后如果HashArrayMapNode的存儲(chǔ)數(shù)量降低小于16了，又會(huì)進(jìn)行packNodes轉(zhuǎn)為BitmapIndexedNode。
Map中，每次set都將對應(yīng)的層的節(jié)點(diǎn)進(jìn)行類型轉(zhuǎn)換，updateNode這個(gè)方法會(huì)將受影響的節(jié)點(diǎn)生成新的結(jié)構(gòu)返回，不影響其它層的節(jié)點(diǎn)，這就實(shí)現(xiàn)了結(jié)構(gòu)共享。
這其中還有一種節(jié)點(diǎn)HashCollisionNode進(jìn)行了hash沖突的處理。

四、分析下生成的Map數(shù)據(jù)結(jié)構(gòu)

在Map中為了找到數(shù)據(jù)存儲(chǔ)位置，使用了很多的位操作，現(xiàn)在對一組map數(shù)據(jù)進(jìn)行分析，看看它是如何進(jìn)行計(jì)算的。這里用到的常量，
31 和 5 在TrieUtils.js文件中:

export const SHIFT = 5; // Resulted in best performance after ______?
export const SIZE = 1 << SHIFT;
export const MASK = SIZE - 1;

我們生成500個(gè)長度的map數(shù)據(jù)結(jié)構(gòu)，使它包含BitmapIndexedNode，HashArrayMapNode這幾種結(jié)構(gòu)：

比如我們選取"KEY6787241"這個(gè)節(jié)點(diǎn)進(jìn)行分析，它的hash是這樣計(jì)算出來的：

我們根據(jù)這個(gè)hash計(jì)算出它在第一層即_root下面的位置：

看到它確實(shí)放在了對應(yīng)位置下的HashArrayMapNode中，那在HashArrayMapNode中12的位置是怎么算出來的呢，我們執(zhí)行這樣的操作：

然后來看看這個(gè)bitmap 524352:

可以看出它只有兩位保存了數(shù)據(jù)。為了支持不定長的寬度，位置的計(jì)算是從后往前算的，那么，存儲(chǔ)數(shù)據(jù)的情況就是倒數(shù)第7位，相當(dāng)于index為6和倒數(shù)第20位，相當(dāng)于index為19，那么我們再計(jì)算下hash：785947024和-137605744是否在對應(yīng)位置：

每深入一層，將位右移動(dòng)5位，并且與上31來算出對應(yīng)位置。
那為啥是 31 和 5 呢，在代碼中可以看到：

就是上面對應(yīng)的兩個(gè)常量。
785947024的二進(jìn)制是"101110110110001001100110010000"，31的二進(jìn)制是"000000000000000000000000011111"，&，位與操作后意思就是留下最后的5位，"10000" 16。再位移5位并位與31后就是，"01100" 12。2 ^ 5 = 32，所以5位二進(jìn)制就能保存32個(gè)數(shù)，也就能滿足我們每一層最多32個(gè)的情況。
那32是怎么來的呢，這里統(tǒng)計(jì)了位分區(qū)的查找更新效率情況：

可以看到64位查詢速度最快，8位更新速度最快。immutable-js選擇32是因?yàn)閷?shí)際使用中，查詢的頻率要比更新多，所以選擇了查詢速度較優(yōu)，更新速度不是最差的32。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/98437.html

相關(guān)文章

  • 前端進(jìn)階（11） - js 數(shù)據(jù)結(jié)構(gòu)類型擴(kuò)展：immutable-js

    摘要：數(shù)據(jù)結(jié)構(gòu)類型擴(kuò)展相對之類的強(qiáng)類型語言，有一點(diǎn)很大的區(qū)別就是，數(shù)據(jù)結(jié)構(gòu)只有與，并且都是動(dòng)態(tài)可變的，而有等數(shù)據(jù)結(jié)構(gòu)。所以，為了能在中也使用這些數(shù)據(jù)結(jié)構(gòu)，就應(yīng)運(yùn)而生。擴(kuò)充了中的不可變集合，即一旦創(chuàng)建就不能改變的數(shù)據(jù)類型。 js 數(shù)據(jù)結(jié)構(gòu)類型擴(kuò)展：immutable-js 相對 java、.net 之類的強(qiáng)類型語言，js 有一點(diǎn)很大的區(qū)別就是，數(shù)據(jù)結(jié)構(gòu)只有 array 與 object，并且都...

    BLUE 評論0 收藏0

  • 筆記, immutable-js 基礎(chǔ)操作

    摘要：這篇文章是一些操作的整理目前只有基本的操作文檔請查看使用過程中遇到的寫法我會(huì)不會(huì)增加在后邊當(dāng)中不可變數(shù)據(jù)有點(diǎn)不適應(yīng)需要借鑒一些中的內(nèi)容更新六月份到十月份我們完成了不可變數(shù)據(jù)的重構(gòu)配合簡聊的巨大的單一可以整理出來一些常用的方法示例代碼用的是 這篇文章是 immutable-js 一些操作的整理, 目前只有基本的操作:文檔請查看: http://facebook.github.io/imm...

    alexnevsky 評論0 收藏0

  • immer.js 簡介及源碼解析

    摘要：例如維護(hù)一份在內(nèi)部，來判斷是否有變化，下面這個(gè)例子就是一個(gè)構(gòu)造函數(shù)，如果將它的實(shí)例傳入對象作為第一個(gè)參數(shù)，就能夠后面的處理對象中使用其中的方法上面這個(gè)構(gòu)造函數(shù)相比源代碼省略了很多判斷的部分。 showImg(https://segmentfault.com/img/bV27Dy?w=1400&h=544); 博客鏈接：下一代狀態(tài)管理工具 immer 簡介及源碼解析 JS 里面的變量類...

    Profeel 評論0 收藏0

  • immutability-helper 學(xué)習(xí)筆記 -1

    摘要：張偉輸出結(jié)果這樣就實(shí)現(xiàn)了在源數(shù)據(jù)的基礎(chǔ)上更改了值并且輸出一個(gè)與之地址完全不同數(shù)組。 本來想將有關(guān)于immutability-helper的博文放在一起學(xué)React系列博文中，但是考慮到該插件不僅僅在React中實(shí)用到，所以就單獨(dú)拿出來分兩期寫。 發(fā)現(xiàn)問題 immutability意為不變，不變性，永恒性。至于該插件能做什么，我想它的作者對它的標(biāo)注已經(jīng)很明確了mutate a copy ...

    xbynet 評論0 收藏0

  • React性能優(yōu)化

    摘要：當(dāng)大家考慮在項(xiàng)目中使用的時(shí)候，第一個(gè)問題往往是他們的應(yīng)用的速度和響應(yīng)是否能和非版一樣，每當(dāng)狀態(tài)改變的時(shí)候就重新渲染組件的整個(gè)子樹，讓大家懷疑這會(huì)不會(huì)對性能造成負(fù)面影響。 當(dāng)大家考慮在項(xiàng)目中使用 React 的時(shí)候，第一個(gè)問題往往是他們的應(yīng)用的速度和響應(yīng)是否能和非 React 版一樣，每當(dāng)狀態(tài)改變的時(shí)候就重新渲染組件的整個(gè)子樹，讓大家懷疑這會(huì)不會(huì)對性能造成負(fù)面影響。React 用了一些黑...

    n7then 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<