1

下面的程序（嗯，“从这里”之后的行）是一个我必须经常使用的结构。我想知道是否有可能（最终使用 eigen 库中的函数）矢量化或以其他方式使该程序运行得更快。

本质上，给定一个向量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 需要合并两个排序列表，在某些情况下可以通过向量化来改进，但在最坏的情况下（我认为）需要与标量情况相同的步数。

而且，当然，您从矢量化中获得的任何主要速度提升都很有可能已经在您的标准库的std::sort实现中完成。但是，要获得它，您需要使用默认比较运算符对原始类型进行排序。

不过，如果您担心性能，您可以轻松避免最后一个循环。只需使用浮点数组作为比较对索引列表进行排序：

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()));
    // ...
}

现在您只生成了排序索引列表。您可能会丢失一些缓存位置，因此对于非常大的列表可能会更慢。到那时，可能会根据架构对最后一个循环进行矢量化。不过，这只是数据操作——读取四个值，将第一个和第三个存储在一个地方，将第二个和第四个存储在另一个地方——所以我不指望 Eigen 在这一点上有多大帮助。

于 2012-07-01T19:44:55.950 回答