はじめに
こんにちは。
42tokyoといったところで、コンピュータサイエンス？を学んでいます。
最近、Merge-insertion sort(Ford–Johnson algorithm)の実装を行う課題を通して、C++98のコンテナについて調べました。
今回は、std::vector, std::deque, std::listの各操作に掛かる時間を計測した結果をまとめます。
間違い等があれば、ご指摘ください。
参考
実行環境
環境
MacBook Pro
プロセッサ 2.3 GHz 8 コア Intel Core i9
c++ -v
Apple clang version 15.0.0 (clang-1500.3.9.4)
Target: x86_64-apple-darwin23.5.0
Thread model: posix
まとめ
各操作の実行結果は画像の通り
各コンテナの概要
std::vector
- 連続したメモリ領域を確保し要素を格納する
- 必要に応じて動的にメモリを確保する
- 末尾に対する操作が高速で行われる
| 操作 | 計算量（$O(x)$） |
|---|---|
| ランダムアクセス | 少ない（常に$O(1)$） |
| 終端に要素の追加、または削除 | 少ない（常に$O(1)$） |
| 終端以外に要素の追加、または削除 | 終端までの距離（$n$）に比例（$O(n)$） |
std::deque
- 固定サイズの配列を確保し要素を格納する
- 必要に応じて動的にメモリを確保するが、各配列は連続したメモリ領域に配置されない
- 先頭と末尾に対する操作が高速で行われる
| 操作 | 計算量（$O(x)$） |
|---|---|
| ランダムアクセス | 少ない（常に$O(1)$） |
| 終端に要素の追加、または削除 | 少ない（常に$O(1)$） |
| 終端以外に要素の追加、または削除 | 全体の要素数（$n$）に比例（$O(n)$） |
std::list
- 双方向リスト
| 操作 | 計算量（$O(x)$） |
|---|---|
| ランダムアクセス | 高速なアクセスとは言えない |
| 要素の追加、または削除 | 常に一定時間を要する |
各テストのコード
事前準備
~ ~ ~
std::srand(std::time(NULL));
std::clock_t start, finish;
double time;
int nums[1000000];
for (int i = 0; i < 1000000; i++) { nums[i] = std::rand() % 1000000; }
std::vector<int> vec;
std::deque<int> deq;
std::list<int> lst;
~ ~ ~
終端に要素を追加するテスト
計測した処理の実装のみ記述
start = std::clock();
for (int i = 0; i < 1000000; i++) { vec.push_back(nums[i]); }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
start = std::clock();
for (int i = 0; i < 1000000; i++) { deq.push_back(nums[i]); }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
start = std::clock();
for (int i = 0; i < 1000000; i++) { lst.push_back(nums[i]); }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
ランダムな位置の要素にアクセスするテスト
このテストでは、終端に要素を追加するテストで作成したコンテナを使用
start = std::clock();
for (int i = 0; i < 1000000; i++) { vec[nums[i]] = nums[i]; }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
start = std::clock();
for (int i = 0; i < 1000000; i++) { deq[nums[i]] = nums[i]; }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
std::list<int>::iterator beginIt = lst.begin();
std::list<int>::iterator endIt = lst.end();
int lstSize = lst.size();
int middleIndex = lstSize / 2;
start = std::clock();
for (int i = 0; i < 1000; i++) {
if (nums[i] < middleIndex) {
std::advance(beginIt, nums[i]);
*beginIt = nums[i];
beginIt = lst.begin();
} else {
std::advance(endIt, nums[i] - lstSize);
*endIt = nums[i];
endIt = lst.end();
}
}
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
ランダムな位置で要素を追加するテスト
このテストでは、終端に要素を追加するテストで作成したコンテナを使用
std::vector<int>::iterator vecBeginIt, vecEndIt;
int vecSize = vec.size();
int vecMiddleIndex = vecSize / 2;
start = std::clock();
for (int i = 0; i < 1000; i++) {
if (nums[i] < vecMiddleIndex) {
vecBeginIt = vec.begin();
std::advance(vecBeginIt, nums[i]);
vec.insert(vecBeginIt, nums[i]);
} else {
vecEndIt = vec.end();
std::advance(vecEndIt, nums[i] - vecSize);
vec.insert(vecEndIt, nums[i]);
}
vecSize = vec.size();
vecMiddleIndex = vecSize / 2;
}
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
std::deque<int>::iterator deqBeginIt, deqEndIt;
int deqSize = deq.size();
int deqMiddleIndex = deqSize / 2;
start = std::clock();
for (int i = 0; i < 1000; i++) {
if (nums[i] < deqMiddleIndex) {
deqBeginIt = deq.begin();
std::advance(deqBeginIt, nums[i]);
deq.insert(deqBeginIt, nums[i]);
} else {
deqEndIt = deq.end();
std::advance(deqEndIt, nums[i] - deqSize);
deq.insert(deqEndIt, nums[i]);
}
deqSize = deq.size();
deqMiddleIndex = deqSize / 2;
}
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
std::list<int>::iterator lstBeginIt, lstEndIt;
int lstSize = lst.size();
int lstMiddleIndex = lstSize / 2;
start = std::clock();
for (int i = 0; i < 1000; i++) {
if (nums[i] < lstMiddleIndex) {
lstBeginIt = lst.begin();
std::advance(lstBeginIt, nums[i]);
lst.insert(lstBeginIt, nums[i]);
} else {
lstEndIt = lst.end();
std::advance(lstEndIt, nums[i] - lstSize);
lst.insert(lstEndIt, nums[i]);
}
lstSize = lst.size();
lstMiddleIndex = lstSize / 2;
}
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
先頭に要素を追加するテスト
std::vector<int> vec;
std::deque<int> deq;
std::list<int> lst;
start = std::clock();
for (int i = 0; i < 100000; i++) { vec.insert(vec.begin(), nums[i]); }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
start = std::clock();
for (int i = 0; i < 100000; i++) { deq.push_front(nums[i]); }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
start = std::clock();
for (int i = 0; i < 100000; i++) { lst.push_front(nums[i]); }
finish = std::clock();
time = static_cast<double>(finish - start) / CLOCKS_PER_SEC * 1000.0;
さいごに
初めて、比較することを意識してコードを書いてみました。
正直なところ「これで正しく比較ができているのか？」といった気持ちです。
不備があればお申し付けください。
ありがとうございました。