获取向量<float>中 k 个最大值的 indize 的有效方法

Question

如何

从vector<float>创建std::map<int, float>，以便映射包含来自向量的 k 个最大值，键与向量中值的索引有关。

一种幼稚的方法是遍历向量（O（n）），提取和擦除（O（n））最高元素k次（O（k）），导致O（k*n^2）的复杂性，我猜这是次优的。

更好的是只复制（O（n））并删除最小的，直到大小为k。这将导致 O（n^2）。仍然是多项式...

有什么想法吗？

Answer 1

以下应该可以完成这项工作：

#include <cstdint>
#include <algorithm>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>
// Compare: greater T2 first.
struct greater_by_second
{
    template <typename T1, typename T2>
    bool operator () (const std::pair<T1, T2>& lhs, const std::pair<T1, T2>& rhs)
    {
        return std::tie(lhs.second, lhs.first) > std::tie(rhs.second, rhs.first);
    }
};

std::map<std::size_t, float> get_index_pairs(const std::vector<float>& v, int k)
{
    std::vector<std::pair<std::size_t, float>> indexed_floats;
    indexed_floats.reserve(v.size());
    for (std::size_t i = 0, size = v.size(); i != size; ++i) {
        indexed_floats.emplace_back(i, v[i]);
    }
    std::nth_element(indexed_floats.begin(),
                     indexed_floats.begin() + k,
                     indexed_floats.end(), greater_by_second());
    return std::map<std::size_t, float>(indexed_floats.begin(), indexed_floats.begin() + k);
}

让我们测试一下：

int main(int argc, char *argv[])
{
    const std::vector<float> fs {45.67f, 12.34f, 67.8f, 4.2f, 123.4f};
    for (const auto& elem : get_index_pairs(fs, 2)) {
        std::cout << elem.first << " " << elem.second << std::endl;
    }
    return 0;
}

输出：

2 67.8
4 123.4

Answer 2

您可以保留到目前为止 k 最大值的列表，并针对向量中的每个值更新它，这会将您降低到 O（n*log k）（假设每次更新最大值列表的日志 k）或者，对于朴素列表，O（kn）。

你可能会更接近O（n），但假设k可能很小，可能不值得付出努力。

Answer 3

您的最优解将具有 O（n+k*log（k）） 的复杂度，因为对 k 个元素进行排序可以简化为此复杂度，并且您必须至少查看每个元素一次。

我想到了两种可能的解决方案：

1. 遍历向量，同时将所有元素添加到有界（大小 k）优先级队列/堆中，同时保留它们的索引。

2. 创建包含原始索引的向量副本，即 std::vector<std::pair<float, std::size_t>>并使用std::nth_element使用仅比较第一个元素的比较器将 k 个最大值移动到前面。然后将这些元素插入到目标地图中。具有讽刺意味的是，最后一步在整体复杂性中增加了k*log（k），而nth_element是线性的（但会排列你的索引）。

Answer 4

也许我不明白，但如果增量方法不是一种选择，为什么不使用std::sort std::partial_sort？

这应该是一个 o（n log k），并且由于 k 很可能很小，这实际上是一个 o（n）。

编辑：感谢迈克·西摩的更新。编辑（之二）：

这个想法是使用中间向量进行排序，然后将其放入地图中。试图减少计算顺序只适用于大量数据，所以我想复制时间（以 o（n） 为单位）可能会在背景噪音中丢失。

编辑（之二）：

这实际上是所选答案的作用，没有:)的理论解释。