これは、再帰について友人と議論しているときに出てきました。
を構築してみませんか 再帰的プログラミングの演習として 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 


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


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




システムが異なれば実行方法も異なる可能性がありますが、かかった時間の比率は

std 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 つの文字列を連結しています。

文字列の連結には
が必要なためコストがかかります

結合された文字列全体に適合する新しい文字列バッファを作成します
個々の文字列を新しく作成したバッファにコピーします
自分自身でバッファを使用し、そこにデータを直接書き込むことで、次の結果が得られる可能性があります

パフォーマンスの向上。大きなバッファ（たとえば 80 文字）を作成できるため

そして、80 文字が足りなくなったら、さらに 80 文字が収まるように新しいバッファーを作成します。

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

それらの操作を削減します。

もう 1 つの遅延の可能性は、再帰的なプロセス自体です。具体的には

時間がかかる関数呼び出し。 json_stringify(val)
 という関数呼び出しを考えてみましょう。
パラメーターが 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 エンジン 自体に更新が行われた可能性があります。

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

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