C++ Parallel std :: vector Sorting With Expensive Copying

Question

Suppongo di avere un vector<int>intVec e uno vector<vector<double> >matrix. Voglio ordinare intVec e riordinare la prima dimensione di matrix corrispondentemente in C++. Mi rendo conto che questa domanda è stata posta diverse volte prima, ma questo caso ha una svolta. Un vector<double> è costoso da copiare, quindi ad es. copiare sia intVec sia matrix in un vector<pair<int, vector<double> >, ordinarlo e copiarli è ancora più inefficiente del solito.

A corto di rotazione mia algoritmo di ordinamento personalizzato, come posso sorta intVec e riordinare la prima dimensione di matrix in sincronia senza copiare alcun elemento di matrix e invocando vector 's copiare costruttore?

Answer 1

A vector<double> è costoso da copiare, quindi ad es. copiare sia intVec che la matrice in un vector<pair<int, vector<double> >, l'ordinamento e copiarli è ancora più inefficiente del solito.

Il modo più semplice per ottenere l'ottimizzazione che si desidera è quindi di di swap gli elementi della sorgente vector<vector<double>> nel temporanea vector<pair<int, vector<double>>, ordinare, e poi di swap di nuovo al loro nuove posizioni nel vettore originale .

Ci sarà ancora un sovraccarico superiore a quello strettamente necessario (ad esempio per costruire e distruggere i vettori vuoti). Tuttavia, nessun vettore viene mai copiato e il codice rimane molto simile a quello che hai già. Quindi se hai ragione sul fatto che il problema è il costo della copia, il problema è risolto.

In C++ 11 è possibile spostarsi in entrambe le direzioni anziché scambiare. Dubito che ci sia molta differenza di prestazioni tra lo spostamento e lo scambio con un vettore vuoto, ma non sono sicuro che non ci sia.

Answer 2

Se non si desidera copiare il vettore articolo vector<double>, quindi creare un vettore di puntatore o indici negli elementi vector<double>. Ordinalo insieme al vettore principale.

Tuttavia non è affatto chiaro che otterrai un guadagno in termini di prestazioni, quindi ti suggerisco di misurare sia l'ordinamento diretto che l'ordinamento intelligente e confrontare.

---

Esempio:

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

struct Mat 
{ 
    vector< vector<double> > items; 

    Mat(int const size) 
     : items(size, vector<double>(size)) 
    {} 
}; 

struct KeyAndData 
{ 
    int      key; 
    vector<double> const* data; 

    friend bool operator<(KeyAndData const& a, KeyAndData const& b) 
    { 
     return a.key < b.key; 
    } 
}; 

int main() 
{ 
    int const  data[] = {3, 1, 4, 1, 5}; 
    Mat    m(5); 
    vector<int>  v(5); 

    for(int i = 0; i < 5; ++i) 
    { 
     m.items[i][i] = v[i] = data[i]; 
    } 

    vector<KeyAndData>  sorted(5); 
    for(int i = 0; i < 5; ++i) 
    { 
     sorted[i].key = v[i]; 
     sorted[i].data = &m.items[i]; 
    } 

    sort(sorted.begin(), sorted.end()); 
    for(int i = 0; i < 5; ++i) 
    { 
     cout << sorted[i].key << ": "; 

     vector<double> const& r = *sorted[i].data; 
     for(int x = 0; x < 5; ++x) 
     { 
      cout << r[x] << " "; 
     } 
     cout << endl; 
    } 
} 

Answer 3

in base allo spazio tra le due > s', sto cercando di indovinare che si sta utilizzando pre-C++ 11 C++. In C++ 11, std::sort sembra spostare elementi quando possibile invece di copiare.

È possibile passare un comparatore personalizzato a std::sort. Tuttavia, anche se lo fai, stai facendo copie Theta (n log n) di pair<int, vector<double> >.

direi, sulla base di non averla provata, che si dovrebbe ordinare un pair<int, vector<double> *> (o pair<int, int> se int è abbastanza grande), utilizzando la seconda int come un indice), invece per ottenere la permutazione appropriato e quindi applicare la permutazione usando la funzione membro swap di vector per evitare di copiare il contenuto vettoriale.

Answer 4

Un'opzione: creare un std::vector<std::pair<int,size_t>> dove il primo elemento è l'int da intVec e il secondo elemento è l'indice originale di quell'elemento. Quindi ordina quel nuovo vettore. Quindi mischiate la vostra matrice e intVec all'ordine indicato dai secondi elementi delle coppie (ad esempio, con un singolo passaggio, facendo scambi).

Answer 5

La risposta ovvia è ristrutturare i due vettori come uno vector<pair<int, vector<double> > (poiché i dati sono chiaramente accoppiati in modo fisso).

