2018年02月24日
《その308》 ベクトルのシャッフル
ベクトル要素のシャッフル
下記のプログラムでは、ベクトル内の要素を shuffle関数を使ってシャッフルしています。
そして、シャッフルした後に、昇順にソートしているのですが、ここでは、マージソートを行う関数を作成して、それを使っています。
※マージソートを行う関数は、本ブログの《162》で、作成しました。
ベクトル内の要素をシャッフルするには、random_shuffle関数が便利ですが、
random_shuffle関数は、C++14から非推奨となり、C++17で削除されたということなので、
ここでは、C++11で導入された shuffle関数を使いました。
shuffle関数
template <class RandomAccessIterator, class UniformRandomNumberGenerator>
void shuffle (RandomAccessIterator first, RandomAccessIterator last,
UniformRandomNumberGenerator&& g)
{
for (auto i=(last-first)-1; i>0; --i) {
std::uniform_int_distribution<decltype(i)> d(0,i);
swap (first[i], first[d(g)]);
}
}
上記の shuffle関数の定義について、少し補足します。
◆uniform_int_distribution<decltype(i)> d(0,i);
コンストラクタ uniform_int_distribution により、一様分布の 0以上 i 以下の整数が生成されます。
◆decltype は、i の型を取得します。
decltype を使用すると、型名を指定しなくても、i から型を判断してもらえます。
◆UniformRandomNumberGenerator&& g
g には、乱数生成エンジンを指定します。 & は左辺値参照ですが、&& は右辺値参照です。
乱数生成エンジン random_device
random_device は、乱数を生成するクラスで、<random>ヘッダにより提供されます。
このクラスは、擬似乱数ではなく、予測不能な乱数を作成してくれる乱数生成エンジンです。
ただし、パフォーマンス的には、擬似乱数生成エンジンより劣るため、擬似乱数生成エンジンに与えるタネを生成するのに使われることが多いようです。
下記のプログラムでは、特に問題ないので、この random_device をそのまま使っています。
#include <random>
#include <vector>
#include <iostream>
using namespace std;
// マージソートをする関数
void mergesort(int* base, int nmemb)
{
if (nmemb <= 1) return;
int* temp = new int[nmemb];
int m = nmemb / 2; // 分割位置
mergesort(base, m); // 左側
mergesort(&base[m], nmemb - m); // 右側
for (int i = 0; i < nmemb; i++) {
temp[i] = base[i];
}
int p = 0; // 分割左側の最初の添字
int q = m; // 分割右側の最初の添字
int i = 0;
do {
if (temp[p] < temp[q]) {
base[i] = temp[p];
p++;
}
else {
base[i] = temp[q];
q++;
}
i++;
} while (p < m && q < nmemb);
if (p == m) {
for (; i < nmemb; i++) {
base[i] = temp[q];
q++;
}
}
else if (q == nmemb) {
for (; i < nmemb; i++) {
base[i] = temp[p];
p++;
}
}
delete[] temp;
}
// ベクトルの要素を順に表示
template<class InputIterator>
void disp(InputIterator first, InputIterator last)
{
for (InputIterator i = first; i != last; i++)
cout << ' ' << *i;
}
int main()
{
random_device rd;
vector<int> x;
// ベクトル x に要素 0 〜 9 を挿入
for (unsigned i = 0; i < 10; i++)
x.push_back(i);
cout << "シャッフル前\n";
disp(x.begin(), x.end()); cout << "\n\n";
cout << "シャッフル後\n";
// シャッフル
shuffle(x.begin(), x.end(), rd);
disp(x.begin(), x.end()); cout << "\n\n";
cout << "ソート後\n";
mergesort(&x[0], x.size()); // マージソート
disp(x.begin(), x.end()); cout << '\n';
}
この記事へのコメント
コメントを書く
この記事へのトラックバックURL
https://fanblogs.jp/tb/7357714
※ブログオーナーが承認したトラックバックのみ表示されます。
この記事へのトラックバック
