c++ - 为 double vector 创建排名

Question

我有一个带有 double 的 vector ，我想对其进行排名(实际上它是一个带有对象的 vector ，该对象具有一个名为 costs 的 double 成员)。如果只有唯一值或我忽略非唯一值，则没有问题。但是，我想对非唯一值使用平均排名。此外，我在 SO 上发现了一些关于等级的问题，但是他们忽略了非唯一值。

例如，假设我们有 (1, 5, 4, 5, 5) 那么相应的排名应该是 (1, 4, 2, 4, 4)。当我们忽略非唯一值时，排名为 (1, 3, 2, 4, 5)。

当忽略非唯一值时，我使用了以下内容:

void Population::create_ranks_costs(vector<Solution> &pop)
{
  size_t const n = pop.size();

  // Create an index vector
  vector<size_t> index(n);
  iota(begin(index), end(index), 0);

  sort(begin(index), end(index), 
       [&pop] (size_t idx, size_t idy) { 
         return pop[idx].costs() < pop[idy].costs();
       });

  // Store the result in the corresponding solutions
  for (size_t idx = 0; idx < n; ++idx)
    pop[index[idx]].set_rank_costs(idx + 1);
}

有谁知道如何考虑非唯一值？我更喜欢使用 std::algorithm，因为在我看来这会导致干净的代码。

Answer 1

正如问题的标题所暗示的那样，这是 vector 的例程:

template<typename Vector>
std::vector<double> rank(const Vector& v)
{
    std::vector<std::size_t> w(v.size());
    std::iota(begin(w), end(w), 0);
    std::sort(begin(w), end(w), 
        [&v](std::size_t i, std::size_t j) { return v[i] < v[j]; });

    std::vector<double> r(w.size());
    for (std::size_t n, i = 0; i < w.size(); i += n)
    {
        n = 1;
        while (i + n < w.size() && v[w[i]] == v[w[i+n]]) ++n;
        for (std::size_t k = 0; k < n; ++k)
        {
            r[w[i+k]] = i + (n + 1) / 2.0; // average rank of n tied values
            // r[w[i+k]] = i + 1;          // min 
            // r[w[i+k]] = i + n;          // max
            // r[w[i+k]] = i + k + 1;      // random order
        }
    }
    return r;
}

工作示例参见 IDEone .

对于具有并列(相等)值的排名，有不同的约定(最小值、最大值、平均排名或随机顺序)。在最内层的 for 循环中选择其中之一(平均排名在统计中很常见，最小排名在运动中很常见)。

请注意，平均排名可以是非整数 (n+0.5)。 我不知道，如果四舍五入到整数等级 n是您的应用程序的问题。

该算法可以很容易地推广到用户定义的顺序，如 pop[i].costs() , 与 std::less<>默认。