C++ Równoległe std :: Sortowanie wektorowe z kosztownym kopiowaniem

Question

Załóżmy, że mam vector<int>intVec i vector<vector<double> >matrix. Chcę sortować intVec i zmienić odpowiednio pierwszy wymiar matrix w C++. Zdaję sobie sprawę, że to pytanie było już zadawane kilka razy wcześniej, ale ta sprawa ma pewien skręt. A vector<double> jest drogi do skopiowania, np. kopiowanie zarówno intVec, jak i kopiowanie ich z powrotem jest jeszcze bardziej nieefektywne niż zwykle.

Krótki toczenia mój własny niestandardowy algorytm sortowania, w jaki sposób mogę zmienić kolejność sortowania intVec i pierwszy wymiar matrix w lockstep bez kopiowania jakiegokolwiek elementu matrix i powołując vector „s kopia konstruktora?

Answer 1

A vector<double> jest drogi do skopiowania, np. kopiowanie macierzy intVec i do vector<pair<int, vector<double> >, sortowanie i kopiowanie ich z powrotem jest jeszcze bardziej nieefektywne niż zwykle.

Najprostszym sposobem, aby uzyskać optymalizację chcesz potem jest swapu elementami źródła vector<vector<double>> do tymczasowego vector<pair<int, vector<double>>, sortować je, a następnie wymiany je z powrotem do swoich nowych lokalizacjach w oryginalnego wektora .

Nadal będzie więcej narzutów niż jest to absolutnie konieczne (na przykład do konstruowania i niszczenia pustych wektorów). Jednak żaden wektor nie jest nigdy kopiowany, a kod pozostaje bardzo podobny do tego, co już masz. Więc jeśli masz rację, problem polega na kosztach kopiowania, problem został rozwiązany.

W C++ 11 można poruszać się w obu kierunkach, a nie zamieniać. Wątpię, by różnica między wydajnością a przenoszeniem z pustym wektorem była duża, ale nie jestem pewna, czy tak nie jest.

Answer 2

Jeśli nie chcesz skopiować wektora pozycji vector<double>, zrób wektor wskaźnika lub wskaźników do elementów vector<double>. Posortuj go wraz z głównym wektorem.

To jednak wcale oczywiste, że dostaniesz wzrost wydajności, a więc sugeruję miarą zarówno proste sortowanie i inteligentne sortowanie i porównania.

---

Przykład:

#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

oparciu o przestrzeń pomiędzy swoimi dwoma > „s, zgaduję używasz pre-C++ 11 C++. W C++ 11, std::sort wydaje się przenosić elementy, gdy tylko jest to możliwe, zamiast kopiować.

Możesz przesłać niestandardowy komparator do std::sort. Jednak nawet jeśli to zrobisz, robisz Theta (n log n) kopie pair<int, vector<double> >.

Przypuszczam, na podstawie faktycznie nie próbując go, że należy posortować pair<int, vector<double> *> (lub pair<int, int> jeśli int jest wystarczająco duży), przy drugim int jako wskaźnik) zamiast dostać odpowiednią permutacji, a następnie zastosować permutacja przy użyciu funkcji składowej vector, aby uniknąć kopiowania zawartości wektorowej.

Answer 4

Jedna opcja: utwórz std::vector<std::pair<int,size_t>>, gdzie pierwszym elementem jest int intVec, a drugi element jest oryginalnym indeksem tego elementu. Następnie posortuj ten nowy wektor. Następnie przetasuj swoją matrycę i intVec do kolejności wskazanej przez drugie elementy pary (np. Jednym ruchem, wykonując wymiany).

Answer 5

Oczywistą odpowiedzią jest zrestrukturyzowanie twoich dwóch wektorów jako jeden vector<pair<int, vector<double> > (ponieważ dane są wyraźnie ciasno sprzężone).

Jeśli to naprawdę nie jest opcja, utwórz kolejny wektor indeksów i posortuj go zamiast vec i matrix.

Answer 6

Od std::vector::swap działa w stałym czasie, można użyć algorytmu sortowania, który działa poprzez serię swapy (takie jak quicksort) do sortowania intVec jednocześnie wykonując identyczne swapy na 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

jestem ładna pewność, że --- gdy używasz jakiegoś aktualnego kompilatora (powiedzmy gcc 4.4 i wyższego) --- nic tak naprawdę nie jest kopiowane: obecnie obiekty w standardowych kontenerach C++ są (przeważnie) zawsze przenoszone. Dlatego też IMHO nie trzeba obawiać się kosztownych kopii.

Spójrz na poniższy przykład - został napisany przy użyciu gcc 4.4.6 w Debianie. Jak widać, podczas fazy "zmiany kolejności" nie ma żadnego wywołania konstruktora kopiowania, a także żadnego wywołania operatora `operator = (... & inne) '.

#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; 
} 

wyjściowa:

[    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]