JSON.stringify との競合 - カスタムの構築による

これは、再帰について友人と議論しているときに出てきました。
を構築してみませんか 再帰的プログラミングの演習として Javascript JSON.stringify メソッドを使用しますか?素晴らしいようです
アイデア。

私はすぐに最初のバージョンを草稿しました。そしてそれは恐ろしいパフォーマンスでした！
所要時間は標準の約 4 倍でした JSON.stringify.

最初の草案

function json_stringify(obj) {
  if (typeof obj == "number" || typeof obj == "boolean") {
    return String(obj);
  }

  if (typeof obj == "string") {
    return `"${obj}"`;
  }

  if (Array.isArray(obj)) {
    return "[" + obj.map(json_stringify).join(",") + "]";
  }

  if (typeof obj === "object") {
    const properties_str = Object.entries(obj)
      .map(([key, val]) => {
        return `"${key}":${json_stringify(val)}`;
      })
      .join(",");
    return "{" + properties_str + "}";
  }
}

以下を実行すると、json_stringify が次のように動作することがわかります

const { assert } = require("console");
const test_obj = {
  name: "John Doe",
  age: 23,
  hobbies: ["football", "comet study"]
};

assert(json_stringify(test_obj) === JSON.stringify(test_obj))

より多くのシナリオをテストし、複数回実行して
がどのように機能するかについての平均的なアイデアを得る。 スクリプトが実行されるので、簡単なテスト スクリプトを作成しました!

簡単なテストスクリプト

function validity_test(fn1, fn2, test_values) {
  for (const test_value of test_values) {
    assert(fn1(test_value) == fn2(test_value));
  }
}

function time(fn, num_runs = 1, ...args) {
  const start_time = Date.now()

  for (let i = 0; i < num_runs; i++) {
    fn(...args);
  }

  const end_time = Date.now()
  return end_time - start_time
}


function performance_test(counts) {
  console.log("Starting performance test with", test_obj);

  for (const count of counts) {
    console.log("Testing", count, "times");

    const duration_std_json = time(JSON.stringify.bind(JSON), count, test_obj);
    console.log("\tStd lib JSON.stringify() took", duration_std_json, "ms");

    const duration_custom_json = time(json_stringify, count, test_obj);
    console.log("\tCustom json_stringify() took", duration_custom_json, "ms");
  }
}

const test_obj = {} // a deeply nested JS object, ommitted here for brevity 
const test_values = [
  12,
  "string test",
  [12, 34, 1],
  [12, true, 1, false],
  test_obj
];

validity_test(JSON.stringify, json_stringify, test_values);
performance_test([1000, 10_000, 100_000, 1000_000]);

これを実行すると、次のようなタイミングが得られます。

Testing 1000 times
    Std lib JSON.stringify() took 5 ms
    Custom json_stringify() took 20 ms
Testing 10000 times
    Std lib JSON.stringify() took 40 ms
    Custom json_stringify() took 129 ms
Testing 100000 times
    Std lib JSON.stringify() took 388 ms
    Custom json_stringify() took 1241 ms
Testing 1000000 times
    Std lib JSON.stringify() took 3823 ms
    Custom json_stringify() took 12275 ms

システムが異なれば実行方法も異なる場合がありますが、かかった時間の比率は
標準の JSON.strngify からカスタム json_stringify の値までは
程度になるはずです 1:3 - 1:4

興味深いケースでは、これも異なる可能性があります。
についてさらに詳しく知りたい方は続きをお読みください。 それ!

パフォーマンスの向上

最初に修正できるのは、map 関数の使用です。
を作成します 古い配列から新しい配列に。オブジェクトの場合、
の配列を作成しています。 オブジェクト エントリを含む配列からの JSON 文字列化されたオブジェクト プロパティ。

配列要素の文字列化でも同様のことが起こります。

配列内の要素、またはオブジェクトのエントリをループする必要があります。でも
JSON 文字列化された部分を結合するためだけに、別の配列の作成をスキップできます。

更新バージョンは次のとおりです (簡潔にするために、変更された部分のみを示しています)

function json_stringify(val) {
  if (typeof val === "number" || typeof val === "boolean") {
    return String(val);
  }

  if (typeof val === "string") {
    return `"${val}"`;
  }

  if (Array.isArray(val)) {
    let elements_str = "["

    let sep = ""
    for (const element of val) {
      elements_str += sep + json_stringify(element)
      sep = ","
    }
    elements_str += "]"

    return elements_str
  }

  if (typeof val === "object") {
    let properties_str = "{"

    let sep = ""
    for (const key in val) {
      properties_str += sep + `"${key}":${json_stringify(val[key])}`
      sep = ","
    }
    properties_str += "}"

    return properties_str;
  }
}

