indici dei k più grandi elementi in una lunghezza non ordinata n array

Question

Ho bisogno di trovare gli indici dei k più grandi elementi di una lunghezza non ordinata n, matrice/vettore in C++, con k < n. Ho visto come usare nth_element() per trovare la statistica k-th, ma non sono sicuro che l'uso di questo sia la scelta giusta per il mio problema in quanto sembra che avrei bisogno di effettuare k chiamate a nth_statistic, che immagino avrebbe complessità O (kn), che può essere buono come si può ottenere? O c'è un modo per farlo solo in O (n)?

L'implementazione senza nth_element() sembra che dovrò iterare su tutto l'array una volta, compilando un elenco di indici degli elementi più grandi ad ogni passaggio.

C'è qualcosa nella libreria standard C++ che rende questo un one-liner o un modo intelligente per implementarlo da solo in un paio di righe? Nel mio caso particolare, k = 3 e n = 6, quindi l'efficienza non è un problema enorme, ma sarebbe bello trovare un modo pulito ed efficiente per fare questo per k e n arbitrari.

Sembra che Mark the top N elements of an unsorted array sia probabilmente il post più vicino che riesco a trovare su SO, i post presenti in Python e PHP.

Answer 1

È possibile utilizzare la base dell'algoritmo quicksort per fare ciò che è necessario, ma invece di riordinare le partizioni, è possibile eliminare le voci che escono dall'intervallo desiderato.

E 'stato denominato "Selezione rapida" e here is a C++ implementation:

int partition(int* input, int p, int r) 
{ 
    int pivot = input[r]; 

    while (p < r) 
    { 
     while (input[p] < pivot) 
      p++; 

     while (input[r] > pivot) 
      r--; 

     if (input[p] == input[r]) 
      p++; 
     else if (p < r) { 
      int tmp = input[p]; 
      input[p] = input[r]; 
      input[r] = tmp; 
     } 
    } 

    return r; 
} 

int quick_select(int* input, int p, int r, int k) 
{ 
    if (p == r) return input[p]; 
    int j = partition(input, p, r); 
    int length = j - p + 1; 
    if (length == k) return input[j]; 
    else if (k < length) return quick_select(input, p, j - 1, k); 
    else return quick_select(input, j + 1, r, k - length); 
} 

int main() 
{ 
    int A1[] = { 100, 400, 300, 500, 200 }; 
    cout << "1st order element " << quick_select(A1, 0, 4, 1) << endl; 
    int A2[] = { 100, 400, 300, 500, 200 }; 
    cout << "2nd order element " << quick_select(A2, 0, 4, 2) << endl; 
    int A3[] = { 100, 400, 300, 500, 200 }; 
    cout << "3rd order element " << quick_select(A3, 0, 4, 3) << endl; 
    int A4[] = { 100, 400, 300, 500, 200 }; 
    cout << "4th order element " << quick_select(A4, 0, 4, 4) << endl; 
    int A5[] = { 100, 400, 300, 500, 200 }; 
    cout << "5th order element " << quick_select(A5, 0, 4, 5) << endl; 
} 

USCITA:

1st order element 100 
2nd order element 200 
3rd order element 300 
4th order element 400 
5th order element 500 

EDIT

Questo particolare implementazione ha un O (n) tempo medio di esecuzione; a causa del metodo di selezione di pivot, condivide il tempo di esecuzione nel caso peggiore di quicksort. Con optimizing the pivot choice, anche il tuo caso peggiore diventa O (n).

Answer 2

La libreria standard non otterrà un elenco di indici (è stato progettato per evitare il passaggio di dati ridondanti). Tuttavia, se siete interessati a n elementi più grandi, utilizzare un qualche tipo di partizionamento (sia std::partition e std::nth_element sono O (n)):

#include <iostream> 
#include <algorithm> 
#include <vector> 

struct Pred { 
    Pred(int nth) : nth(nth) {}; 
    bool operator()(int k) { return k >= nth; } 
    int nth; 
}; 

int main() { 

    int n = 4; 
    std::vector<int> v = {5, 12, 27, 9, 4, 7, 2, 1, 8, 13, 1}; 

    // Moves the nth element to the nth from the end position. 
    std::nth_element(v.begin(), v.end() - n, v.end()); 

    // Reorders the range, so that the first n elements would be >= nth. 
    std::partition(v.begin(), v.end(), Pred(*(v.end() - n))); 

    for (auto it = v.begin(); it != v.end(); ++it) 
     std::cout << *it << " "; 
    std::cout << "\n"; 

    return 0; 
} 

Answer 3

Ecco la mia implementazione che fa quello che voglio e penso sia ragionevolmente efficiente:

