Dies kam während einer Diskussion mit meinem Freund über Rekursion zur Sprache. Warum nicht
bauen? eine Javascript JSON.stringify-Methode als rekursive Programmierübung? Scheint großartig zu sein
Idee.

Ich habe schnell die erste Version entworfen. Und es hat schrecklich funktioniert! Der
Die benötigte Zeit war etwa viermal so hoch wie beim Standard JSON.stringify.

Der erste Entwurf

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   "}";
  }
}

Indem wir Folgendes ausführen, können wir sehen, dass unser json_stringify wie folgt funktioniert:
erwartet.

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))

Um mehr Szenarien und mehrere Durchläufe zu testen, um eine durchschnittliche Vorstellung davon zu bekommen, wie unsere
Skript läuft, wir haben ein einfaches Testskript erstellt!

Ein einfaches Testskript

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 


Wenn wir das ausführen, erhalten wir die Zeitangaben wie folgt.



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




Es kann auf verschiedenen Systemen unterschiedlich laufen, aber das Verhältnis der benötigten Zeit 

von std JSON.strngify zu unserem benutzerdefinierten json_stringify sollte ungefähr 
 sein
1:3 - 1:4

In einem interessanten Fall könnte es auch anders sein. Lesen Sie weiter, um mehr über 
 zu erfahren
Das!

  
  
  Verbesserung der Leistung


Das erste, was behoben werden könnte, ist die Verwendung der Kartenfunktion. Es erstellt

neues Array vom alten. In unserem Fall von Objekten wird ein Array von
 erstellt.
JSON-stringifizierte Objekteigenschaften aus dem Array, das Objekteinträge enthält.

Ähnliches passiert auch mit der Stringifizierung der Array-Elemente.

Wir müssen die Elemente in einem Array oder die Einträge eines Objekts durchlaufen! Aber

Wir können die Erstellung eines weiteren Arrays überspringen, nur um die JSON-String-Teile zu verbinden.

Hier ist die aktualisierte Version (der Kürze halber werden nur die geänderten Teile angezeigt)



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;
  }
}




Und hier ist jetzt die Ausgabe des Testskripts



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




Das sieht jetzt viel besser aus. Unser benutzerdefiniertes json_stringify benötigt nur 3 ms

mehr als JSON.stringify, um ein tief verschachteltes Objekt 10.000 Mal zu stringisieren.

Obwohl dies nicht perfekt ist, ist es eine akzeptable Verzögerung.

  
  
  Mehr rausquetschen??


Die aktuelle Verzögerung könnte auf die gesamte Erstellung und Verkettung von Zeichenfolgen zurückzuführen sein 

das passiert. Jedes Mal, wenn wir elements_str = sep json_stringify(element)
 ausführen
Wir verketten 3 Zeichenfolgen.

Das Verketten von Zeichenfolgen ist kostspielig, da es
 erfordert.


Erstellen eines neuen Zeichenfolgenpuffers, der in die gesamte kombinierte Zeichenfolge passt
Einzelne Zeichenfolgen in den neu erstellten Puffer kopieren


Wenn wir selbst einen Puffer verwenden und die Daten direkt dorthin schreiben, erhalten wir möglicherweise

eine Leistungssteigerung. Da wir einen großen Puffer erstellen können (sagen wir 80 Zeichen)

und dann neue Puffer erstellen, um 80 Zeichen mehr aufzunehmen, wenn sie aufgebraucht sind.

Wir werden die Neuzuweisung/das Kopieren von Daten nicht ganz vermeiden, aber wir werden

Reduzierung dieser Vorgänge.

Eine weitere mögliche Verzögerung ist der rekursive Prozess selbst! Insbesondere die

Funktionsaufruf, der Zeit kostet. Betrachten Sie unseren Funktionsaufruf json_stringify(val)

das nur einen Parameter hat.

  
  
  Funktionsaufrufe verstehen


Die Schritte wären


Rücksprungadresse auf den Stapel übertragen
Schieben Sie die Argumentreferenz auf den Stapel
In der aufgerufenen Funktion


Entfernen Sie die Parameterreferenz vom Stapel
Entfernen Sie die Absenderadresse vom Stapel
Schiebe den Rückgabewert (den stringifizierten Teil) auf den Stapel


In der aufrufenden Funktion


Entfernen Sie den von der Funktion zurückgegebenen Wert vom Stapel




Alle diese Vorgänge werden durchgeführt, um sicherzustellen, dass Funktionsaufrufe stattfinden, und dies erhöht die CPU

Kosten.

Wenn wir einen nicht rekursiven Algorithmus von json_string erstellen, überprüfen Sie alle diese Vorgänge

oben für Funktionsaufrufe aufgeführt (mal die Anzahl solcher Aufrufe) wäre

auf Null reduziert.

Dies kann ein zukünftiger Versuch sein. 

  
  
  NodeJs-Versionsunterschiede


Eine letzte Sache, die hier zu beachten ist. Betrachten Sie die folgende Ausgabe des Testskripts



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




Hat unser benutzerdefiniertes json_stringify einfach eine bessere Leistung als der NodeJs-Standard?

JSON.stringify???

Na ja! Dies ist jedoch eine ältere Version von NodeJs (v18.20.3). Es stellt sich heraus, dass für

In dieser Version (und vielleicht auch in einer niedrigeren Version) funktioniert unser maßgeschneidertes json_stringify

schneller als die Standardbibliothek!

Alle Tests für diesen Artikel (außer diesem letzten) wurden mit 
 durchgeführt
Knoten v22.6.0

Die Leistung von JSON.stringify ist von v18 auf v22 gestiegen. Das ist so toll

Es ist auch wichtig zu beachten, dass unser Skript in NodeJs v22 eine bessere Leistung erbracht hat.

Das bedeutet also, dass NodeJs auch die Gesamtleistung der Laufzeit erhöht hat.

Möglicherweise wurde ein Update an der zugrunde liegenden V8-Engine selbst durchgeführt.

Nun, das war eine erfreuliche Erfahrung für mich. Und ich hoffe, dass es so sein wird

Du auch. Und inmitten all dieser Freude haben wir das eine oder andere gelernt!

Bauen Sie weiter, testen Sie weiter!