代码之家 › 专栏 › 技术社区 › CygnusX1 Stack Overflow is garbage

按非惰性lambda表达式/投影排序

range-v3 c++11 sorting c++

3

CygnusX1 Stack Overflow is garbage · 技术社区 · 7 年前

我有某种类型的元素数组 T . 对于某些复杂函数我想按函数的值对数组进行排序。高效。

当我研究如何做这样的事情时,我很快发现 range::v3::sort 在range-v3库中,可以在投影 . 在这种情况下, 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>> 用于排序。

除了手动排序输入数组之外,还有什么简单的方法吗?

3 回复 | 直到 7 年前

1

3

Jarod42 7 年前

您可以存储评估,并将其用作投影(实际上,我不会投影为元组的顺序很好,原始数据也是可比较的):

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>`.

Demo

2

1

Max Langhof 7 年前

显然,您需要存储函数调用。如果您不想在一个映射中(这样您就可以通过数据值进行索引)但是在一个向量中(比映射开销小得多),那么您就不能直接对原始数组进行排序(因为您没有从每个数据值到其函数值的链接,所以需要索引)。因此,我们将索引排序到数据数组中:

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 价值观,但也许这对你来说是不必要的。

Demo

3

0

CygnusX1 Stack Overflow is garbage 7 年前

根据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;
}

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