创建双向量的排名 [英] Create ranking for vector of double

问题描述

我有一个向量与我要排名的双打（实际上它是一个向量与对象与一个双成员 costs ）。如果只有唯一的值或者我忽略非唯一值，那么没有问题。但是，我想使用非唯一值的平均排名。此外，我已经发现了一些关于行列的问题，但他们忽略了非唯一的值。

I have a vector with doubles which I want to rank (actually it's a vector with objects with a double member called costs). If there are only unique values or I ignore the nonunique values then there is no problem. However, I want to use the average rank for nonunique values. Furthermore, I have found some question at SO about ranks, however they ignore the non-unique values.

例如，我们有（1,5,4,5， 5），则相应的秩应该是（1,4,2,4,4）。当我们忽略非唯一值时，排名为（1，3，2，4，5）。

Example, say we have (1, 5, 4, 5, 5) then the corresponding ranks should be (1, 4, 2, 4, 4). When we ignore the non-unique values the ranks are (1, 3, 2, 4, 5).

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

When ignoring the nonunique values I used the following:

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 ，因为IMO导致干净的代码。

Does anyone know how to take the non-unique values into account? I prefer using std::algorithm since IMO this lead to clean code.

推荐答案

这样做的一种方法是使用 multimap 。

One way to do so would be using a multimap.

• 将项目放置在多重映射中将对象映射到 size_t s（初始值不重要）。

• Place the items in a multimap mapping your objects to size_ts (the intial values are unimportant). You can do this with one line (use the ctor that takes iterators).

循环（显式或使用算法），并指定0，1，...作为值。

Loop (either plainly or using whatever from algorithm) and assign 0, 1, ... as the values.

对于每个不同的键，请调用 equal_range ，并将其值设置为平均值（同样，您可以使用算法中的内容）。

Loop over the distinct keys. For each distinct key, call equal_range for the key, and set its values to the average (again, you can use stuff from algorithm for this).

总体复杂度应该是 ，其中向量的长度。

The overall complexity should be Theta(n log(n)), where n is the length of the vector.

这篇关于创建双向量的排名的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！