Если вы хотите всегда создавать ранг для всего массива, тогда первый параметр n является избыточным - вы можете получить ту же информацию из arr.size(). Избыточности могут быть источниками ошибок, поэтому в этом случае лучше сбросить параметр:
std::vector<size_t> getRank(std::vector<double> const& arr);
Два других изменения:
- Похоже, что ранг никогда не получится отрицательное; тогда неподписанный тип - лучший выбор.
size_t подходит для хранения любого количества элементов, которые вы можете упаковать в std::vector, так что это хороший тип. Только если это потребует слишком много памяти, я бы прибегнул к меньшему типу ... - При использовании константной ссылки избегается копирование вектора. В любом случае вы не собираетесь изменять его, поэтому создавать копии не нужно. Это особенно актуально для вашей
getHighestVal -функции, которая вызывается снова и снова.
Однако нет необходимости заново изобретать колесо, уже есть std::max_element, который делает то же самое. ..
std::vector<size_t> getRank(std::vector<double> const& arr)
{
vector<size_t> rank(arr.size());
vector<bool> used(arr.size(), false);
// Noticed second argument? It makes the subsequent loop obsolete...
//for (int i = 0; i < n; i++)
// used[i] = false;
// using std:max_element instead
auto lowestVal = std::max_element(arr.begin(), arr.end()) - arr.begin();
// std::max_element returns an iterator, though – for getting an index,
// we need to calculate the difference to first element
std::cout << "Pass waypoint lowestVal" << std::endl;
// now avoid calling std::max_element again and again!
auto lowestValConst = lowestVal;
for (size_t i = 1; i <= arr.size(); i++)
{
for (size_t j = 0; j < arr.size(); j++)
{
if (!used[j] && arr[lowestVal] > arr[j])
lowestVal = j;
}
rank[lowestVal] = i;
used[lowestVal] = true;
// avoid re-calculation:
lowestVal = lowestValConst; //getHighestVal(n, arr);
std::cout << "\rPass waypoint RANKING Loop2: " << arr.size();
}
std::cout << "Pass waypoint RANKING" << std::endl;
}
Однако этот алгоритм все еще остается алгоритмом O (n²). Вы можете лучше, тем не менее, к O (n * log (n)):
std::vector<size_t> getRank(std::vector<double> const& arr)
{
std::vector<std::pair<double, size_t>> values;
values.reserve(arr.size()); // avoid re-allocations
size_t index = 0;
for(auto d : arr)
values.emplace_back(d, index++);
// copying the array into a second one with indices paired: O(n)
std::sort
(
values.begin(), values.end(),
std::greater<std::pair<double, size_t>>
);
// std::pair has already a lexicographical operator<, so we can use that one
// – but because of lexicographical comparison it is important to use the
// double value as first element; the index as second element then, as a
// bonus assures stable sorting...
// still we want to get descending order, so we need to compare with
// greater instead of default of less
// sorting has complexity of O(n*log(n))
// we need to copy the indices into the ranks:
std::vector<size_t> rank(arr.size());
index = 0;
for(auto& v : values)
//ranks[v.second] = index++;
// pre-increment: you seem to need 1-based rank...
ranks[v.second] = ++index;
// copying back: O(n)
}
Всего сейчас O (n) + O (n * log (n) + O (n), что O (n * log (n)) всего.
Имейте в виду, что приведенный выше код не проверен - если вы столкнулись с ошибкой, пожалуйста, исправьте ее самостоятельно ...