Ich versuche Go zu verwenden, um einen binären Baum mit Werten auf dem Blatt zu implementieren, d. h. entspricht:
%Vor% Ich hatte zwei Probleme: 1, ich konnte keinen Weg finden, einen Typ mit mehreren Konstruktoren zu erstellen, also musste ich alle Daten in einen hineinpassen. 2, konnte ich es nicht polymorph machen, also musste ich interface{} verwenden (was ich denke, ist ein "Opt-out" des Typsystems?). Das ist das Beste, was ich machen könnte:
Er implementiert den Typ und testet ihn, indem er über einen riesigen generierten Baum summiert. Ich habe eine gleichwertige Implementierung in JavaScript vorgenommen (einschließlich der redundanten Daten über Konstruktoren, für Fairness):
%Vor% Ich habe den Go-Code mit go build test.go kompiliert und ihn mit time ./test ausgeführt. Ich habe den Node.js-Code mit node test.js ausgeführt. Nach mehreren Tests lief das Go-Programm ungefähr in 2.5 Sekunden im Vergleich zu 1.0 Sekunden von Node.js.
Das macht Go 2.5x langsamer als Node.js für dieses einfache Programm, was nicht korrekt sein kann, da Go eine statisch typisierte, kompilierte Sprache mit einem ausgereiften Compiler ist, während JavaScript untypisiert ist , interpretiert einen.
Warum ist mein Go-Programm so langsam? Fehle ich ein Compiler-Flag, oder ist der Code problematisch?
Dieser Code ist aufgrund der Typassertion und der redundanten Daten langsamer.
Go ermutigt Sie nicht, Typ-Assertions an heißen Stellen zu schreiben:
%Vor% Nehmen Sie diese Typbestätigung heraus (und ändern Sie dementsprechend Value in einen int -Typ), und Ihr Code wird ungefähr doppelt so schnell ausgeführt (was ungefähr der Geschwindigkeit Ihres Knotenbeispiels entsprechen sollte).
Nehmen Sie auch die redundanten Daten heraus, und Ihr Code wird ungefähr dreimal so schnell ausgeführt. Siehe das Beispiel für den Spielplatz am Ende des Posts.
Ich denke, das ist ein Fehler des Designs und nicht der Implementierung. Wenn ich Ihre Frage lese, gibt es einige Verwirrung darüber, wie Go's Typsystem funktioniert.
Das Objektmodell von Go ermutigt Sie nicht, Polymorphismus mit Catch-All-Typen zu machen (siehe die obere Hälfte von diese exzellente Antwort für eine Diskussion von Gos Polymorphismus).
In einer JavaScript-Welt ist jedes Objekt ein bestimmter Typ. In Go kann ein struct als spezifischer Schnittstellentyp behandelt werden, wenn er den Vertrag von interface erfüllt. Beachten Sie, dass structs keine Objekte sind - was Sie Konstruktoren genannt haben, sind nur struct Initialisierer.
Es ist möglich, Go-Code zu schreiben, der auf interface{} als Platzhalter für alle Typen funktioniert, aber die Sprache ermutigt Sie nicht wirklich, Code auf diese Art zu schreiben (wie Sie in Ihrer Frage gezeigt haben, war es eine Herausforderung schreibe sauberen Code so, wie man ihn in JavaScript schreiben würde.)
Da Go keine Objekte hat, wird es schwierig sein, Code zu schreiben, der sich in Go sehr objektorientiert anfühlt (außerdem hat Go keine Standardvererbung oder Methodenüberladung). Aus diesem Grund glaube ich nicht, dass Ihr Code die Art von Code ist, den Go dem Programmierer zum Schreiben empfiehlt. Also, es ist kein fairer Test.
Type assertion is langsam . (Ich gehe nicht über das Design von Go's Interna hinaus, aber das zeigt sicherlich, dass der Programmierer nicht viele Typ-Assertions schreiben soll). Aus diesem Grund ist es nicht verwunderlich, dass Ihr Code nicht performant ist. Ich habe deinen Code folgendermaßen geändert:
%Vor%Und erreichte eine doppelte Geschwindigkeit auf meiner Maschine.
Es gibt wahrscheinlich andere Optimierungen - Sie könnten IsLeaf entfernen und Sie müssen keine Werte auf Nicht-Blatt-Knoten speichern (oder alternativ könnten Sie Werte im gesamten Baum verteilen, also verschwenden Sie niemals die% Code%). Ich weiß nicht, ob JavaScript diese unnötigen Value s optimiert, aber ich glaube nicht, dass Go das tut.
Also, ich denke, dass Ihr Code viel mehr Speicher benötigt, als er benötigt, was auch nicht zur Performance beiträgt.
Ich persönlich bin nicht davon überzeugt, dass "ich dieses Programm in X und Y geschrieben habe und festgestellt habe, dass Y langsamer war", vor allem, weil es schwierig ist, Frameworks zu vergleichen. Es gibt so viele andere Quellen der Varianz - Programmierkenntnisse, Maschinenlast, Spin-up-Zeit, etc.
Um einen fairen Test durchzuführen, müssen Sie Code schreiben, der in jeder Sprache idiomatisch ist, aber auch denselben Code verwendet. Ich glaube nicht, dass es realistisch ist, beides zu erreichen.
Wenn dieser Code Ihr spezifisches Szenario ist und die Leistung das Hauptziel ist, dann ist dieser Test möglicherweise hilfreich. Aber ansonsten halte ich das für keinen sehr aussagekräftigen Vergleich.
Bei der Skalierung würde ich erwarten, dass andere Überlegungen übertreffen, wie schnell Sie einen Baum erstellen und durchqueren können. Es gibt technische Probleme wie Datendurchsatz und Leistung unter Last, aber auch sanftere Probleme wie Programmierzeit und Wartungsaufwand.
Die akademische Übung ist jedoch interessant. Und das Schreiben von Code ist eine gute Möglichkeit, die Kanten eines Frameworks zu finden.
Bearbeiten: Ich habe versucht, Ihren Code mehr Go-like zu machen, was den zusätzlichen Vorteil einer 3-fachen Beschleunigung gegenüber dem Original hat.:
Der Baum ist ein bisschen schwer für den Spielplatz, aber Sie können den Code kopieren und einfügen, um lokal zu laufen.
Es gibt mehr Optimierungen, die ich nicht versucht habe, wie zum Beispiel die parallele Konstruktion des Baumes.
Sie können diesen Entwurf möglicherweise auf das gewünschte polymorphe Verhalten erweitern (indem Sie alternative Value -Implementierungen bereitstellen), aber ich bin nicht sicher, was Leaf für Nicht-Zahl-Typen bedeutet. Nicht zu wissen, wie man Sum() definiert, ist ein gutes Beispiel für die Art des Denkens, die dazu führt, dass man sich nicht entscheidet, Polymorphie durch Generika einzuschließen.
Ich dachte, das könnte nützlich sein. Dies ist meine Implementierung eines symmetrischen Binärbaums, der Rekursions-, Go-Routinen und Kanäle verwendet. Es sollte als Paket verwendet werden, weshalb ich exportierte und nicht exportierte Funktionen verwende. Die exportierten Funktionen sind das, was du verwenden solltest / mod etc .. Ich habe es vor langer Zeit geschrieben ... es gibt viele Dinge, die besser hätten geschrieben werden können ... Ich habe gerade jetzt eine Sum-Funktion für dich hinzugefügt. Ich fügte 23 Knoten hinzu und bekam die Summe in 1/4 Sekunde.
AKTUALISIEREN Ich habe eine neue Funktion mit dem Namen GetTreeTotal () hinzugefügt, wenn Sie sich die Baumstruktur ansehen. In der Funktion Add () aktualisiere ich dieses Feld, während der Knoten hinzugefügt wird. Nun muss sum () nicht in der Masse berechnet werden, das ist nur ein Teil der Metadaten des Baumes. Also in diesem Sinne. Super schnell. Mit ähnlicher Logik kann die Anzahl der Knoten im Baum auch als Metadaten beibehalten werden. Wenn man diese Informationen kennt, würde das Funktionen wie TreeToArray () beschleunigen, weil man dann die Größe des Slices vorher definieren könnte. Weniger Zuordnungen .. usw.
UPDATE2 Diese Frage hat mich neugierig gemacht, ich habe den folgenden Code umgeschrieben und ihn in ein Paket verwandelt. Ссылка Iterative Inserts sind fast 3x schneller (Benchmarks enthalten), obwohl Sie diesen Unterschied wirklich sehen, wenn die Anzahl der Inserts wirklich hoch ist.
%Vor%Das Problem liegt hauptsächlich in der fragmentierten Speicherzuweisung (über den rekursiven Stack). Dies verursacht eine Menge kleiner Zuordnungen, und anschließend hat der Garbage Collector einen hohen Job. Sie können dies umgehen, indem Sie ein Array vormerken, das alle Knoten enthält und einen laufenden Index für die Zuweisung enthält:
bar.go
bar_test.go
Dies wird die Geschwindigkeit um bis zu 0,5 Sek. pro Iteration beschleunigen.
Beachten Sie das Build-in-Profiling von diesem:
go test -cpuprofile cpu.out
und
go tool pprof cpu.out + web
Tags und Links javascript performance go