将一个向量相对于另一个向量排序-最有效的方法? [英] Sorting one vector with respect to another - most efficient way?

问题描述

我知道这个问题已经询问 一些

I'm aware that this question has already been asked a few times, but different answers have been provided for simple cases (where compactness, readability or user proficiency are the deciding factors) and I'm not sure which one is the most efficient, as I'm concerned with repeating that operation O(1M) times.

设置如下:

• float的两个向量A和B；不能更改，但是可以从A和B创建其他结构.
• A和B的长度相等，长度至少为4，最大为20(如果有任何帮助).
• A需要根据其条目的值按降序进行排序，而B只需匹配A的顺序.

• Two vectors A and B of float's; this cannot be changed, but additional structures can be created from A and B.
• A and B have equal length, which is at least 4 and at most 20 (if that's helpful in any way).
• A needs to be sorted in descending order based on the values of its entries, while B simply needs to match A's ordering.

示例:

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

问题:

最有效的 (=快速+节省内存)方式是什么?

What's the most efficient (= fast + memory saving) way of doing this?

推荐答案

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

One common way is to create an index and sort it, rather than sorting the original values. This is known as indirect sort or 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}

这篇关于将一个向量相对于另一个向量排序-最有效的方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！