3

我有某种类型的元素数组T。对于一些复杂的函数在此处输入图像描述，我想按该函数的值对数组进行排序。有效率的。

当我对如何做这样的事情进行一些研究时，我很快发现 range::v3::sort，从 range-v3 库中，可以在projections的帮助下使用。在这种情况下，T可以将该值投影到比较器使用的新值上。问题是，它是懒惰地完成的。

考虑以下示例：

#include <range/v3/algorithm/sort.hpp>
#include <vector>
#include <iostream>

int main() {
    int invocations=0;
    std::vector<int> data{1,5,2,7,6,3,4,8,9,0};
    auto f = [&](int val){
        ++invocations;
        return val%2 ? val+100 : val;
    };
    ranges::v3::sort(data, std::less<int>{}, f);
    for (int v : data) {
        std::cout << v << ' ';
    }
    std::cout << "Invocations " << invocations << std::endl;
}

为简洁起见，此处保持T简单。f这给了我输出：

0 2 4 6 8 1 3 5 7 9 Invocations 60

但设想这f是一些我不想重复执行的复杂功能，每次在比较器中使用它（否则我可以编写一个自定义比较器并使用常规std::sort）。我希望f每个值都只被调用一次。但是，一旦对数组进行了排序，f就可以丢弃 的结果。

此外，它们自身的真实价值T也相对复杂。我可以快速交换两个元素，但我不应该将它们复制到一个新的临时容器（例如std::vector<std::pair<T,int>>）中进行排序。

除了手动排序我的输入数组之外，还有一些简单的方法吗？

4

3 回答 3

3

您可以存储评估，并将其用作投影（我实际上不投影，因为元组的顺序很好，原始数据也可比较）：

std::vector<int> data{1,5,2,7,6,3,4,8,9,0};
auto values = data | ranges::view::transform(f) | ranges::to_vector;
// to_vector needed to do evaluation **now**.
ranges::v3::sort(ranges::view::zip(values, data)); // Values first to avoid real projection
                                                   // else use projection on `get<I>`.

演示

于 2018-12-14T17:58:08.190 回答
1

您显然需要存储函数调用。如果您不想在地图中执行此操作（因此您可以按数据值进行索引）但在向量中（比地图的开销要少得多），那么您不能直接对原始数组进行排序（因为您没有链接从每个数据值到其函数值，都需要索引）。因此，我们将索引排序到数据数组中：

int invocations=0;
std::vector<int> data{1,5,2,7,6,3,4,8,9,0};
auto f = [&](int val){
    ++invocations;
    return val%2 ? val+100 : val;
};

std::vector<int> fValues(data.size());
std::vector<int> indices(data.size());

std::transform(data.begin(), data.end(), fValues.begin(), f);

std::iota(indices.begin(), indices.end(), 0);
std::sort(indices.begin(), indices.end(), [&](auto i, auto j) {
    return fValues[i] < fValues[j];
});

for (int sortedIndex : indices) {
    std::cout << data[sortedIndex] << ' ';
}
std::cout << "Invocations " << invocations << std::endl;

您仍然必须应用排列才能获得与直接通过比较值进行排序完全相同的效果f，但这对您来说可能是不必要的。

演示

于 2018-12-14T17:23:04.460 回答
0

根据 Phil M 的建议和 Max Langhof 的部分解决方案（谢谢！），我设计了以下具有非延迟投影的排序功能的相对通用实现。它使用链接的就地置换函数。

#include <vector>
#include <algorithm>
#include <iostream>

template <typename T, typename Comp, typename Proj>
void sort_proj(std::vector<T>& v, Comp cmp, Proj f) {
    using FRet = std::invoke_result_t<Proj, T>;
    using Tmp = std::pair<size_t, FRet>;

    //create temporary values of f
    std::vector<Tmp> fval;
    fval.reserve(v.size());
    for (size_t i=0; i<v.size(); ++i)
        fval.emplace_back(i, f(v[i]));

    //sort it
    std::sort(fval.begin(), fval.end(), [&cmp](const Tmp& a, const Tmp& b) { return cmp(a.second, b.second); });

    //apply the permutation
    //based on https://stackoverflow.com/a/17074810/635654
    std::vector<bool> done(v.size());
    for (std::size_t i = 0; i < v.size(); ++i) {
        if (done[i])
            continue;
        done[i] = true;
        std::size_t prev_j = i;
        std::size_t j = fval[i].first;
        while (i != j) {
            std::swap(v[prev_j], v[j]);
            done[j] = true;
            prev_j = j;
            j = fval[j].first;
        }
    }
}

int main() {
    int invocations=0;
    std::vector<int> data{1,5,2,7,6,3,4,8,9,0};
    auto f = [&](int val){
        ++invocations;
        return val%2 ? val+100 : val;
    };
    sort_proj(data, std::less<int>{}, f);
    for (int v : data) {
        std::cout << v << ' ';
    }
    std::cout << "Invocations " << invocations << std::endl;
}

我希望有一些库或现有工具的非常短的应用程序，以避免重新发明轮子。

于 2018-12-14T17:37:55.107 回答