Создать рейтинг для вектора двойного

У меня есть вектор с двойными элементами, который я хочу ранжировать (на самом деле это вектор с объектами с двойным членом, называемым 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 это приводит к чистому коду.


c++ rank algorithm c++11
person Michiel uit het Broek    schedule 13.06.2015    source источник
comment
Что ты имеешь в виду average rank for non unique values? Разве это не будет само (неуникальное) значение?   -  person barak manos    schedule 13.06.2015
comment
@barakmanos, см. пример, приведенный в вопросе. Значение 5 не уникально, и если мы его проигнорируем, ранги будут (1, 3, 2, 4, 5). Затем есть три пятерки, каждая с разным рангом. В статистике принято присваивать среднее значение этих рангов, avg(3, 4, 5, ) = 4, всем значениям 5.   -  person Michiel uit het Broek    schedule 13.06.2015

Ответы (3)


arrow_upward
1
arrow_downward

Один из способов сделать это — использовать multimap.

  • Поместите элементы в мультикарту, сопоставив ваши объекты с size_ts (начальные значения не важны). Вы можете сделать это с помощью одной строки (используйте ctor, который принимает итераторы).

  • Цикл (либо просто, либо с использованием чего-либо из algorithm) и назначьте 0, 1, ... в качестве значений.

  • Цикл по отдельным клавишам. Для каждого отдельного ключа вызовите equal_range для ключа и установите для него значения средний (опять же, для этого можно использовать материал из algorithm).

Общая сложность должна быть равна Theta(n log(n)), где n — длина вектора.

person Ami Tavory    schedule 13.06.2015

arrow_upward
4
arrow_downward

Вот процедура для векторов, как следует из названия вопроса:

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<> по умолчанию.

person René Richter    schedule 14.06.2015

arrow_upward
0
arrow_downward

Что-то в этом роде:

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). Для каждого такого прогона вы вычисляете его средний рейтинг и устанавливаете его для всех элементов в прогоне.

person Igor Tandetnik    schedule 13.06.2015