1

以下のプログラム ("from here" の後の行) は、私が頻繁に使用しなければならない構造です。(最終的に固有ライブラリの関数を使用して) ベクトル化するか、このプログラムをより高速に実行できるかどうか疑問に思っていました。

基本的に、 のベクトルが与えられたfloat x場合、この構文は のソートされた要素のインデックスをベクトル に復元xしintますSIndex。たとえば、 の最初のエントリSIndexが 10 の場合、 の 10 番目の要素xが の最小の要素であったことを意味しxます。

#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>

using std::vector;
using namespace std;

typedef pair<int, float> sortData;
bool sortDataLess(const sortData& left, const sortData& right){
    return left.second<right.second;
}

int main(){
    int n=20,i;
    float LO=-1.0,HI=1.0;
    srand (time(NULL));
    vector<float> x(n);
    vector<float> y(n);
    vector<int> SIndex(n);  
    vector<sortData> foo(n);
    for(i=0;i<n;i++) x[i]=LO+(float)rand()/((float)RAND_MAX/(HI-LO));
    //from here:
    for(i=0;i<n;i++) foo[i]=sortData(i,x[i]);
    sort(foo.begin(),foo.end(),sortDataLess);
    for(i=0;i<n;i++){
        sortData bar=foo[i];
        y[i]=x[bar.first];
        SIndex[i]=bar.first;
    }
    for(i=0;i<n;i++) std::cout << SIndex[i] << std::endl;

    return 0;
}
4

1 に答える 1

1

これが並べ替えの問題であるという事実を回避することはできず、ベクトル化によって必ずしも並べ替えが大幅に改善されるとは限りません。たとえば、クイックソートの分割ステップでは比較を並行して実行できますが、比較に合格した 0 ～ <em>n の値を選択して保存する必要があります。これは絶対に実行できますが、ベクトル化から得られる利点が失われ始めます。比較マスクからシャッフル マスクに変換する必要があり、これはおそらくルックアップ テーブル (悪い) であり、可変サイズのストアが必要です。これは、アラインメントがないことを意味します (悪いですが、それほど悪くはないかもしれません)。Mergesort は 2 つの並べ替えられたリストをマージする必要があり、場合によってはベクトル化によって改善される可能性がありますが、最悪の場合 (私が思うに) スカラーの場合と同じ数のステップが必要です。

std::sortそしてもちろん、ベクトル化による大幅な速度向上は、標準ライブラリの実装内で既に行われている可能性が十分にあります。ただし、それを取得するには、デフォルトの比較演算子を使用してプリミティブ型を並べ替える必要があります。

ただし、パフォーマンスが心配な場合は、最後のループを簡単に回避できます。float 配列を比較として使用して、インデックスのリストを並べ替えるだけです。

struct IndirectLess {
    template <typename T>
    IndirectLess(T iter) : values(&*iter) {}

    bool operator()(int left, int right)
    {
        return values[left] < values[right];
    }

    float const* values;
};

int main() {
    // ...
    std::vector<int> SIndex;
    SIndex.reserve(n);
    for (int i = 0; i < n; ++i)
        SIndex.push_back(n);

    std::sort(SIndex.begin(), SIndex.end(), IndirectLess(x.begin()));
    // ...
}

これで、ソートされたインデックスのリストのみが作成されました。キャッシュの局所性が失われる可能性があるため、非常に大きなリストの場合は遅くなる可能性があります。その時点で、アーキテクチャによっては、最後のループをベクトル化できる場合があります。ただし、これは単なるデータ操作であり、4 つの値を読み取り、1 番目と 3 番目を別の場所に保存し、2 番目と 4 番目を別の場所に保存します。

于 2012-07-01T19:44:55.950 に答える