Zmiana kolejności wektora za pomocą wektora indeksów

Oto prawidłowy kod

void REORDER(vector<char>& vA, vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());

    // for all elements to put in place
    for( int i = 0; i < va.size() - 1; ++i )
    { 
        // while the element i is not yet in place 
        while( i != vOrder[i] )
        {
            // swap it with the element at its final place
            int alt = vOrder[i];
            swap( vA[i], vA[alt] );
            swap( vOrder[i], vOrder[alt] );
        }
    }
}

Zauważ, że możesz zapisać jeden test, ponieważ jeśli n-1 elementów jest na miejscu, ostatni N-Ten element jest na pewno na miejscu.

Przy wyjściu vA i vOrder są odpowiednio uporządkowane.

Algorytm ten wykonuje co najwyżej zamianę n-1, ponieważ każdy swap przenosi element do jego ostatecznej pozycji. I będziemy musieli zrobić co najwyżej 2N testy na vorderze.

Jeśli modyfikowanie tablicy Porządkowej jest w porządku, to implementacja sortująca wektor porządkowy i przy każdej operacji sortowania również zamienia odpowiednie elementy wektora wartości, może załatwić sprawę.

Wydaje mi się, że vOrder zawiera zbiór indeksów w żądanej kolejności (na przykład wynik sortowania według indeksów). Przykład kodu jest odmianą sortowania cyklicznego. Każda Zamiana umieszcza co najmniej jeden element we właściwym miejscu. Ten przykład kodu skutecznie zmienia kolejność vA zgodnie z vorderem, podczas gdy "unordering" lub "unpermuting" Vorder wraca do pierwotnego stanu (0 :: n-1). Jeśli vA zawierało wartości od 0 do n-1 w kolejności, to po zmianie kolejności VA kończyłoby się tam, gdzie vOrder zaczęło się.

template <class T>
void reorder(vector<T>& vA, vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());

    // for all elements to put in place
    for( size_t i = 0; i < vA.size(); ++i )
    { 
        // while vOrder[i] is not yet in place 
        // every swap places at least one element in it's proper place
        while(       vOrder[i] !=   vOrder[vOrder[i]] )
        {
            swap( vA[vOrder[i]], vA[vOrder[vOrder[i]]] );
            swap(    vOrder[i],     vOrder[vOrder[i]] );
        }
    }
}

Można to również zaimplementować nieco bardziej efektywnie za pomocą ruchów zamiast swapów. Obiekt tymczasowy jest potrzebny do trzymania elementu podczas ruchów. Przykładowy kod C, zmienia kolejność [] według indeksów w I [], sortuje również I []:

void reorder(int *A, int *I)
{    
int i, j, k;
int tA;
    /* reorder A according to I */
    /* every move puts an element into place */
    /* time complexity is O(n) */
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){
        if(i != I[i]){
            tA = A[i];
            j = i;
            while(i != (k = I[j])){
                A[j] = A[k];
                I[j] = j;
                j = k;
            }
            A[j] = tA;
            I[j] = j;
        }
    }
}

Nigdy przedwcześnie nie Optymalizuj. Meassure, a następnie określić, gdzie trzeba zoptymalizować i co. Możesz zakończyć złożonym kodem, który jest trudny do utrzymania i podatny na błędy w wielu miejscach, gdzie wydajność nie stanowi problemu.

    template <typename T>
    void reorder( std::vector<T> & data, std::vector<std::size_t> const & order )
    {
       std::vector<T> tmp;         // create an empty vector
       tmp.reserve( data.size() ); // ensure memory and avoid moves in the vector
       for ( std::size_t i = 0; i < order.size(); ++i ) {
          tmp.push_back( data[order[i]] );
       }
       data.swap( tmp );          // swap vector contents
    }

Ten kod tworzy i pusty (wystarczająco duży) wektor, w którym pojedyncza kopia jest wykonywana w kolejności. Na końcu wektory uporządkowane i oryginalne są zamienione. Spowoduje to zmniejszenie kopii, ale nadal wymaga dodatkowej pamięci.

Jeśli chcesz wykonać ruchy w miejscu, prostym algorytmem może być:

template <typename T>
void reorder( std::vector<T> & data, std::vector<std::size_t> const & order )
{
   for ( std::size_t i = 0; i < order.size(); ++i ) {
      std::size_t original = order[i];
      while ( i < original )  {
         original = order[original];
      }
      std::swap( data[i], data[original] );
   }
}

Ten kod powinien być sprawdzany i debugowany. W prostych słowach algorytm w każdym kroku pozycjonuje element na i-tej pozycji. Najpierw określamy, gdzie element pierwotny dla tej pozycji jest teraz umieszczony w wektorze danych. Jeśli oryginalna pozycja została już dotknięta przez algorytm (jest przed i-tą pozycją) następnie oryginalny element został zamieniony na pozycję order [original]. Z drugiej strony, ten element mógł już zostać przeniesiony...

Ten algorytm jest mniej więcej O (N^2) w liczbie operacji całkowitych, a zatem teoretycznie jest gorszy w czasie wykonania w porównaniu do początkowego algorytmu O(N). Ale może to zrekompensować, jeśli operacje wymiany N^2 (najgorszy przypadek) kosztują mniej niż operacje kopiowania N lub jeśli jesteś naprawdę ograniczony przez ślad pamięci.

Można by to zrobić rekurencyjnie, chyba-coś takiego (nie zaznaczone, ale daje pomysł):