Se questa non è davvero un'opzione, creare un altro vettore di indici e ordinarli al posto del vec e della matrice.

Answer 6

Dal std::vector::swap opera in tempo costante, è possibile utilizzare un algoritmo di ordinamento che opera attraverso una serie di swap (come quicksort) per ordinare intVec eseguendo contemporaneamente swap identici su matrix:

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

// Sorts intVec in [low, high) while also performing identical swaps on matrix. 
void iqsort(std::vector<int> &intVec, std::vector<std::vector<double>> &matrix, 
      int low, int high) { 
    if (low >= high) return; 
    int pivot = intVec[low]; 
    int nLow = low + 1; 
    int nHigh = high - 1; 
    while (nLow <= nHigh) { 
    if (intVec[nLow] <= pivot) { 
     ++nLow; 
    } else { 
     std::swap(intVec[nLow], intVec[nHigh]); 
     std::swap(matrix[nLow], matrix[nHigh]); 
     --nHigh; 
    } 
    } 
    std::swap(intVec[low], intVec[nHigh]); 
    std::swap(matrix[low], matrix[nHigh]); 

    iqsort(intVec, matrix, low, nHigh); 
    iqsort(intVec, matrix, nLow, high); 
} 

int main() { 
    std::vector<int> intVec = {10, 1, 5}; 
    std::vector<std::vector<double>> matrix = {{33.0}, {11.0}, {44.0}}; 
    iqsort(intVec, matrix, 0, intVec.size()); 
    // intVec is {1, 5, 10} and matrix is {{11.0}, {44.0}, {33.0}} 
} 

Answer 7

Sono abbastanza certo che --- quando usi un compilatore aggiornato (diciamo gcc 4.4 e versioni successive) --- non c'è nulla di veramente copiato: oggigiorno gli oggetti all'interno dei contenitori di libreria standard C++ sono (per lo più) sempre spostati. Quindi IMHO non è necessario avere paura delle copie costose.

Dai un'occhiata al seguente esempio: è stato scritto usando gcc 4.4.6 in Debian. Come potete vedere, durante la fase di "riordino", non vi è alcuna chiamata al costruttore di copie e anche nessuna chiamata all'operatore = (... & altro).

#include <vector> 
#include <iostream> 
#include <iomanip> 

class VeryExpensiveToCopy { 
public: 
    explicit VeryExpensiveToCopy(long i) : id(i) { ++cnt_normal_cstr; } 

    // Just to be sure this is never used. 
    VeryExpensiveToCopy & operator=(VeryExpensiveToCopy & other) = delete; 
    VeryExpensiveToCopy(VeryExpensiveToCopy & other) = delete; 

    VeryExpensiveToCopy(VeryExpensiveToCopy && other) : id(other.id) { 
     ++cnt_move_cstr; 
    } 
    VeryExpensiveToCopy & operator=(VeryExpensiveToCopy && other) { 
     id = other.id; ++cnt_op_as_move; return *this; 
    } 

    long get_id() const { return id; } 

    static void print_stats(std::string const & lref) { 
     std::cout << "[" << std::setw(20) << lref << "] Normal Cstr [" 
       << cnt_normal_cstr 
       << "] Move Cstr [" << cnt_move_cstr 
       << "] operator=(&&) [" << cnt_op_as_move << "]" << std::endl; 
    } 

private: 
    long id; 

    static long cnt_normal_cstr; 
    static long cnt_move_cstr; 
    static long cnt_op_as_move; 
}; 

// Counts the number of calls. 
long VeryExpensiveToCopy::cnt_normal_cstr { 0 }; 
long VeryExpensiveToCopy::cnt_move_cstr { 0 }; 
long VeryExpensiveToCopy::cnt_op_as_move { 0 }; 

int main() { 
    std::vector<VeryExpensiveToCopy> v; 

    VeryExpensiveToCopy::print_stats("Start"); 
    for(auto i(0); i<100000; ++i) { 
     v.emplace_back(i); 
    } 
    VeryExpensiveToCopy::print_stats("After initialization"); 
    for(auto i(0); i<100000-1; ++i) { 
     v[i] = std::move(v[i+1]); 
    } 
    VeryExpensiveToCopy::print_stats("After moving"); 
    for(auto i(0); i<100000-1; ++i) { 
     if(v[i].get_id() != i+1) { abort(); } 
    } 
    VeryExpensiveToCopy::print_stats("After check"); 

    return 0; 
} 

uscita:

[    Start] Normal Cstr [0] Move Cstr [0] operator=(&&) [0] 
[After initialization] Normal Cstr [100000] Move Cstr [131071] operator=(&&) [0] 
[  After moving] Normal Cstr [100000] Move Cstr [131071] operator=(&&) [99999] 
[   After check] Normal Cstr [100000] Move Cstr [131071] operator=(&&) [99999]