これがテスト スクリプトの出力です

Testing 1000 times
        Std lib JSON.stringify() took 5 ms
        Custom json_stringify() took 6 ms
Testing 10000 times
        Std lib JSON.stringify() took 40 ms
        Custom json_stringify() took 43 ms
Testing 100000 times
        Std lib JSON.stringify() took 393 ms
        Custom json_stringify() took 405 ms
Testing 1000000 times
        Std lib JSON.stringify() took 3888 ms
        Custom json_stringify() took 3966 ms

これでかなり良くなりました。カスタム json_stringify にはわずか 3 ミリ秒しかかかりません
深くネストされたオブジェクトを 10,000 回文字列化するには、JSON.stringify を超えます。
これは完璧ではありませんが、許容できる遅延です。

もっと絞り出す？？

現在の遅延は、すべての文字列の作成と連結が原因である可能性があります
それが起こっているのです。 elements_str += sep + json_stringify(element)
を実行するたびに 3 つの文字列を連結しています。

文字列の連結は、

が必要なためコストがかかります

1. 結合された文字列全体に適合する新しい文字列バッファを作成します
2. 個別の文字列を新しく作成したバッファにコピーします

自分自身でバッファを使用し、そこにデータを直接書き込むことで、次のことが得られる可能性があります
パフォーマンスの向上。大きなバッファ (たとえば 80 文字) を作成できるため
そして、80 文字が足りなくなったら、さらに 80 文字が収まるように新しいバッファーを作成します。

データの再割り当て/コピーを完全に回避するわけではありませんが、必ず回避します
それらの操作を削減します。

もう 1 つの遅延の可能性は、再帰的なプロセス自体です。具体的には
時間がかかる関数呼び出し。関数呼び出し json_stringify(val)
を考えてみましょう。 パラメータが 1 つだけあります。

関数呼び出しについて

手順は次のとおりです

1. リターンアドレスをスタックにプッシュします
2. 引数の参照をスタックにプッシュします
3. 呼び出された関数内
   1. スタックからパラメータ参照をポップします
   2. リターンアドレスをスタックからポップします
   3. 戻り値 (文字列化された部分) をスタックにプッシュします
4. 呼び出し関数内
   1. 関数によって返された値をスタックからポップオフします

これらの操作はすべて、関数呼び出しが確実に行われるようにするために発生し、これにより CPU が追加されます
費用がかかります。

json_string の非再帰アルゴリズムを作成すると、これらすべての操作が実行されます
上記の関数呼び出し (そのような呼び出しの数を掛けたもの) は
となります。 何もなくなりました。

これは将来の試みとなる可能性があります。

NodeJsのバージョンの違い

ここで最後に注意すべき点が 1 つあります。次のテスト スクリプトの出力を考えてみましょう

Testing 1000 times
        Std lib JSON.stringify() took 8 ms
        Custom json_stringify() took 8 ms
Testing 10000 times
        Std lib JSON.stringify() took 64 ms
        Custom json_stringify() took 51 ms
Testing 100000 times
        Std lib JSON.stringify() took 636 ms
        Custom json_stringify() took 467 ms
Testing 1000000 times
        Std lib JSON.stringify() took 6282 ms
        Custom json_stringify() took 4526 ms

カスタム json_stringify は NodeJs 標準よりも優れたパフォーマンスを示しただけでしょうか
JSON.stringify???

そうですね！ただし、これは NodeJs の古いバージョン (v18.20.3) です。結局のところ、
このバージョン (おそらくそれ以下のバージョンでも) カスタムメイドの json_stringify は機能します
標準ライブラリよりも高速です!

この記事のすべてのテスト (最後のテストを除く) は
で行われました。 ノード v22.6.0

JSON.stringify のパフォーマンスが v18 から v22 に向上しました。これはとても素晴らしいです

スクリプトのパフォーマンスが NodeJs v22 でより良くなったことに注意することも重要です。
つまり、NodeJs によってランタイムの全体的なパフォーマンスも向上したということです。
おそらく、基礎となる V8 エンジン 自体に更新が行われた可能性があります。

そうですね、これは私にとって楽しい経験でした。そしてそれが
のためになることを願っています あなたも。そして、このすべての楽しみの真っ只中に、私たちは一つか二つのことを学びました!

構築を続け、テストを続けてください!

以上がJSON.stringify との競合 - カスタムの構築によるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。