Stack ist nicht in der Sprache Go implementiert.
Die Stapelverarbeitung selbst erfolgt in einer beliebigen Sprache Sie können es selbst mithilfe von Arrays und linearen Listen implementieren.
Ich habe es selbst für die Go-Sprache gemacht Ich habe die Verarbeitungsgeschwindigkeit (Verarbeitungszeit) mit anderen Sprachen verglichen, in denen Stack implementiert ist.
Die im Experiment verwendete Sprache ist
Es gibt 5 Sprachen.
Die Quelle jeder Sprache wird auch auf Github veröffentlicht. https://github.com/NobuyukiInoue/StackSpeedTest
C# https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_CS
Go (Stapel implementiert mit 64K-Segmenten (Array)) (Hinzugefügt am 17.07.2020) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_Segment
Go (Stack in einem Array implementieren) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_Array
Go (Stack mit linearer Liste implementieren) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_ListNode
Java https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Java_Stack https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Java_ArrayDeque https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Java_Deque
Python https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Python3
C-Sprache (Stack ist mit 64K-Segmenten (Arrays) implementiert) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_C_Stack_by_Segment
C-Sprache (Implementierung von Stack mit linearer Liste) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_C_Stack_by_ListNode
Obwohl es als Stapel bezeichnet wird, werden je nach Sprache verschiedene Operationen durch Methoden bereitgestellt. Die Implementierungsinhalte der detaillierten Verarbeitung sind unterschiedlich, z. B. das Einchecken der Eigenschaft.
Das Folgende ist eine Liste von Klassen / Schnittstellen / Funktionen in jeder Sprache, die in diesem Experiment verwendet wird.
| Inhalte verarbeiten | C#(.NET Core3.x) (Stapelklasse) |
Java 8 (Klassenstapel) |
Java 8 (Klasse ArrayDeque) |
Java 8 (Klasse Deque) |
Python3.8.3 (aufführen) |
|---|---|---|---|---|---|
| Schreiben Sie an Stack | Push-Methode | Push-Methode | Push-Methode | addFirst-Methode | Funktion anhängen |
| Aus dem Stapel auswerfen | Pop-Methode | Pop-Methode | Pop-Methode | removeFirst-Methode | Pop-Funktion |
| Suche nach Wert | Enthält Methode (Der Rückgabewert ist vom Typ Bool) |
Suchmethode (Der Rückgabewert ist die Indexnummer) |
Enthält Methode (Der Rückgabewert ist vom Typ Bool) |
Enthält Methode (Der Rückgabewert ist vom Typ Bool) |
Indexfunktion |
| Überprüfen Sie, ob der Stapel leer ist | Verwenden Sie die Count-Eigenschaft | leere Methode | isEmpty-Methode | isEmpty-Methode | Verwenden Sie die Len-Funktion |
| Artikel | Wert |
|---|---|
| OS | MS-Windows 10 |
| CPU | Intel Core-i7 8559u |
| Erinnerung | 16GB(LPDDR3/2133MHz) |
Speicherkapazität hinzugefügt. (2020/07/11)
Der Inhalt des Prozesses ist
ist.
(Der Grund für 100 Millionen ist, dass die Verarbeitungszeit zwischen den einzelnen Sprachen von hier aus zu öffnen begann. Wenn Sie die große JSON-Analyseverarbeitung nicht im Stapel implementieren, wird sie nicht so viel verbrauchen.)
Wenn Sie mit int64 (8 Byte) 100 Millionen Nummern zuweisen, benötigen Sie eine Kapazität von 762 MByte. Wenn es int32 (4 Byte) ist, ist es die Hälfte 381 MByte.
Solange die Kapazität des generierten Stapels klein ist, gibt es keinen großen Unterschied in der Verarbeitungszeit. Wenn 100 Millionen Stapel generiert werden sollen, kann der Speicherverbrauch je nach gewählter Methode 4 GB überschreiten.
Wenn der installierte Speicher je nach Sprache 8 GB oder weniger beträgt (Standardeinstellung), Ich erhalte die Fehlermeldung, dass nicht genügend Heapspeicher vorhanden ist.
Die Verarbeitungszeit in jeder Sprache war wie folgt.
Der verbrauchte Speicher wird auch nur als Referenz angezeigt, obwohl er vom Ressourcenmonitor (Festschreibungswert) von Windows 10 visuell angezeigt wird. (Hinzugefügt am 2020/07/11)
C# NET Core 3.0.100
Verwenden Sie die Stapelklasse https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.stack-1?view=netcore-3.1
Der Speicherverbrauch betrug 0,39 GB.
| times | Execution time |
|---|---|
| 1st | 977 [ms] |
| 2nd | 1003 [ms] |
| 3rd | 1004 [ms] |
Unter dem Gesichtspunkt des Speicherverbrauchs scheint int32 intern verwendet zu werden.
Es verbraucht viel weniger Speicher als andere Sprachen und Es scheint, dass die geringe Menge an Verarbeitungsdaten die kurze Verarbeitungszeit beeinflusst.
Die Zeit zum Beenden des Programms war zu kurz für das Abtastintervall des Ressourcenmonitors, und der Speicherverbrauch konnte nicht visuell bestätigt werden. (0,02 GB am Ende) Wahrscheinlich das gleiche Niveau wie die C-Sprache.
| times | Execution time |
|---|---|
| 1st | 874 [ms] |
| 2nd | 881 [ms] |
| 3rd | 904 [ms] |
Als ich es mit 64.000 Einheiten von Segmenten (Arrays) ähnlich der C-Sprache implementierte, war die Verarbeitungszeit fast nahe an der der C-Sprache.
Es war ab 2020/07/15 schneller als das C-Sprachprogramm, das mit der gcc 32bit-Version kompiliert wurde Danach wird die C-Sprachversion mit der MinGW-W64-Version kompiliert und erneut gemessen. (2020/07/17)
Der Speicherverbrauch betrug 2,36 GB.
| times | Execution time |
|---|---|
| 1st | 2089 [ms] |
| 2nd | 1853 [ms] |
| 3rd | 1737 [ms] |
Die wiederholte Neuzuweisung des Arrays scheint nicht zu langsam zu sein. Das Ergebnis ist schneller als Java.
Der Speicherverbrauch betrug 1,49 GB.
| times | Execution time |
|---|---|
| 1st | 5617 [ms] |
| 2nd | 5400 [ms] |
| 3rd | 5569 [ms] |
Die Verarbeitungszeit ist langsamer als die Array-Version.
Die lineare Liste benötigt also einen Zeiger auf den nächsten Knoten Es gibt mehr unnötige Daten als ein Array mit einem linearen Speicherlayout. Das Ergebnis ist, dass es weniger als die Array-Version verbraucht.
In der Sprache Go, auch wenn Sie das Array neu zuweisen Der Speicher wurde möglicherweise erst am Ende des Programms freigegeben. (Vermutlich möchte ich, dass jemand dies überprüft.)
Verwenden Sie den Klassenstapel https://docs.oracle.com/javase/jp/8/docs/api/java/util/Stack.html
Der Speicherverbrauch betrug 4,21 GB.
| times | Execution time |
|---|---|
| 1st | 6743 [ms] |
| 2nd | 6690 [ms] |
| 3rd | 6733 [ms] |
Verwenden Sie die Klasse ArrayDeque https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html
Der Speicherverbrauch betrug 3,96 GB.
| times | Execution time |
|---|---|
| 1st | 4397 [ms] |
| 2nd | 4612 [ms] |
| 3rd | 4477 [ms] |
Die Verarbeitungszeit ist kürzer als bei Class Stack.
Verwenden Sie die Schnittstelle Deque https://docs.oracle.com/javase/jp/8/docs/api/java/util/Deque.html
Der Speicherverbrauch betrug 4,31 GB.
| times | Execution time |
|---|---|
| 1st | 21416 [ms] |
| 2nd | 20187 [ms] |
| 2nd | 20341 [ms] |
Die Verarbeitungszeit hat sich gegenüber der Klasse Stack erhöht.
Python 3.8.3
Liste verwenden
Der Speicherverbrauch betrug 4,42 GB.
| times | Execution time |
|---|---|
| 1st | 16957 [ms] |
| 2nd | 16561 [ms] |
| 3rd | 17558 [ms] |
In anderen Sprachen wurde der einmal zugewiesene Speicher noch belegt. In Python3 liegt der maximale Speicherverbrauch unmittelbar nach 100 Millionen Pushs. Sie können sehen, wie der Speicherverbrauch im Verlauf des Pop-Prozesses abnimmt.
Der Speicherverbrauch betrug 0,38 GB.
Wie erwartet ist die C-Sprache schnell. Ich habe versucht, -O3 als Optimierungsoption zur Kompilierungszeit anzugeben.
| times | Execution time |
|---|---|
| 1st | 843 [ms] |
| 2nd | 828 [ms] |
| 3rd | 828 [ms] |
Übrigens, wenn Sie den Speicher zum Zeitpunkt des Popups nicht freigeben, ist die Verarbeitungszeit wie folgt.
| times | Execution time |
|---|---|
| 1st | 734 [ms] |
| 2nd | 734 [ms] |
| 3rd | 734 [ms] |
Der Speicherverbrauch betrug 1,55 GB.
Ich habe versucht, -O3 als Optimierungsoption zur Kompilierungszeit anzugeben. Da die Anzahl der Verarbeitungen zum Zuweisen und Freigeben von Speicher groß ist, wird die Verarbeitungszeit entsprechend verlangsamt.
| times | Execution time |
|---|---|
| 1st | 7816 [ms] |
| 2nd | 7828 [ms] |
| 3rd | 7953 [ms] |
Es gibt auch ein Problem bei der Implementierung von Stack selbst im LeetCode-Problem. Da Beispielantworten in verschiedenen Sprachen veröffentlicht wurden, wäre es interessant, die Bearbeitungszeiten zu vergleichen.
Recommended Posts