如何高效地对数组进行排序并获取排列索引？

Question

如何高效地对数组进行排序并获取排列索引？

3

我有两个随机访问的可迭代对象：一个包含值，另一个包含排列索引。我想对这些值进行排序，并跟踪排列索引的变化。

示例输入：

std::array values{7, 45, 18, 33, 77, 96, 83, 80, 4, 51};
std::array<int, values.size()> index;

输出：

values == {4, 7, 18, 33, 45, 51, 77, 80, 83, 96};
index == {8, 0, 2, 3, 1, 9, 4, 7, 6, 5};

简单的解决方案

一个解决方案是构建一个包含值和索引的pair向量，通过值对这个向量进行排序，然后从中提取解决方案。但原始向量可能很大，所以我想避免两次转换。我将给这个解决方案取一个别名vector pair sort。

另一个解决方案

我可以使用值可迭代对象中的值来对排列索引（最初包含0、1、2...）进行std::sort。这在如何在排序后获取索引排列中有描述。这将给我排列索引，但不会对值可迭代对象进行排序。从这里我可以做两件事：

std::sort() 排序值。

我将不得不对数据进行两次排序。我希望避免这样做。比较运算符可能不便宜。这个解决方案将是 double sort。
使用排列索引对值进行排序。

我不太确定如何做到这一点。一个解决方案在这里描述 here。这个解决方案是 boost index apply sort（因为它是由 boost::algorithm::apply_permutation() 实现的）。这会修改排列索引，所以在传递给 boost::algorithm::apply_permutation() 之前我必须创建一个副本。

一个可以直接进行排序的简单解决方案在这里描述 here。这是 permutate in place sort。

另一个解决方案是将索引转换成 cycles，然后应用它。我还没有实现这个。

最佳解决方案

我认为最合理的方法是按照正常顺序对值进行排序，但是当排序算法交换两个值时，也应该交换相应的排列索引。

这样一来，两个可迭代对象都会同时就地排序，而不会增加任何额外的成本。

但是我不知道如何实现这一点。如果我要实现排序算法，只需添加一个额外的swap()函数，问题就可以解决了。但是我想重用std::sort()。它给我提供了一个相当快速的排序算法，而无需编写代码。将来，我还可以通过将std::sort()替换为custom_sort()（假设custom_sort()具有相同的签名，这是一个合理的假设）来使用不同的算法。

我对swap()很感兴趣。std::sort()使用这个函数来交换元素。我的目标是重写这个函数，使其交换实际的值和索引。

其中一种方法是创建一个自定义迭代器，它将组合值和索引的迭代器。这个迭代器在调用operator*或operator[]时会返回对包装值的引用。这个包装值将具有自定义的swap()。

基准测试

顺便说一下，我做了一些基准测试。你可以在https://github.com/meator/indexsort_impl找到这些测试和实现。我尝试对包含 1,000,000 个随机int和double的vector进行排序。这些int的范围是从INT_MIN到INT_MAX，而double的范围是从0到1。我进行了200次样本运行。以下是结果：

功能	`int` 基准测试	`double` 基准测试
值排序*	114.153 毫秒	127.824 毫秒
使用值进行索引排序*	177.985 毫秒	206.153 毫秒
向量对排序	122.795 毫秒	139.467 毫秒
双精度排序	291.954 毫秒	339.121 毫秒
使用 Boost 库的索引应用排序	263.827 毫秒	298.844 毫秒
原地排列排序	679.917 毫秒	708.676 毫秒

“简单”的向量对排序效果出奇的好。也许编译器很聪明。

问题

使用迭代器的方式是我的“最佳”解决方案可行吗？我该如何实现呢？是否有其他被我忽略的解决方案？哪个是最好的？

编辑：我的基准测试存在一个严重的缺陷，使所有结果无效。我已经修复了这个问题。我还按照Paul Sanders的建议添加了原始排序基准测试。当然，这些并不是索引排序。

* 如上所述，这些并不是真正的索引排序。

- user13840624

2

简单的解决方案可能是适应的：对 zip_view 进行排序（std C++23，使用 ranges-v3 适用于之前的标准）。 - Jarod42

2

可以采用简单的解决方案：使用 zip_view（std C++23）进行排序，对于之前的标准，请使用 ranges-v3。 - Jarod42

2

可能会采用简单的解决方案：对 zip_view 进行排序（使用 std C++23，对于之前的标准，请使用 ranges-v3）。 - undefined

vector pair sort与仅对值向量进行排序相比，执行时间如何？ - Paul Sanders

我已经为基准测试添加了简单的排序功能。 - user13840624

显示剩余6条评论

2个回答

0

你的“最佳”解决方案并不会是最好的，因为它在只需要O(N)次交换时却进行了O(N log N)次交换。

我认为实际上最好的选择是使用值来对索引进行排序，然后使用排列索引在O(N)时间内重新排序值。

这里有一个简单的实现，它临时地反转排列索引中的条目，以标记我们已经排序过的值位置，然后修复它们。完成后，data和index都是正确的。

我从你链接的@SergeyKalinichenko的答案中借用了排序部分。

vector<int> index(data.size(), 0);
for (int i = 0 ; i != index.size() ; i++) {
    index[i] = i;
}
sort(index.begin(), index.end(),
    [&](const int& a, const int& b) {
        return (data[a] < data[b]);
    }
);
for (int target = 0; target < index.size(); ++target) {
    int src = index[target];
    if (src < 0) {
        // did this one already
        index[target] = ~src;
        continue;
    }
    if (src == target) {
        //already in the right place
        continue;
    }
    auto save = data[target];
    int t2 = target;
    do {
        data[t2] = data[src];
        t2 = src;
        src = index[t2];
        index[t2] = ~src; // mark t2 position as done. invar: t2 > target
    } while(src != target);
    data[t2] = save;
}

- Matt Timmermans

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Accepted Answer

你最好的解决方案应该是可行的。根据std::sort，C++20之前只有一个签名。

template< class RandomIt >
void sort( RandomIt first, RandomIt last );

并且在它变化之后

template< class RandomIt >
constexpr void sort( RandomIt first, RandomIt last );

在满足LegacyRandomAccessIterator和ValueSwappable的要求下，其中class RandomIt看起来像是迭代器可以包含索引和指向两个数组的指针，实现正确的方法，并且有一个接受两个迭代器并交换其内容的交换函数。

然后你可以使用std::sort而无需新的大型数据结构。