Stack is not implemented in Go language,
The Stack process itself is in any language You can implement it yourself using arrays and linear lists.
In addition to making my own for Go language I compared the processing speed (processing time) with other languages in which Stack is implemented.
The language used in the experiment was
There are 5 languages.
The source of each language is also published on github. https://github.com/NobuyukiInoue/StackSpeedTest
C# https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_CS
Go (Implemented Stack with 64K segments (array)) (Added 2020/07/17) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_Segment
Go (Implement Stack with array) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_Go_Stack_by_Array
Go (Implementing Stack with linear list) 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 language (Implementing Stack with 64K segments (arrays)) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_C_Stack_by_Segment
C language (implementing Stack with linear list) https://github.com/NobuyukiInoue/StackSpeedTest/tree/master/Project_C_Stack_by_ListNode
Even though it is called Stack, various operations are provided by methods depending on the language, The implementation contents of detailed processing are different, such as having to check in the property.
The following is a list of classes / interfaces / functions in each language used in this experiment.
| Processing content | C#(.NET Core3.x) (Stack class) |
Java 8 (Class Stack) |
Java 8 (Class ArrayDeque) |
Java 8 (Class Deque) |
Python3.8.3 (list) |
|---|---|---|---|---|---|
| Write to Stack | Push method | push method | push method | addFirst method | append function |
| Eject from Stack | Pop method | pop method | pop method | removeFirst method | pop function |
| Search for value | Contains method (Return value is bool type) |
search method (The return value is the index number) |
Contains method (Return value is bool type) |
Contains method (Return value is bool type) |
index function |
| Check if Stack is empty | Use Count property | empty method | isEmpty method | isEmpty method | Use len function |
| item | value |
|---|---|
| OS | MS-Windows 10 |
| CPU | Intel Core-i7 8559u |
| memory | 16GB(LPDDR3/2133MHz) |
Added memory capacity. (2020/07/11)
The content of the process is
is.
(The reason for 100 million is that the processing time between each language started to open from around here. Unless you implement the huge JSON parse processing on the stack, it will not consume that much.)
If you allocate 100 million numbers with int64 (8byte), you will need a capacity of 762MByte. If it is int32 (4byte), it is half 381MByte.
As long as the capacity of the generated stack is small, there is not much difference in processing time, When it comes to generating 100 million stacks, memory consumption can exceed 4GB, depending on the method you choose.
If the installed memory is 8GB or less, depending on the language (by default setting), I get an error saying that the heap memory is insufficient.
The processing time in each language was as follows.
The memory consumed is also shown for reference only, although it is visually displayed by the resource monitor (commit value) of Windows 10. (Added on 2020/07/11)
C# NET Core 3.0.100
Use Stack class https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.stack-1?view=netcore-3.1
Memory consumption was 0.39GB.
| times | Execution time |
|---|---|
| 1st | 977 [ms] |
| 2nd | 1003 [ms] |
| 3rd | 1004 [ms] |
From the viewpoint of memory consumption, it seems that int32 is used internally.
It consumes much less memory than other languages and It seems that the small amount of processing data affects the short processing time.
The time to end the program was too short for the resource monitor sampling interval, and memory consumption could not be visually confirmed. (0.02GB at the end) Probably the same level as C language.
| times | Execution time |
|---|---|
| 1st | 874 [ms] |
| 2nd | 881 [ms] |
| 3rd | 904 [ms] |
When I implemented it with 64k segments (arrays) similar to C language, the processing time was almost close to that of C language.
It was faster than the C language program as of 2020/07/15, which was compiled with gcc 32bit version, so After that, the C language version is compiled with the MinGW-W64 version and remeasured. (2020/07/17)
Memory consumption was 2.36GB.
| times | Execution time |
|---|---|
| 1st | 2089 [ms] |
| 2nd | 1853 [ms] |
| 3rd | 1737 [ms] |
Repeated array reassignments don't seem to be too slow. The result is faster than Java.
Memory consumption was 1.49GB.
| times | Execution time |
|---|---|
| 1st | 5617 [ms] |
| 2nd | 5400 [ms] |
| 3rd | 5569 [ms] |
The processing time is slower than the array version.
The linear list needs a pointer to the next node, so Unnecessary data will increase compared to an array with a linear memory arrangement, The result is that it consumes less than the array version.
In Go language, even if you reassign the array The memory may not have been released until the end of the program. (Just guess, I want someone to verify)
Use class Stack https://docs.oracle.com/javase/jp/8/docs/api/java/util/Stack.html
Memory consumption was 4.21GB.
| times | Execution time |
|---|---|
| 1st | 6743 [ms] |
| 2nd | 6690 [ms] |
| 3rd | 6733 [ms] |
Use class ArrayDeque https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html
Memory consumption was 3.96GB.
| times | Execution time |
|---|---|
| 1st | 4397 [ms] |
| 2nd | 4612 [ms] |
| 3rd | 4477 [ms] |
Processing time is shorter than class Stack.
Use interface Deque https://docs.oracle.com/javase/jp/8/docs/api/java/util/Deque.html
Memory consumption was 4.31GB.
| times | Execution time |
|---|---|
| 1st | 21416 [ms] |
| 2nd | 20187 [ms] |
| 2nd | 20341 [ms] |
The processing time has increased compared to the class Stack.
Python 3.8.3
Use list
Memory consumption was 4.42GB.
| times | Execution time |
|---|---|
| 1st | 16957 [ms] |
| 2nd | 16561 [ms] |
| 3rd | 17558 [ms] |
In other languages, the memory once allocated was still consumed, In Python3, the maximum memory consumption is immediately after 100 million pushes. You can see how the memory consumption decreases as the Pop process progresses.
Memory consumption was 0.38GB.
As expected, C language is fast. I tried to specify -O3 as a compile-time optimization option.
| times | Execution time |
|---|---|
| 1st | 843 [ms] |
| 2nd | 828 [ms] |
| 3rd | 828 [ms] |
By the way, if the memory is not released at the time of pop, the processing time will be as follows.
| times | Execution time |
|---|---|
| 1st | 734 [ms] |
| 2nd | 734 [ms] |
| 3rd | 734 [ms] |
Memory consumption was 1.55GB.
I tried to specify -O3 as a compile-time optimization option. Since the number of memory allocation / release processes is large, the processing time is slowed down accordingly.
| times | Execution time |
|---|---|
| 1st | 7816 [ms] |
| 2nd | 7828 [ms] |
| 3rd | 7953 [ms] |
There is also a problem with implementing Stack yourself in the LeetCode Problem. Since sample answers in various languages have been posted, it would be interesting to compare the processing times.
Recommended Posts