8つのフロートで構成される小さな配列をたくさん並べ替える必要がありました。もともと私はstd :: sortを使用していましたが、そのパフォーマンスに不満があり、これによって生成されたコンペアスワップアルゴリズムを試しました:http://pages.ripco.net/~jgamble/nw.html
テストコードは次のとおりです。
template <typename T>
bool PredDefault(const T &a, const T &b) {return a > b;}
template <typename T>
bool PredDefaultReverse(const T &a, const T &b) {return a < b;}
template <typename T>
void Sort8(T* Data, bool(*pred)(const T &a, const T &b) = PredDefault) {
#define Cmp_Swap(a, b) if (pred(Data[a], Data[b])) {T tmp = Data[a]; Data[a] = Data[b]; Data[b] = tmp;}
Cmp_Swap(0, 1); Cmp_Swap(2, 3); Cmp_Swap(4, 5); Cmp_Swap(6, 7);
Cmp_Swap(0, 2); Cmp_Swap(1, 3); Cmp_Swap(4, 6); Cmp_Swap(5, 7);
Cmp_Swap(1, 2); Cmp_Swap(5, 6); Cmp_Swap(0, 4); Cmp_Swap(3, 7);
Cmp_Swap(1, 5); Cmp_Swap(2, 6);
Cmp_Swap(1, 4); Cmp_Swap(3, 6);
Cmp_Swap(2, 4); Cmp_Swap(3, 5);
Cmp_Swap(3, 4);
}
int lastTick;
int tick() {
int hold = lastTick;
lastTick = GetTickCount();
return lastTick - hold;
}
int main()
{
vector<vector<float>> rVec(1000, vector<float>(8));
for (auto &v : rVec) {
v[0] = ((float)rand()) * 0.001;
v[1] = ((float)rand()) * 0.001;
v[2] = ((float)rand()) * 0.001;
v[3] = ((float)rand()) * 0.001;
v[4] = ((float)rand()) * 0.001;
v[5] = ((float)rand()) * 0.001;
v[6] = ((float)rand()) * 0.001;
v[7] = ((float)rand()) * 0.001;
}
system("PAUSE");
tick();
for (int n = 0; n < 50000; n++)
for (int j = 0; j < rVec.size(); j++) {
std::sort(rVec[j].begin(), rVec[j].end(), PredDefault<float>);
std::sort(rVec[j].begin(), rVec[j].end(), PredDefaultReverse<float>);
//Sort8(rVec[j].data(), PredDefault<float>);
//Sort8(rVec[j].data(), PredDefaultReverse<float>);
}
cout << "\nTime: " << tick() << "\n";
system("PAUSE");
return 1;
}
どちらかをテストするときにコメントマークを追加/削除します。
私はあまり期待していませんでしたが、違いはスワッピングソートのものを支持して10倍です(vs2012のリリース構成でエネルギー節約のものをオフにしてテストを行いました)。結果もチェックしてください。これは正しいですか?
私がすぐに考えることができるいくつかの理由があります。
std::sort
ないO(nlogn)
比較を。ただし、表記の定数が大きくなる可能性があるため、このBigO表記は大きなNにも当てはまります。したがって、8つの値の範囲で実行して効率を判断することはできません。この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加