// Recursive function
template<typename T>
void REORDER(int oldPosition, vector<T>& vA, 
             const vector<int>& vecNewOrder, vector<bool>& vecVisited)
{
    // Keep a record of the value currently in that position,
    // as well as the position we're moving it to.
    // But don't move it yet, or we'll overwrite whatever's at the next
    // position. Instead, we first move what's at the next position.
    // To guard against loops, we look at vecVisited, and set it to true
    // once we've visited a position.
    T oldVal = vA[oldPosition];
    int newPos = vecNewOrder[oldPosition];
    if (vecVisited[oldPosition])
    {
        // We've hit a loop. Set it and return.
        vA[newPosition] = oldVal;
        return;
    }
    // Guard against loops:
    vecVisited[oldPosition] = true;

    // Recursively re-order the next item in the sequence.
    REORDER(newPos, vA, vecNewOrder, vecVisited);

    // And, after we've set this new value, 
    vA[newPosition] = oldVal;
}

// The "main" function
template<typename T>
void REORDER(vector<T>& vA, const vector<int>& newOrder)
{
    // Initialise vecVisited with false values
    vector<bool> vecVisited(vA.size(), false);

    for (int x = 0; x < vA.size(); x++)
    {
        REORDER(x, vA, newOrder, vecVisited);
    }
}

Oczywiście, masz nad głową vecVisited. Myśli ktoś o tym podejściu?

Iteracją przez wektor jest operacja O (n). Ciężko to przebić.

Twój kod jest złamany. Nie można przypisać do vA i trzeba użyć parametrów szablonu.

vector<char> REORDER(const vector<char>& vA, const vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());  
    vector<char> vCopy(vA.size()); 
    for(int i = 0; i < vOrder.size(); ++i)  
        vCopy[i] = vA[ vOrder[i] ];  
    return vA;
} 

Powyższe jest nieco bardziej wydajne.

Nie jest jasne po tytule i pytaniu, czy wektor powinien być uporządkowany z tymi samymi krokami, jakie trzeba wykonać, aby uporządkować vOrder, czy też vOrder zawiera już indeksy pożądanej kolejności. Pierwsza interpretacja ma już satysfakcjonującą odpowiedź (patrz chmike i Potatoswatter), dodaję kilka przemyśleń na temat tej drugiej. Jeśli koszt tworzenia i / lub kopiowania obiektu T jest istotny

template <typename T>
void reorder( std::vector<T> & data, std::vector<std::size_t> & order )
{
 std::size_t i,j,k;
  for(i = 0; i < order.size() - 1; ++i) {
    j = order[i];
    if(j != i) {
      for(k = i + 1; order[k] != i; ++k);
      std::swap(order[i],order[k]);
      std::swap(data[i],data[j]);
    }
  }
}

Jeśli koszt tworzenia obiektu jest mały i pamięć nie jest problemem (zobacz "dribeas"): {]}

template <typename T>
void reorder( std::vector<T> & data, std::vector<std::size_t> const & order )
{
 std::vector<T> tmp;         // create an empty vector
 tmp.reserve( data.size() ); // ensure memory and avoid moves in the vector
 for ( std::size_t i = 0; i < order.size(); ++i ) {
  tmp.push_back( data[order[i]] );
 }
 data.swap( tmp );          // swap vector contents
}

Zauważ, że dwa fragmenty kodu w dribeas answer robią różne rzeczy.

Próbowałem użyć rozwiązania @ Potatoswatter do sortowania wielu wektorów przez trzeci i bardzo się pomyliłem przez wyjście z korzystania z powyższych funkcji na wektor indeksów wyjście z Armadillo sort_index. Aby przełączyć wyjście wektorowe z sort_index (wektor arma_inds poniżej) na wyjście, które może być użyte z rozwiązaniem @ Potatoswatter (new_inds poniżej), możesz wykonać następujące czynności:

vector<int> new_inds(arma_inds.size());
for (int i = 0; i < new_inds.size(); i++) new_inds[arma_inds[i]] = i;

To ciekawe ćwiczenie intelektualne, aby zrobić reorder z o (1) wymagania przestrzeni, ale w 99,9% przypadków prostsza odpowiedź wykona się do Twoich potrzeb:

void permute(vector<T>& values, const vector<size_t>& indices)  
{   
    vector<T> out;
    out.reserve(indices.size());
    for(size_t index: indices)
    {
        assert(0 <= index && index < values.size());
        out.push_back(values[index]);
    }
    values = std::move(out);
}

Poza wymaganiami pamięci, jedyny sposób, w jaki mogę myśleć o tym, że jest to wolniejsze, byłby spowodowany pamięcią out znajdującą się na innej stronie pamięci podręcznej niż values i indices.

Wymyśliłem rozwiązanie, które ma złożoność przestrzeni z O(max_val - min_val + 1), ale może być zintegrowane z std::sort i korzysta z std::sort'S O(n log n)przyzwoity złożoność czasu.

std::vector<int32_t> dense_vec = {1, 2, 3};
std::vector<int32_t> order = {1, 0, 2};

int32_t max_val = *std::max_element(dense_vec.begin(), dense_vec.end());
std::vector<int32_t> sparse_vec(max_val + 1);

int32_t i = 0;
for(int32_t j: dense_vec)
{
    sparse_vec[j] = order[i];
    i++;
}

std::sort(dense_vec.begin(), dense_vec.end(),
    [&sparse_vec](int32_t i1, int32_t i2) {return sparse_vec[i1] < sparse_vec[i2];});

Następujące założenia poczynione podczas pisania tego kodu:

• wartości wektorowe zaczynają się od zera.
• Wektor nie zawiera powtarzających się wartości.
• mamy wystarczająco dużo pamięci do poświęcenia, aby użyć std::sort

Powinno to unikać kopiowania wektora:

void REORDER(vector<char>& vA, const vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size()); 
    for(int i = 0; i < vOrder.size(); ++i)
        if (i < vOrder[i])
            swap(vA[i], vA[vOrder[i]]);
}