immutable-jsのMapデータ構造を読み取る
3504 ワード
この文章はImmutable.jsの実現メカニズムを深く探究することによって啓発され、自分のMapソースに対する解読と結び付けて、immutable-jsの中のmapデータ構造に対する理解を話します.
一、Vector Trieベクトル辞書ツリー
Trie辞書ツリーは、空間を時間と交換するツリー型データ構造であり、主な特徴は文字列の共通プレフィックスを利用してクエリ性能を向上させることである.たとえば、一連の文字列［abc］、「ab」、「bd」、「dda」の辞書ツリー構造は以下の通りです.
赤いノードは検索パスによって単語を構成することができます.このように「abc」があるかどうかを検索する時、各文字を逐一比較します.時間の複雑さはO(len)＝3、lenは検索する文字列の長さで、一般的に逐次比較すると、時間の複雑さはO(lenxn)＝4 x 3=12、nは文字列の個数です.明らかに辞書ツリーの方が効率がいいです.
Vector Trieは、Trieに基づいて、データパケット記憶をベクトル配列として実現し、各格納された値に対応するkeyは、配列の下付きにマッピングされる.例えば、このようなデータ構造｛000｝:“bana”、“001”:“grape”、“010”:“lemon”、“011”:“orange”、“100”:“apple”、各keyは配列のインデックス値にマッピングされ、このようにして簡単な2つの配列を生成するVector Trieはこのようなものである.
二、ビットパーティション
keyを数字にマッピングして、行列に対応してもいいです.例えば、一つのkeyが8899で5つの長さ(すなわち5進数)にマッピングされた数字は241044です.そうすると、彼は6つの深さのデータ構造を生成します.各階層のインデックスはそれぞれの数字です.このように各インデックスに数学計算を行います.immutable-jsでは効率の高いビット演算を使ってインデックスを生成します.データをパーティションします.例えば、8899はバイナリビットにマッピングされます.10010010010001、1はこのビットを表してデータがあります.0はデータがないことを表しています.このように、各層の配列長が7であれば、第1層の格納状況が直接ビット演算8899>>7で100100101(69)、第2層8899&127(Math.pow(2,7)-1)で100011(67)を得ることができる.ビット演算は、各値が格納されているかどうかを容易にすることができます.計算速度も数学演算よりずっと速いです.
三、Mapではどんな操作をしましたか?
Mapには、主なこれらのノードタイプがあります.ArayMapNode、ValueNode、BitmapIndexedNode、HashArayMapNode.set毎に、ノードタイプはこれらの間で変換される.また、最終的なentry配列が示す真の保存キーがあり、entry[0]はkey、entry[1]はvalueを記憶しています.ValueNodeは葉っぱノードとして見なされ、entry値が格納されている.まず、格納されたキーのペアが8より大きくない場合、生成されたentryは直接ArayMapNode配列に格納され、ArayMapNodeは_として作用する.rootノードが戻り、また値を格納し続けると、_を呼び出します.rootのudate方法、つまりArayMapNodeのudate方法は、8より多く保存されている場合、ValueNodeを作成し、udate方法を呼び出します.ここでmerge IntoNodeの操作を行います.つまり、同じインデックスがここにあるノードであれば、一度の合併操作を行い、BitmapIndexNodeを生成します.BitmapIndexedNodeは圧縮処理された層で、最大16個の長さのコンテンツを記憶し、bitmap属性はこの層の記憶状況を表している.例えば、1935909081の値は「11100100010101000 00011」です.最大32位です.足りないなら、上位0位に相当します.0を除くと、1の数がこの層の実際に記憶されている個数です.なぜ圧縮されたのかというと、このbitmapはこの層の記憶状況を表しています.長さ32の配列の各々の記憶状況ですが、この層の実際の記憶の数はせいぜいその半分です.空間占有と検索効率を減らすために、保存しないビットを記録する必要がありません.bitmapには何の効果がありますか?続けて見て、データを追加して、BitmapIndexededNodeの層のデータ量を16以上にします.この時に一回expandNodesを変換してノードを展開します.この層の構造をHashArayMapNodeに変えます.これは長さ32の配列です.bitmapに記録されているビットの記憶状況は、前のデータを一つずつ32桁のグループに入れて対応するところです.値がないところはundefinedです.その後、HashArayMapNodeの保存数が16以下に減少したら、またpackNodesをBitmapIndexedNodeに変更します.Mapでは、setごとに対応する層のノードをタイプ変換し、udateNodeという方法は、影響を受けるノードが新たな構造を生成して戻ってきます.他の層のノードに影響を与えずに、構造共有を実現します.この中にはハシュ衝突の処理を行うノードもあります.
四、分析の下で生成されたMapデータ構造
Mapではデータストアの位置を見つけるために、多くのビット操作が使われていますが、現在はmapデータのセットを分析して、どのように計算されているかを確認してみます.ここで使用する定数は、31と5はTrieUtils.jsファイルにあります.
例えば「KEY 6787241」というノードを選んで分析します.そのhashはこのように計算されます.
私たちはこのhashから第一階である_を計算しました.rootの下の位置:
これは確かに対応する位置に置いてあります.HasharrayMapNodeでは、HasharrayMapNodeで12の位置はどう計算されますか?
このビットmap 524352を見に来てください.
データを保存したのは2人だけと見られます.不定長の幅をサポートするために、位置の計算は後から前に計算します.データを格納する場合は下から7番目で、indexが6番目と後ろから20番目で、indexが19に相当します.その後、hash:785947024と-1378605744が対応するビットにあるかどうかを再計算します.
1階に深く入るごとに、ビットを5ビット右に移動し、上31と対応する位置を算出する.なぜ31と5ですか?コードで見られます.
上の二つの定数です.785947024のバイナリは「1011101100010001000」で、31のバイナリは「000000 00000011111」です.さらに5桁シフトして31の後に「01100」12となります.2^5=32ですから、5桁のバイナリは32個の数を保存できます.私達の各層の最大32個の状況を満足することができます.32はどうやって来ましたか?ビットパーティションの検索更新効率を統計しました.
64ビットの照会速度が一番速く、8ビットの更新速度が一番速いと見られます.immutable-js選択32は、実際の使用において、クエリの周波数が更新よりも多いため、クエリの速度がより優れており、更新速度が最も悪い32ではない.
一、Vector Trieベクトル辞書ツリー
Trie辞書ツリーは、空間を時間と交換するツリー型データ構造であり、主な特徴は文字列の共通プレフィックスを利用してクエリ性能を向上させることである.たとえば、一連の文字列［abc］、「ab」、「bd」、「dda」の辞書ツリー構造は以下の通りです.
赤いノードは検索パスによって単語を構成することができます.このように「abc」があるかどうかを検索する時、各文字を逐一比較します.時間の複雑さはO(len)＝3、lenは検索する文字列の長さで、一般的に逐次比較すると、時間の複雑さはO(lenxn)＝4 x 3=12、nは文字列の個数です.明らかに辞書ツリーの方が効率がいいです.
Vector Trieは、Trieに基づいて、データパケット記憶をベクトル配列として実現し、各格納された値に対応するkeyは、配列の下付きにマッピングされる.例えば、このようなデータ構造｛000｝:“bana”、“001”:“grape”、“010”:“lemon”、“011”:“orange”、“100”:“apple”、各keyは配列のインデックス値にマッピングされ、このようにして簡単な2つの配列を生成するVector Trieはこのようなものである.
二、ビットパーティション
keyを数字にマッピングして、行列に対応してもいいです.例えば、一つのkeyが8899で5つの長さ(すなわち5進数)にマッピングされた数字は241044です.そうすると、彼は6つの深さのデータ構造を生成します.各階層のインデックスはそれぞれの数字です.このように各インデックスに数学計算を行います.immutable-jsでは効率の高いビット演算を使ってインデックスを生成します.データをパーティションします.例えば、8899はバイナリビットにマッピングされます.10010010010001、1はこのビットを表してデータがあります.0はデータがないことを表しています.このように、各層の配列長が7であれば、第1層の格納状況が直接ビット演算8899>>7で100100101(69)、第2層8899&127(Math.pow(2,7)-1)で100011(67)を得ることができる.ビット演算は、各値が格納されているかどうかを容易にすることができます.計算速度も数学演算よりずっと速いです.
三、Mapではどんな操作をしましたか?
Mapには、主なこれらのノードタイプがあります.ArayMapNode、ValueNode、BitmapIndexedNode、HashArayMapNode.set毎に、ノードタイプはこれらの間で変換される.また、最終的なentry配列が示す真の保存キーがあり、entry[0]はkey、entry[1]はvalueを記憶しています.ValueNodeは葉っぱノードとして見なされ、entry値が格納されている.まず、格納されたキーのペアが8より大きくない場合、生成されたentryは直接ArayMapNode配列に格納され、ArayMapNodeは_として作用する.rootノードが戻り、また値を格納し続けると、_を呼び出します.rootのudate方法、つまりArayMapNodeのudate方法は、8より多く保存されている場合、ValueNodeを作成し、udate方法を呼び出します.ここでmerge IntoNodeの操作を行います.つまり、同じインデックスがここにあるノードであれば、一度の合併操作を行い、BitmapIndexNodeを生成します.BitmapIndexedNodeは圧縮処理された層で、最大16個の長さのコンテンツを記憶し、bitmap属性はこの層の記憶状況を表している.例えば、1935909081の値は「11100100010101000 00011」です.最大32位です.足りないなら、上位0位に相当します.0を除くと、1の数がこの層の実際に記憶されている個数です.なぜ圧縮されたのかというと、このbitmapはこの層の記憶状況を表しています.長さ32の配列の各々の記憶状況ですが、この層の実際の記憶の数はせいぜいその半分です.空間占有と検索効率を減らすために、保存しないビットを記録する必要がありません.bitmapには何の効果がありますか?続けて見て、データを追加して、BitmapIndexededNodeの層のデータ量を16以上にします.この時に一回expandNodesを変換してノードを展開します.この層の構造をHashArayMapNodeに変えます.これは長さ32の配列です.bitmapに記録されているビットの記憶状況は、前のデータを一つずつ32桁のグループに入れて対応するところです.値がないところはundefinedです.その後、HashArayMapNodeの保存数が16以下に減少したら、またpackNodesをBitmapIndexedNodeに変更します.Mapでは、setごとに対応する層のノードをタイプ変換し、udateNodeという方法は、影響を受けるノードが新たな構造を生成して戻ってきます.他の層のノードに影響を与えずに、構造共有を実現します.この中にはハシュ衝突の処理を行うノードもあります.
四、分析の下で生成されたMapデータ構造
Mapではデータストアの位置を見つけるために、多くのビット操作が使われていますが、現在はmapデータのセットを分析して、どのように計算されているかを確認してみます.ここで使用する定数は、31と5はTrieUtils.jsファイルにあります.
export const SHIFT = 5; // Resulted in best performance after ______?
export const SIZE = 1 << SHIFT;
export const MASK = SIZE - 1;例えば「KEY 6787241」というノードを選んで分析します.そのhashはこのように計算されます.
私たちはこのhashから第一階である_を計算しました.rootの下の位置:
これは確かに対応する位置に置いてあります.HasharrayMapNodeでは、HasharrayMapNodeで12の位置はどう計算されますか?
このビットmap 524352を見に来てください.
データを保存したのは2人だけと見られます.不定長の幅をサポートするために、位置の計算は後から前に計算します.データを格納する場合は下から7番目で、indexが6番目と後ろから20番目で、indexが19に相当します.その後、hash:785947024と-1378605744が対応するビットにあるかどうかを再計算します.
1階に深く入るごとに、ビットを5ビット右に移動し、上31と対応する位置を算出する.なぜ31と5ですか?コードで見られます.
上の二つの定数です.785947024のバイナリは「1011101100010001000」で、31のバイナリは「000000 00000011111」です.さらに5桁シフトして31の後に「01100」12となります.2^5=32ですから、5桁のバイナリは32個の数を保存できます.私達の各層の最大32個の状況を満足することができます.32はどうやって来ましたか?ビットパーティションの検索更新効率を統計しました.
64ビットの照会速度が一番速く、8ビットの更新速度が一番速いと見られます.immutable-js選択32は、実際の使用において、クエリの周波数が更新よりも多いため、クエリの速度がより優れており、更新速度が最も悪い32ではない.