CPP09 1.0
読み取り中…
検索中…
一致する文字列を見つけられません
PmergeMe.cpp
[詳解]
1/* ************************************************************************** */
2/* */
3/* ::: :::::::: */
4/* PmergeMe.cpp :+: :+: :+: */
5/* +:+ +:+ +:+ */
6/* By: kamitsui <kamitsui@student.42tokyo.jp> +#+ +:+ +#+ */
7/* +#+#+#+#+#+ +#+ */
8/* Created: 2025/08/28 18:01:57 by kamitsui #+# #+# */
9/* Updated: 2025/08/28 18:03:00 by kamitsui ### ########.fr */
10/* */
11/* ************************************************************************** */
12
18#include "PmergeMe.hpp"
19#include <algorithm> // for std::lower_bound, std::min
20#include <climits>
21#include <cstdlib>
22#include <utility>
23
24// --- Helper function to find the corresponding pend element ---
25// This function replaces the std::map lookup.
26template <typename Container> int findPend(int mainElement, const Container &pairs) {
27 for (size_t i = 0; i < pairs.size(); ++i) {
28 if (pairs[i].first == mainElement) {
29 return pairs[i].second;
30 }
31 }
32 return -1; // Should not be reached in correct logic
33}
34
35// --- Orthodox Canonical Form ---
36
37PmergeMe::PmergeMe() {}
38
39PmergeMe::~PmergeMe() {}
40
41PmergeMe::PmergeMe(const PmergeMe &src) { (void)src; }
42
43PmergeMe &PmergeMe::operator=(const PmergeMe &rhs) {
44 (void)rhs;
45 return *this;
46}
47
48// --- Timing Helper ---
49
50long PmergeMe::getTimeStamp() {
51 struct timeval tv;
52 gettimeofday(&tv, NULL);
53 return tv.tv_sec * 1000000 + tv.tv_usec;
54}
55
56// --- Vector Implementation ---
57
58void PmergeMe::mergeInsertSort(std::vector<int> &vec) {
59 if (vec.size() <= 1)
60 return;
61
62 // 1. ペアを作成
63 std::vector<std::pair<int, int> > pairs;
64 int straggler = -1;
65 bool hasStraggler = vec.size() % 2 != 0;
66 if (hasStraggler) {
67 straggler = vec.back();
68 vec.pop_back();
69 }
70
71 for (size_t i = 0; i < vec.size(); i += 2) {
72 if (vec[i] < vec[i + 1]) {
73 pairs.push_back(std::make_pair(vec[i + 1], vec[i]));
74 } else {
75 pairs.push_back(std::make_pair(vec[i], vec[i + 1]));
76 }
77 }
78
79 // 2. メインチェーンを構築し、再帰的にソート
80 std::vector<int> mainChain;
81 for (size_t i = 0; i < pairs.size(); ++i) {
82 mainChain.push_back(pairs[i].first);
83 }
84
85 mergeInsertSort(mainChain);
86
87 // 3. 挿入処理
88 std::vector<int> sortedChain = mainChain;
89
90 // 最初の保留要素を挿入
91 int firstPend = findPend(mainChain[0], pairs);
92 sortedChain.insert(sortedChain.begin(), firstPend);
93
94 // ヤコブスタール数に基づき、残りの保留要素を挿入
95 const int jacobsthal[] = {3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461};
96 size_t lastInsertedEnd = 1;
97 for (int i = 0; i < 12; ++i) {
98 size_t currentJacobsthal = jacobsthal[i];
99 size_t limit = std::min(currentJacobsthal, mainChain.size());
100
101 for (size_t j = limit; j > lastInsertedEnd; --j) {
102 int mainElement = mainChain[j - 1];
103 int valueToInsert = findPend(mainElement, pairs);
104
105 std::vector<int>::iterator it = std::lower_bound(sortedChain.begin(), sortedChain.end(), valueToInsert);
106 sortedChain.insert(it, valueToInsert);
107 }
108 lastInsertedEnd = currentJacobsthal;
109 if (lastInsertedEnd >= mainChain.size())
110 break;
111 }
112
113 // 4. はぐれ要素を挿入
114 if (hasStraggler) {
115 std::vector<int>::iterator it = std::lower_bound(sortedChain.begin(), sortedChain.end(), straggler);
116 sortedChain.insert(it, straggler);
117 }
118
119 vec = sortedChain;
120}
121
122// --- Deque Implementation ---
123
124void PmergeMe::mergeInsertSort(std::deque<int> &deq) {
125 if (deq.size() <= 1)
126 return;
127
128 // 1. ペアを作成
129 std::deque<std::pair<int, int> > pairs;
130 int straggler = -1;
131 bool hasStraggler = deq.size() % 2 != 0;
132 if (hasStraggler) {
133 straggler = deq.back();
134 deq.pop_back();
135 }
136
137 for (size_t i = 0; i < deq.size(); i += 2) {
138 if (deq[i] < deq[i + 1]) {
139 pairs.push_back(std::make_pair(deq[i + 1], deq[i]));
140 } else {
141 pairs.push_back(std::make_pair(deq[i], deq[i + 1]));
142 }
143 }
144
145 // 2. メインチェーンを構築し、再帰的にソート
146 std::deque<int> mainChain;
147 for (size_t i = 0; i < pairs.size(); ++i) {
148 mainChain.push_back(pairs[i].first);
149 }
150
151 mergeInsertSort(mainChain);
152
153 // 3. 挿入処理
154 std::deque<int> sortedChain = mainChain;
155
156 // 最初の保留要素を挿入
157 int firstPend = findPend(mainChain[0], pairs);
158 sortedChain.insert(sortedChain.begin(), firstPend);
159
160 // ヤコブスタール数に基づき、残りの保留要素を挿入
161 const int jacobsthal[] = {3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461};
162 size_t lastInsertedEnd = 1;
163 for (int i = 0; i < 12; ++i) {
164 size_t currentJacobsthal = jacobsthal[i];
165 size_t limit = std::min(currentJacobsthal, mainChain.size());
166
167 for (size_t j = limit; j > lastInsertedEnd; --j) {
168 int mainElement = mainChain[j - 1];
169 int valueToInsert = findPend(mainElement, pairs);
170
171 std::deque<int>::iterator it = std::lower_bound(sortedChain.begin(), sortedChain.end(), valueToInsert);
172 sortedChain.insert(it, valueToInsert);
173 }
174 lastInsertedEnd = currentJacobsthal;
175 if (lastInsertedEnd >= mainChain.size())
176 break;
177 }
178
179 // 4. はぐれ要素を挿入
180 if (hasStraggler) {
181 std::deque<int>::iterator it = std::lower_bound(sortedChain.begin(), sortedChain.end(), straggler);
182 sortedChain.insert(it, straggler);
183 }
184
185 deq = sortedChain;
186}
187
188// --- Main Execution Logic ---
189
190void PmergeMe::sortAndCompare(int argc, char **argv) {
191 std::vector<int> vec;
192 std::deque<int> deq;
193
194 // 1. 引数のパースと検証
195 for (int i = 1; i < argc; ++i) {
196 char *end;
197 long val = std::strtol(argv[i], &end, 10);
198 if (*end != '\0' || val <= 0 || val > INT_MAX) {
199 throw std::invalid_argument("Error: Invalid input.");
200 }
201 vec.push_back(static_cast<int>(val));
202 deq.push_back(static_cast<int>(val));
203 }
204
205 // 2. ソート前のシーケンスを表示
206 std::cout << "Before: ";
207 for (size_t i = 0; i < vec.size(); ++i) {
208 std::cout << vec[i] << (i == vec.size() - 1 ? "" : " ");
209 }
210 std::cout << std::endl;
211
212 // 3. vectorのソートと時間計測
213 long startVec = getTimeStamp();
214 mergeInsertSort(vec);
215 long endVec = getTimeStamp();
216 double timeVec = static_cast<double>(endVec - startVec);
217
218 // 4. ソート後のシーケンスを表示
219 std::cout << "After: ";
220 for (size_t i = 0; i < vec.size(); ++i) {
221 std::cout << vec[i] << (i == vec.size() - 1 ? "" : " ");
222 }
223 std::cout << std::endl;
224
225 // 5. dequeのソートと時間計測
226 long startDeq = getTimeStamp();
227 mergeInsertSort(deq);
228 long endDeq = getTimeStamp();
229 double timeDeq = static_cast<double>(endDeq - startDeq);
230
231 // 6. 結果の表示
232 std::cout << "Time to process a range of " << argc - 1 << " elements with std::vector : " << timeVec << " us"
233 << std::endl;
234 std::cout << "Time to process a range of " << argc - 1 << " elements with std::deque : " << timeDeq << " us"
235 << std::endl;
236}
findPend
int findPend(int mainElement, const Container &pairs)
Definition PmergeMe.cpp:26
PmergeMe.hpp
マージ挿入ソートアルゴリズムを実装し、異なるコンテナでのパフォーマンスを比較するPmergeMeクラスを提供します。
std::vector::back
T back(T... args)
std::vector::begin
T begin(T... args)
PmergeMe
マージ挿入ソート（フォード・ジョンソンアルゴリズム）を用いて数値シーケンスをソートするクラス。
Definition PmergeMe.hpp:38
PmergeMe::sortAndCompare
void sortAndCompare(int argc, char **argv)
コマンドライン引数をパースし、ソートを実行して結果を比較・表示します。
Definition PmergeMe.cpp:190
PmergeMe::mergeInsertSort
void mergeInsertSort(std::vector< int > &arr)
std::vectorに対してマージ挿入ソートを実行します。
Definition PmergeMe.cpp:58
PmergeMe::PmergeMe
PmergeMe()
デフォルトコンストラクタ。
Definition PmergeMe.cpp:37
PmergeMe::~PmergeMe
~PmergeMe()
デストラクタ。
Definition PmergeMe.cpp:39
std::vector::end
T end(T... args)
std::endl
T endl(T... args)
std::vector::insert
T insert(T... args)
std::lower_bound
T lower_bound(T... args)
std::make_pair
T make_pair(T... args)
std::min
T min(T... args)
std::vector::pop_back
T pop_back(T... args)
std::vector::push_back
T push_back(T... args)
std::vector::size
T size(T... args)
std::strtol
T strtol(T... args)