我有一个我想排名的双精度向量(实际上它是一个向量,其中包含一个名为 costs
的双精度成员的对象)。如果只有唯一值或我忽略非唯一值,则没有问题。但是,我想对非唯一值使用平均排名。此外,我在 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
,因为 IMO 这会导致干净的代码。
这是向量的例程,正如问题标题所暗示的那样:
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<>
。
是使用multimap
。
- 将
项目放置在将对象映射到
size_t
s 的多重映射中(初始值不重要)。您可以使用一行来执行此操作(使用接受迭代器的 ctor)。循环(无论是普通的还是使用
algorithm
中的任何内容)并分配 0、1、...作为值。循环遍历不同的键。对于每个不同的键,调用
equal_range
键,并将其值设置为平均值(同样,您可以使用algorithm
中的内容)。
整体复杂度应该是 Theta(n log(n)),其中 n 是向量的长度。
大致如下:
size_t run_start = 0;
double run_cost = pop[index[0]].costs();
for (size_t idx = 1; idx <= n; ++idx) {
double new_cost = idx < n ? pop[index[idx]].costs() : 0;
if (idx == n || new_cost != run_cost) {
double avg_rank = (run_start + 1 + idx) / 2.0;
for (size_t j = run_start; j < idx; ++j) {
pop[index[j]].set_rank_costs(avg_rank);
}
run_start = idx;
run_cost = new_cost;
}
}
基本上,您遍历排序序列并识别值相等的运行(可能长度为 1 的运行)。对于每个此类运行,计算其平均排名,并为运行中的所有元素设置它。