Mapと構造体(JSON)の比較

直感的に感じる
Nodejsでは各データ構造の性能と特徴に注目することはめったにありませんが、今日はちょうどこの問題に遭遇して簡単に比較しました.ついでにメモを取って、必ずしも正しいとは限りません.nodejsコードの下では泥棒が遅くて、まだ降りていません.以下に、nodejsにおける構造体(オブジェクト)とmapの例を示す.

        let some_state_map = new Map();
        setInterval(()=>{
            some_state_map.set(`element${Math.ceil(Math.random()*1000)}`,Math.random());
        },1000);

        let some_state = {};
        setInterval(()=>{setInterval(()=> {
            some_state_map[`element${Math.ceil(Math.random() * 1000)}`] = Math.random();
        },1000);

上記のコードの役割は、1秒ごとに構造体またはオブジェクトに要素を挿入することです.何の違いもないように見えますが、実際には99%のシーンで両者を完全に置き換えることができます.しかし、両者の実現から見ると、彼らには一定の違いがあり、次に両者のデータ構造を分析する.
データ構造
こうぞうたい
c言語ではstructと配列の格納方式に本質的な違いはなく,どちらも順序格納である(そのような特殊な処理は考慮しない).これはstructの読み取り時間の複雑さがO(n)であることを意味し,想像していたO(1)ではなくnodejsなどの言語が実現する際に調整されたことを排除しない.structのメンバー変数が多いと性能が悪くなると予想されますが、一般的には構造体のメンバーは多くないので、一般的にはこの問題を心配する必要はありません.
Map
基本的にすべてのアルゴリズムブックではMap(Set)の読み取りの複雑さを1としているが,これが理想的である.Mapの考え方は簡単で、マッピングをすることです.一般的にはhash関数で、keyを入力して、アドレスやオフセット量を出力して、データを対応する位置に置くことができます.読み込み時にマッピングでオフセット量を見つけるだけでこの値を直接取得できます.しかしながら、実際の実装では、完全に衝突せず、結果が一定区間であることを保証できる関数を見つけることは不可能である(結局、記憶空間は限られている)ため、実際の実装スキームは一致しない.通常の方法は、競合を回避するためにチェーンテーブルを用い、必要な空間が相対的に受け入れられることを保証することであり、具体的には、ここでは説明しないが、この方法の読み書き時間の複雑さは、主にチェーンテーブルの長さとデータの分布に関係するO(1)とO(n)の間にある.もう1つの方法は,ツリー構造を直接採用し,この方法の読み書き複雑度はO(lgn)である.
両者の対比
nodejsでは両者を完全に入れ替えることができる場合が多いが,データが多い場合,例えばドット情報やユーザ情報については,Mapを用いることが望ましい.もちろん,ここでの解析は性能と使いやすさについて簡単に説明しただけである.次は簡単なテストです:構造体

//test-struct.js
const num = 1000000;
let a = {};
for(let i = 0;i

Map

//test-map.js
const num = 1000000;
let a = new Map();
for(let i = 0;i

テスト結果

node test-struct.js && node test-map.js
//=>
time cost: 735
time cost: 365