Edited at

C++で速度だけを気にしてスタックとキューを作製する

More than 3 years have passed since last update.

クラスにしないほうがそもそも速いような気もする.

全体的に参照乱発,エラーチェックなしという構成のため,バグを出さずに運用するのは難しい?


※1/14追記 メモリリークを避けるためにデストラクタも実装すべき(コメント感謝)


スタック


コード

コンストラクタでサイズを指定.サイズを超える数のデータを入れたらアウト.

indexとmax_size比べてエラーチェック実装できそう.


stack.h

#ifndef STACK_H

#define STACK_H

template <class T>
class myStack{
public: //カプセル化なんてなかった
T *data;
int index;
int max_size;

myStack(){};
myStack(int size);
T &pop();
void push(T &city);
};

template <class T>
myStack<T>::myStack(int size){
data = new T[size];
index = 0;
max_size = size;
}

template <class T>
T &myStack<T>::pop(){
return data[--index];
}

template <class T>
void myStack<T>::push(T &c){
data[index++] = c;
}

#endif



使い方


how_to

int size = 10;

myStack<int> stack(size);
stack.push(5);
cout << stack.pop() << endl;


キュー


コード

こちらも指定サイズを超えるとアウト.

headとtailを比較して,エラーチェック実装できると思う.


queue.h

#ifndef QUEUE_H

#define QUEUE_H

template <class T>
class myQueue{
public: //カプセル化なんてなかった
T *data;
int head, tail;
int max_size;

myQueue(){};
myQueue(int size);
T &dequeue();
void enqueue(T &city);
};

template <class T>
myQueue<T>::myQueue(int size){
data = new T[size];
head = tail = 0;
max_size = size;
}

template <class T>
T &myQueue<T>::dequeue(){
if(head == max_size) head = 0;
return data[head++];
}

template <class T>
void myQueue<T>::enqueue(T &c){
if(tail == max_size) tail = 0;
data[tail++] = c;
}

#endif



使い方


how_to

int size = 10;

myQueue<int> queue(size);
queue.enqueue(4);
cout << queue.dequeue() << endl;


速度比較

せっかくなので比べてみる


コード

ここを参考にどの程度早くなるか試してみました.


chrono

#include <iostream>

#include <stack>
#include <queue>
#include "stack.h"
#include "queue.h"
#include <chrono>
#include <time.h>

#define size 100000000

using namespace std;

int main(int argc, char **argv){
stack<int> stl_stack;
myStack<int> mystack(100);

queue<int> stl_queue;
myQueue<int> myqueue(100);

int hoge;
int *rands = (int *) malloc(sizeof(int) * size);

srand((unsigned int)time(NULL));

for(int i = 0; i < size; i++)
rands[i] = rand();

auto start = chrono::system_clock::now();

for(int i = 0; i < size; i++){
stl_stack.push(rands[i]);
hoge = stl_stack.top();
stl_stack.pop();
}

auto end = chrono::system_clock::now();
auto diff = end - start;
cout << "elapsed time stl_stack = "
<< chrono::duration_cast<chrono::milliseconds>(diff).count()
<< " msec." << endl;

start = chrono::system_clock::now();

for(int i = 0; i < size; i++){
mystack.push(rands[i]);
hoge = mystack.pop();
}

end = chrono::system_clock::now();
diff = end - start;
cout << "elapsed time my stack = "
<< chrono::duration_cast<chrono::milliseconds>(diff).count()
<< " msec." << endl;

start = chrono::system_clock::now();

for(int i = 0; i < size; i++){
stl_queue.push(rands[i]);
hoge = stl_queue.front();
stl_queue.pop();
}

end = chrono::system_clock::now();
diff = end - start;
cout << "elapsed time stl_queue = "
<< chrono::duration_cast<chrono::milliseconds>(diff).count()
<< " msec." << endl;

start = chrono::system_clock::now();

for(int i = 0; i < size; i++){
myqueue.enqueue(rands[i]);
hoge = myqueue.dequeue();
}

end = chrono::system_clock::now();
diff = end - start;
cout << "elapsed time my queue = "
<< chrono::duration_cast<chrono::milliseconds>(diff).count()
<< " msec." << endl;

return 0;
}


結果


result

$ ./a.out # 最適化オプション無し

elapsed time stl_stack = 6942 msec.
elapsed time my stack = 855 msec.
elapsed time stl_queue = 5322 msec.
elapsed time my queue = 1062 msec.

$ ./a.out # -O1で最適化
elapsed time stl_stack = 1023 msec.
elapsed time my stack = 505 msec.
elapsed time stl_queue = 1418 msec.
elapsed time my queue = 665 msec.



※1/14追記

stack<int,vector<int> > stl_stack;

という形でSTLのスタックを宣言してやると,-O1下で二つのスタックはほぼ同じ速度になりました.(コメント感謝)

 

結論:最適化オプションすごい