Stack n'est pas implémenté en langage Go,
Le traitement de la pile lui-même est dans n'importe quelle langue Vous pouvez l'implémenter vous-même à l'aide de tableaux et de listes linéaires.
Je l'ai fait moi-même pour la langue Go J'ai comparé la vitesse de traitement (temps de traitement) avec d'autres langages dans lesquels Stack est implémenté.
La langue utilisée dans l'expérience est
Il existe 5 langues.
La source de chaque langue est également publiée sur github. https://github.com/NobuyukiInoue/StackSpeedTest
C# https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_CS
Go (Pile implémentée avec 64K segments (array)) (Ajouté 2020/07/17) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_Segment
Go (implémentation de Stack dans un tableau) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_Array
Go (implémentation de Stack avec liste linéaire) 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
Langage C (Stack est implémenté avec 64K segments (tableaux)) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_C_Stack_by_Segment
Langage C (implémentation de Stack avec liste linéaire) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_C_Stack_by_ListNode
Même s'il s'appelle Stack, diverses opérations sont fournies par des méthodes en fonction de la langue, Le contenu de l'implémentation du traitement détaillé est différent, comme par exemple devoir enregistrer la propriété.
Ce qui suit est une liste de classes / interfaces / fonctions dans chaque langage utilisé dans cette expérience.
| Traitement du contenu | C#(.NET Core3.x) (Classe de pile) |
Java 8 (Pile de classes) |
Java 8 (Classe ArrayDeque) |
Java 8 (Classe Deque) |
Python3.8.3 (liste) |
|---|---|---|---|---|---|
| Écrire dans la pile | Méthode push | méthode push | méthode push | addFirst, méthode | fonction d'ajout |
| Éjecter de la pile | Méthode pop | méthode pop | méthode pop | removeFirst, méthode | fonction pop |
| Recherche de valeur | Contient la méthode (La valeur de retour est de type booléen) |
méthode de recherche (La valeur de retour est le numéro d'index) |
Contient la méthode (La valeur de retour est de type booléen) |
Contient la méthode (La valeur de retour est de type booléen) |
fonction d'index |
| Vérifiez si la pile est vide | Utiliser la propriété Count | méthode vide | Méthode isEmpty | Méthode isEmpty | Utiliser la fonction len |
| article | valeur |
|---|---|
| OS | MS-Windows 10 |
| CPU | Intel Core-i7 8559u |
| Mémoire | 16GB(LPDDR3/2133MHz) |
Capacité de mémoire ajoutée. (11/07/2020)
Le contenu du processus est
est.
(La raison de 100 millions est que le temps de traitement entre chaque langue a commencé à s'ouvrir d'ici. À moins que vous n'implémentiez l'énorme traitement d'analyse JSON dans la pile, il ne consommera pas beaucoup.)
Si vous allouez 100 millions de numéros avec int64 (8 octets), vous aurez besoin d'une capacité de 762 Mo. Si c'est int32 (4 octets), il fait la moitié de 381 Mo.
Tant que la capacité de la pile générée est petite, il n'y a pas beaucoup de différence dans le temps de traitement, Lorsqu'il s'agit de générer 100 millions de piles, la consommation de mémoire peut dépasser 4 Go, selon la méthode choisie.
Si la mémoire installée est de 8 Go ou moins, selon la langue (par défaut), J'obtiens une erreur indiquant qu'il n'y a pas assez de mémoire de tas.
Le temps de traitement dans chaque langue était le suivant.
La mémoire consommée est également affichée à titre de référence uniquement, bien qu'elle soit affichée visuellement par le moniteur de ressources (valeur de validation) de Windows 10. (Ajouté le 11/07/2020)
C# NET Core 3.0.100
Utiliser la classe Stack https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.stack-1?view=netcore-3.1
La consommation de mémoire était de 0,39 Go.
| times | Execution time |
|---|---|
| 1st | 977 [ms] |
| 2nd | 1003 [ms] |
| 3rd | 1004 [ms] |
Du point de vue de la consommation de mémoire, il semble que int32 soit utilisé en interne.
Il consomme beaucoup moins de mémoire que les autres langues et Il semble que la petite quantité de données de traitement affecte le temps de traitement court.
Le temps nécessaire pour terminer le programme était trop court pour l'intervalle d'échantillonnage du moniteur de ressources et la consommation de mémoire n'a pas pu être confirmée visuellement. (0,02 Go à la fin) Probablement le même niveau que le langage C.
| times | Execution time |
|---|---|
| 1st | 874 [ms] |
| 2nd | 881 [ms] |
| 3rd | 904 [ms] |
Lorsque je l'ai implémenté avec 64k unités (tableau) similaires au langage C, le temps de traitement était presque proche de celui du langage C.
Il était plus rapide que le programme en langage C à partir du 15/07/2020, qui était compilé avec la version gcc 32 bits, donc Après cela, la version en langage C est compilée avec la version MinGW-W64 et remesurée. (17/07/2020)
La consommation de mémoire était de 2,36 Go.
| times | Execution time |
|---|---|
| 1st | 2089 [ms] |
| 2nd | 1853 [ms] |
| 3rd | 1737 [ms] |
La réaffectation répétée de la baie ne semble pas trop lente. Le résultat est plus rapide que Java.
La consommation de mémoire était de 1,49 Go.
| times | Execution time |
|---|---|
| 1st | 5617 [ms] |
| 2nd | 5400 [ms] |
| 3rd | 5569 [ms] |
Le temps de traitement est plus lent que la version de la baie.
La liste linéaire a besoin d'un pointeur vers le nœud suivant, donc Il y aura plus de données inutiles qu'un tableau avec une disposition de mémoire linéaire, Le résultat est qu'il consomme moins que la version de la baie.
En langage Go, même si vous réaffectez le tableau La mémoire n'a peut-être pas été libérée avant la fin du programme. (Juste devine, je veux que quelqu'un vérifie)
Utiliser la pile de classes https://docs.oracle.com/javase/jp/8/docs/api/java/util/Stack.html
La consommation de mémoire était de 4,21 Go.
| times | Execution time |
|---|---|
| 1st | 6743 [ms] |
| 2nd | 6690 [ms] |
| 3rd | 6733 [ms] |
Utiliser la classe ArrayDeque https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html
La consommation de mémoire était de 3,96 Go.
| times | Execution time |
|---|---|
| 1st | 4397 [ms] |
| 2nd | 4612 [ms] |
| 3rd | 4477 [ms] |
Le temps de traitement est plus court que la classe Stack.
Utiliser l'interface Deque https://docs.oracle.com/javase/jp/8/docs/api/java/util/Deque.html
La consommation de mémoire était de 4,31 Go.
| times | Execution time |
|---|---|
| 1st | 21416 [ms] |
| 2nd | 20187 [ms] |
| 2nd | 20341 [ms] |
Le temps de traitement a augmenté par rapport à la classe Stack.
Python 3.8.3
Utiliser la liste
La consommation de mémoire était de 4,42 Go.
| times | Execution time |
|---|---|
| 1st | 16957 [ms] |
| 2nd | 16561 [ms] |
| 3rd | 17558 [ms] |
Dans d'autres langues, la mémoire une fois allouée était encore consommée, Dans Python3, la consommation maximale de mémoire est immédiatement après 100 millions de poussées. Vous pouvez voir comment la consommation de mémoire diminue à mesure que le processus Pop progresse.
La consommation de mémoire était de 0,38 Go.
Comme prévu, le langage C est rapide. J'ai essayé de spécifier -O3 comme option d'optimisation au moment de la compilation.
| times | Execution time |
|---|---|
| 1st | 843 [ms] |
| 2nd | 828 [ms] |
| 3rd | 828 [ms] |
À propos, si vous ne libérez pas la mémoire au moment du pop, le temps de traitement sera le suivant.
| times | Execution time |
|---|---|
| 1st | 734 [ms] |
| 2nd | 734 [ms] |
| 3rd | 734 [ms] |
La consommation de mémoire était de 1,55 Go.
J'ai essayé de spécifier -O3 comme option d'optimisation au moment de la compilation. Etant donné que le nombre de traitements pour allouer et libérer de la mémoire est important, le temps de traitement est ralenti en conséquence.
| times | Execution time |
|---|---|
| 1st | 7816 [ms] |
| 2nd | 7828 [ms] |
| 3rd | 7953 [ms] |
Il y a également un problème avec l'implémentation de Stack vous-même dans le problème LeetCode. Étant donné que des exemples de réponses dans différentes langues ont été publiés, il serait intéressant de comparer les délais de traitement.
Recommended Posts