Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@gx3n-inue(Nobuyuki Inoue)

言語別Stack処理速度比較

Last updated at Posted at 2020-07-10

1. はじめに

Go言語にはStackが実装されていませんが、

Stackの処理自体は、どの言語でも、
配列や線形リストを使って自作で実装することができます。

Go言語向けに自作で作ったついでに、
Stackが実装されている他言語との処理速度（処理時間）を比較してみました。

実験で使用した言語は、

  • C#(.NET Core3.0)
  • go1.14.4
  • java 13.0.2
  • Python 3.8.3
  • C言語(MinGW.org GCC-8.2.0-3)(2020/07/12追記)
  • C言語(gcc.exe (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 8.1.0)(2020/07/17更新)

の５言語です。

各言語のソースは、githubでも公開しています。
https://github.com/NobuyukiInoue/StackSpeedTest

2. 言語別のメソッド比較

Stackといっても、言語によって、各種操作がメソッドで提供されていたり、
プロパティでチェックしなければならないなど、細かな処理の実装内容が異なります。

今回の実験で使用した各言語でのクラス／インタフェース／機能を一覧にすると、以下のようになります。

処理内容 C#(.NET Core3.x)
(Stackクラス)		 Java 8
(クラスStack)		 Java 8
(クラスArrayDeque)		 Java 8
(クラスDeque)		 Python3.8.3
(リスト)
Stackへの書き込み Pushメソッド pushメソッド pushメソッド addFirstメソッド append関数
Stackからの取り出し Popメソッド popメソッド popメソッド removeFirstメソッド pop関数
値の検索 Containsメソッド
(戻り値はbool型)		 searchメソッド
(戻り値はindex番号)		 Containsメソッド
(戻り値はbool型)		 Containsメソッド
(戻り値はbool型)		 index関数
Stackが空かどうか調べる Countプロパティを利用 emptyメソッド isEmptyメソッド isEmptyメソッド len関数を利用

3. 検証環境と実験結果(2020/07/11追記)

項目 値
OS MS-Windows 10
CPU Intel Core-i7 8559u
メモリ 16GB(LPDDR3/2133MHz)

メモリ容量を追記しました。(2020/07/11)

処理の内容は、

  • 1～1億までの数値のpush()
  • 最も深い位置にある値1の検索
  • 1億～1までのPop()

です。

（なぜに1億個かというと、このあたりから各言語間の処理時間が開き始めたからです。超巨大なJSONのparse処理をスタックで実装するとかしない限り、そこまで消費しないでしょうけど。）

1億個の数値をint64(8byte)で割り当てると、762MByteの容量が必要になります。
int32(4byte)なら、半分の381MByteですね。

生成するスタックの容量が小さいうちは、それほど処理時間に差はありませんが、
1億個のスタック生成となると、選択した方法によってはメモリ消費が4GBを超えます。

搭載されているメモリが8GB以下だと、言語によっては（デフォルト設定では）、
ヒープメモリが足りないといったエラーがでます。

各言語での処理時間は以下の通りでした。

消費したメモリについても、Windows10のリソースモニター（コミット値）による表示の目視ではありますが、参考程度に掲載しています。(2020/07/11追記)

C# NET Core 3.0.100

Stackクラスを使用
https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.stack-1?view=netcore-3.1

メモリ消費は0.39GBでした。

times Execution time
1st 977 [ms]
2nd 1003 [ms]
3rd 1004 [ms]

メモリ消費からみて、内部ではint32で処理が行われているようです。

他言語と比べてかなりメモリ消費が少なく、
処理データの少なさが処理時間の短さに影響しているようです。

go1.14.4 windows/amd64(64K個単位のセグメント(配列)でStackを実装)(2020/07/17追加)

リソースモニタのサンプリング間隔よりもプログラム終了までの時間が短すぎて、メモリ消費は目視では確認できませんでした。（終了時は0.02GB)
恐らくC言語と同等程度だと思われます。

times Execution time
1st 874 [ms]
2nd 881 [ms]
3rd 904 [ms]

C言語と同様の64k個単位のセグメント(配列)で実装してみたところ、ほぼC言語に迫る処理時間となりました。

gcc 32bit版でコンパイルしていた2020/07/15時点のC言語のプログラムよりも速かったので、
その後、C言語版はMinGW-W64版でコンパイルして再計測しています。(2020/07/17)

go1.14.4 windows/amd64(配列版)

メモリ消費は2.36GBでした。

times Execution time
1st 2089 [ms]
2nd 1853 [ms]
3rd 1737 [ms]

配列の再割り当てを繰り返しても、それほど遅くはないようです。
Javaより速い結果となりました。

go1.14.4 windows/amd64(線形リスト版)

メモリ消費は1.49GBでした。

times Execution time
1st 5617 [ms]
2nd 5400 [ms]
3rd 5569 [ms]

処理時間は配列版よりも遅くなりました。

線形リストでは次ノードへのポインタが必要なので、
直線的なメモリ配置の配列より不要なデータが増えてしまいますが、
配列版より消費が少ない結果となりました。

Go言語では、配列の再割り当てを行っても、
プログラムの終了までメモリの解放が行われていないのかもしれません。
（あくまで推測で、だれか検証してほしい）

java 13.0.2(クラスStack版)

クラスStackを使用
https://docs.oracle.com/javase/jp/8/docs/api/java/util/Stack.html

メモリ消費は4.21GBでした。

times Execution time
1st 6743 [ms]
2nd 6690 [ms]
3rd 6733 [ms]

java 13.0.2(クラスArrayDeque版)

クラスArrayDequeを使用
https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html

メモリ消費は3.96GBでした。

times Execution time
1st 4397 [ms]
2nd 4612 [ms]
3rd 4477 [ms]

クラスStackよりも処理時間が短くなりました。

java 13.0.2(インタフェースDeque版)

インタフェースDequeを使用
https://docs.oracle.com/javase/jp/8/docs/api/java/util/Deque.html

メモリ消費は4.31GBでした。

times Execution time
1st 21416 [ms]
2nd 20187 [ms]
2nd 20341 [ms]

クラスStackよりも処理時間が増えてしまいました。

Python 3.8.3

リストを使用

メモリ消費は4.42GBでした。

times Execution time
1st 16957 [ms]
2nd 16561 [ms]
3rd 17558 [ms]

他言語では、一度確保したメモリは消費したままでしたが、
Python3では、１億個のPush直後がメモリ消費の最大値で、
Pop処理が進むにしたがって消費メモリが減っていく様子が目視できます。

C言語(64K個単位のセグメント(配列)でStackを実装)(2020/07/17更新)

メモリ消費は0.38GBでした。

さすがにC言語は速いですね。
コンパイル時の最適化オプションとして-O3を指定してみました。

times Execution time
1st 843 [ms]
2nd 828 [ms]
3rd 828 [ms]

ちなみに、pop時にメモリを解放しない場合は以下の処理時間となりました。

times Execution time
1st 734 [ms]
2nd 734 [ms]
3rd 734 [ms]

C言語(線形リストでStackを実装)(2020/07/17更新)

メモリ消費は1.55GBでした。

コンパイル時の最適化オプションとして-O3を指定してみました。
メモリの確保・解放の処理回数が多いので、それだけ処理時間が遅くなっています。

times Execution time
1st 7816 [ms]
2nd 7828 [ms]
3rd 7953 [ms]

関連(2020/07/11追記)

LeetCodeのProblemの中にも、Stackを自分で実装する問題があります。
いろんな言語での回答例が投稿されているので、処理時間を比較するのも面白いと思います。

2
1
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?