как бы отсортировать список и получить верхние элементы K? (СТЛ)

Question

У меня есть вектор двойников. Я хочу отсортировать это от самого высокого до самого низкого, и получить индексы верхних элементов K. std :: sort просто сортирует на месте и не возвращает индексы, которым я верю. Каким был бы быстрый способ получить верхние индексы K самых больших элементов?

Answer 1

вы можете использовать алгоритм nth_element STL - он вернет вам N наибольших элементов (это самый быстрый способ, используя stl), а затем использовать .sort для них, или вы можете использовать алгоритм частичной_сортировки, если вы хотите отсортировать первые K элементов (:

Использование просто .sort ужасно - это очень медленно для цели, которую вы хотите ... .sort - это отличный алгоритм STL, но для сортировки всего контейнера, а не только первых K элементов (; это не случайно существование nth_element иpartal_sort;)

Answer 2

Первое, что приходит на ум, несколько хакерски, но вы можете определить структуру, которая хранит как double, так и его исходный индекс, а затем перегрузить оператор

struct s {
    double d;
    int index;
    bool operator < (const struct &s) const {
        return d < s.d;
    }
};

Тогда вы можете получить исходные индексы из структуры.

Более полный пример:

vector<double> orig;
vector<s> v;
...
for (int i=0; i < orig.size(); ++i) {
    s s_temp;
    s_temp.d = orig[i];
    s_temp.index = i;
    v.push_back(s);
}
sort(v.begin(), v.end());
//now just retrieve v[i].index

В результате они будут отсортированы от наименьшего к наибольшему, но вместо этого вы могли бы перегрузить оператор>, а затем передать больший в функцию сортировки.

Answer 3

Таким образом, вам действительно нужна структура, которая отображает индексы в соответствующие двойные числа.

Вы можете использовать класс std::multimap для выполнения этого отображения.Как заметил Джейсон, std::map не допускает дублирования ключей.

std::vector<double> v; // assume it is populated already
std::multimap<double, int> m;
for (int i = 0; i < v.size(); ++i)
    m.insert(std::make_pair(v[i], i));
...

После того, как вы это сделаете, вы можете перебрать первые десять элементов, поскольку карта сохраняет сортировку ключей к элементам.

Answer 4

Используйте multimap для vector (значение, индекс), чтобы обрабатывать дубли. Используйте обратные итераторы, чтобы просмотреть результаты в порядке убывания.

#include <multimap>
#include <vector>
using namespace std;

multimap<double, size_t> indices;
vector<double> values;

values.push_back(1.0);
values.push_back(2.0);
values.push_back(3.0);
values.push_back(4.0);

size_t i = 0;
for(vector<double>::const_iterator iter = values.begin(); 
        iter != values.end(); ++iter, ++i)
{
    indices.insert(make_pair<double,int>(*iter, i));
}

i = 0;
size_t limit = 2;
for (multimap<double, size_t>::const_reverse_iterator iter = indices.rbegin(); 
    iter != indices.rend() && i < limit; ++iter, ++i)
{
    cout << "Value " << iter->first << " index " << iter->second << endl;
}

Выход

Значение 4, индекс 3

Значение 3, индекс 2

Если вы хотите получить индексы vector после сортировки, используйте это:

#include <algorithm>
#include <vector>
using namespace std;

vector<double> values;

values.push_back(1.0);
values.push_back(2.0);
values.push_back(3.0);
values.push_back(4.0);

sort(values.rbegin(), values.rend());

Верхние записи K индексируются от 0 до K-1 и отображаются в порядке убывания. При этом используются обратные итераторы в сочетании со стандартным sort (с использованием less<double> для достижения нисходящего порядка при повторной итерации вперед. Эквивалентно:

sort(values.rbegin(), values.rend(), less<double>());

Пример кода для превосходного nth_element решения, предложенного здесь @Kiril (K = 125000, N = 500000). Я хотел попробовать это, так что вот оно.

vector<double> values;

for (size_t i = 0; i < 500000; ++i)
{
    values.push_back(rand());
}

nth_element(values.begin(), values.begin()+375000, values.end());
sort(values.begin()+375000, values.end());

vector<double> results(values.rbegin(), values.rbegin() + values.size() - 375000);

Answer 5

ОК, как насчет этого?

bool isSmaller (std::pair<double, int> x, std::pair<double, int> y)
{
   return x.first< y.first;
}

int main()
{
   //...
   //you have your vector<double> here, say name is d;
   std::vector<std::pair<double, int> > newVec(d.size());
   for(int i = 0; i < newVec.size(); ++i)
   {
      newVec[i].first = d[i];
      newVec[i].second = i;  //store the initial index
   }
   std::sort(newVec.begin(), newVec.end(), &isSmaller);
   //now you can iterate through first k elements and the second components will be the initial indices
}

Answer 6

Не уверен насчет предварительно консервированных алгоритмов, но взгляните на алгоритмы выбора ;если вам нужны верхние элементы K из набора значений N, а N намного больше, чем K, есть гораздо более эффективные методы.

Если вы можете создать класс индексации (как ответ @ user470379 - в основномкласс, который инкапсулирует указатель / индекс в «реальные» данные, доступные только для чтения), затем использует очередь приоритетов максимального размера K и добавляет каждый несортированный элемент в очередь приоритетов, выталкивая самый нижний элемент при очередидостигает размера К + 1.В таких случаях, как N = 10 ⁶ , K = 100, это обрабатывает случаи гораздо проще и эффективнее, чем полная сортировка.