Эффективный способ получить значения k самых высоких значений в векторе & lt; float & gt;

Question

Эффективный способ получить значения k самых высоких значений в векторе & lt; float & gt;

Как я могу создать std::map<int, float> из vector<float>, так что карта содержит k наибольших значений из вектора с ключами, являющимися индексом значения в векторе.

Наивным подходом было бы пройти вектор (O (n)), извлечь и стереть (O (n)) самый высокий элемент k раз (O (k)), что приведет к сложности O (k * n ^ 2) , что является неоптимальным, я думаю.

Еще лучше было бы просто скопировать (O (n)) и удалить наименьшее, пока размер не станет k. Что привело бы к O (n ^ 2). Все еще полином …

Есть идеи?

0

c++time-complexity

Решение

Другие решения

Вы можете сохранить список k-максимальных значений до настоящего времени и обновлять его для каждого из значений в вашем векторе, что сводит вас к O (n * log k) (предполагая log k для каждого обновления списка наивысших значения) или, для наивного списка, O (kn).

Вы, вероятно, можете приблизиться к O (n), но если предположить, что k, вероятно, довольно мало, может не стоить усилий.

1

Ваше оптимальное решение будет иметь сложность О (п + к * лог (к)), поскольку сортировка k элементов может быть сведена к этому, и вам придется взглянуть на каждый из элементов хотя бы один раз.

На ум приходят два возможных решения:

Выполните итерацию по вектору, добавляя все элементы в ограниченную (размер k) приоритетную очередь / кучу, также сохраняя их индексы.
Создайте копию вашего вектора с включением оригинальных индексов, т.е. std::vector<std::pair<float, std::size_t>> и использовать std::nth_element переместить наивысшие значения k вперед, используя компаратор, который сравнивает только первый элемент. Затем вставьте эти элементы в вашу целевую карту. По иронии судьбы этот последний шаг добавляет вам k * log (k) в общей сложности, в то время как nth_element является линейным (но переставит ваши индексы).

0

Может быть, я не понял, но в случае, если инкрементальный подход не вариант, почему бы не использовать ~~std::sort~~ std::partial_sort?

Это должно быть o (n log k), и так как k, скорее всего, будет маленьким, то это практически o (n).

Изменить: спасибо Майку Сеймуру за обновление.
Изменить (бис):

Идея состоит в том, чтобы использовать промежуточный вектор для сортировки, а затем поместить его в карту. Попытка уменьшить порядок вычислений будет оправдана только для значительного объема данных, поэтому я предполагаю, что время копирования (в o (n)) может быть потеряно при фоновом шуме.

Изменить (бис):

Это именно то, что делает выбранный ответ, без теоретических объяснений :).

0

Источник

Accepted Answer

Следующие должны сделать работу:

#include <cstdint>
#include <algorithm>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>

// Compare: greater T2 first.
struct greater_by_second
{
template <typename T1, typename T2>
bool operator () (const std::pair<T1, T2>& lhs, const std::pair<T1, T2>& rhs)
{
return std::tie(lhs.second, lhs.first) > std::tie(rhs.second, rhs.first);
}
};std::map<std::size_t, float> get_index_pairs(const std::vector<float>& v, int k)
{
std::vector<std::pair<std::size_t, float>> indexed_floats;

indexed_floats.reserve(v.size());
for (std::size_t i = 0, size = v.size(); i != size; ++i) {
indexed_floats.emplace_back(i, v[i]);
}
std::nth_element(indexed_floats.begin(),
indexed_floats.begin() + k,
indexed_floats.end(), greater_by_second());
return std::map<std::size_t, float>(indexed_floats.begin(), indexed_floats.begin() + k);
}

Давайте проверим это:

int main(int argc, char *argv[])
{
const std::vector<float> fs {45.67f, 12.34f, 67.8f, 4.2f, 123.4f};

for (const auto& elem : get_index_pairs(fs, 2)) {
std::cout << elem.first << " " << elem.second << std::endl;
}
return 0;
}

Выход:

2 67.8
4 123.4

2