将一个向量相对于另一个向量排序 - 最有效的方法？

Question

我知道这个问题已经 被问 了好 几次,但是对于简单的情况(紧凑性,可读性或用户熟练程度是决定因素)提供了不同的答案,我不确定哪一个是最有效的,因为我担心重复该操作O(1M)次.

设置如下:

• 两个向量A和B的float的; 这不能改变,但可以从A和创建其他结构B.
• A并且B长度相等,至少为4,最多为20(如果这对任何方式都有帮助).
• A需要根据其条目的值按降序排序,而B只需要匹配A的顺序.

例:

A = {2,4,3,1} -> {4,3,2,1}
     | | | |
B = {1,2,3,4} -> {2,3,1,4}

题:

这样做最有效(快速+节省内存)的方法是什么？

Answer 1

一种常见的方法是创建索引并对其进行排序,而不是对原始值进行排序.这称为间接排序或argsort.

例:

using values_t = std::vector<float>;
using index_t = std::vector<uint8_t>;

index_t make_sorted_index(values_t const& values) {
    index_t index(values.size());
    std::iota(index.begin(), index.end(), 0);
    std::sort(index.begin(), index.end(), [&values](uint8_t a, uint8_t b) { return values[a] > values[b]; } );
    return index;
}

int main() {
    values_t a = {2,4,3,1};
    values_t b = {1,2,3,4};

    auto index = make_sorted_index(a);

    std::cout << "A = {";
    for(auto i : index)
        std::cout << a[i] << ',';
    std::cout << "\b}\n";

    std::cout << "B = {";
    for(auto i : index)
        std::cout << b[i] << ',';
    std::cout << "\b}\n";
}

输出:

A = {4,3,2,1}
B = {2,3,1,4}