#include <queue> 
#include <vector> 
// maxindices.cc 
// compile with: 
// g++ -std=c++11 maxindices.cc -o maxindices 
int main() 
{ 
    std::vector<double> test = {0.2, 1.0, 0.01, 3.0, 0.002, -1.0, -20}; 
    std::priority_queue<std::pair<double, int>> q; 
    for (int i = 0; i < test.size(); ++i) { 
    q.push(std::pair<double, int>(test[i], i)); 
    } 
    int k = 3; // number of indices we need 
    for (int i = 0; i < k; ++i) { 
    int ki = q.top().second; 
    std::cout << "index[" << i << "] = " << ki << std::endl; 
    q.pop(); 
    } 
} 

che fornisce in uscita:

index[0] = 3 
index[1] = 1 
index[2] = 0 

Answer 4

la domanda ha la risposta parziale; ovvero std::nth_element restituisce "la statistica n-esima" con una proprietà che nessuno degli elementi che precedono l'uno è maggiore di quello e nessuno degli elementi che lo seguono è inferiore a.

Pertanto, è sufficiente una chiamata a std::nth_element per ottenere gli elementi k più grandi. La complessità temporale sarà O (n) che è teoricamente la più piccola dal momento che devi visitare ogni elemento almeno una volta per trovare gli elementi più piccoli (o in questo caso k-più piccoli). Se hai bisogno di questi k elementi da ordinare, devi ordinarli che saranno O (k log (k)). Quindi, in totale O (n + k log (k)).

Answer 5

Questo dovrebbe essere una versione migliorata del @hazelnusse che viene eseguita in O(nlogk) anziché O(nlogn)

#include <queue> 
#include <iostream> 
#include <vector> 
// maxindices.cc 
// compile with: 
// g++ -std=c++11 maxindices.cc -o maxindices 
int main() 
{ 
    std::vector<double> test = {2, 8, 7, 5, 9, 3, 6, 1, 10, 4}; 
    std::priority_queue< std::pair<double, int>, std::vector< std::pair<double, int> >, std::greater <std::pair<double, int> > > q; 
    int k = 5; // number of indices we need 
    for (int i = 0; i < test.size(); ++i) { 
    if(q.size()<k) 
     q.push(std::pair<double, int>(test[i], i)); 
    else if(q.top().first < test[i]){ 
     q.pop(); 
     q.push(std::pair<double, int>(test[i], i)); 
    } 
    } 
    k = q.size(); 
    std::vector<int> res(k); 
    for (int i = 0; i < k; ++i) { 
    res[k - i - 1] = q.top().second; 
    q.pop(); 
    } 
    for (int i = 0; i < k; ++i) { 
    std::cout<< res[i] <<std::endl; 
    } 
} 

Answer 6

È possibile farlo in O(n) tempo con un singolo calcolo statistico dell'ordine:

• Sia r essere la statistica k ordine -esimo
• inizializzazione due liste vuote bigger e equal.
• Per ogni indice i:
  • Se array[i] > r, aggiungere i-bigger
  • Se array[i] = r, aggiungere i a equal
• elementi Elimina Da equal fino a quando la somma delle lunghezze delle due liste è k
• Restituisce la concatenazione delle due liste.

Naturalmente, è necessario un solo elenco se tutti gli elementi sono distinti. E se necessario, potresti fare trucchi per combinare le due liste in una sola, anche se ciò renderebbe il codice più complicato.

Answer 7

Anche se il codice seguente potrebbe non soddisfare i vincoli di complessità desiderati, potrebbe essere un'alternativa interessante per la coda di priorità menzionata in precedenza.

#include <queue> 
#include <vector> 
#include <iostream> 
#include <iterator> 
#include <algorithm> 

std::vector<int> largestIndices(const std::vector<double>& values, int k) { 
    std::vector<int> ret; 

    std::vector<std::pair<double, int>> q; 
    int index = -1; 
    std::transform(values.begin(), values.end(), std::back_inserter(q), [&](double val) {return std::make_pair(val, ++index); }); 
    auto functor = [](const std::pair<double, int>& a, const std::pair<double, int>& b) { return b.first > a.first; }; 
    std::make_heap(q.begin(), q.end(), functor); 
    for (auto i = 0; i < k && i<values.size(); i++) { 
     std::pop_heap(q.begin(), q.end(), functor); 
     ret.push_back(q.back().second); 
     q.pop_back(); 
    } 

    return ret; 
} 

int main() 
{ 
    std::vector<double> values = { 7,6,3,4,5,2,1,0 }; 
    auto ret=largestIndices(values, 4); 
    std::copy(ret.begin(), ret.end(), std::ostream_iterator<int>(std::cout, "\n")); 
}