Вектор переупорядочивания использование вектора индексов

Вот правильный код

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] );
        }
    }
}

. Обратите внимание, что вы можете сохранить один тест, потому что, если n-1 элементов на месте, последний n-й элемент наверняка на месте.

На выходе vA и vOrder правильно упорядочены.

Этот алгоритм выполняет самое большее n-1 обмен, потому что каждый обмен перемещает элемент в его окончательное положение. И нам нужно будет сделать не более 2N тестов на vOrder.

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

С учетом вышесказанного не пессимизируйте досрочно. Без изменения кода вы можете удалить половину своих копий:

    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
    }

Этот код создает и пустой (достаточно большой) вектор, в котором одна копия выполняется по порядку. В конце упорядоченные и оригинальные векторы меняются местами. Это уменьшит количество копий, но все равно потребует дополнительной памяти.

Если вы хотите выполнить перемещения на месте, простой алгоритм может быть следующим:

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] );
   }
}

Этот код должен быть проверен и отлажен. Проще говоря, алгоритм на каждом шаге размещает элемент в i-й позиции. Сначала мы определяем, где оригинальный элемент для этой позиции теперь размещен в векторе данных. Если исходная позиция уже была затронута алгоритмом (она находится перед i-й позицией), то исходный элемент менялся местами в порядке [оригинальная] позиция. Опять же, этот элемент уже может быть перемещен ...

Этот алгоритм примерно равен O (N ^ 2) по числу целочисленных операций и, следовательно, теоретически хуже по времени выполнения по сравнению с исходным алгоритмом O (N). , Но это может компенсировать, если операции подкачки N ^ 2 (в худшем случае) стоят меньше, чем операции копирования N или если вы действительно ограничены объемом памяти.

Этот алгоритм примерно равен O (N ^ 2) по числу целочисленных операций и, следовательно, теоретически хуже по времени выполнения по сравнению с исходным алгоритмом O (N). Но это может компенсировать, если операции подкачки N ^ 2 (в худшем случае) стоят меньше, чем операции копирования N или если вы действительно ограничены объемом памяти.

Этот алгоритм примерно равен O (N ^ 2) по числу целочисленных операций и, следовательно, теоретически хуже по времени выполнения по сравнению с исходным алгоритмом O (N). Но это может компенсировать, если операции подкачки N ^ 2 (в худшем случае) стоят меньше, чем операции копирования N или если вы действительно ограничены объемом памяти.

Для итерации по вектору используется O (n) операция. Это своего рода трудно победить.

Следует избегать копирования вектора:

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]]);
}

Ваш код взломан. Вы не можете назначить vA , и вам нужно использовать параметры шаблона.

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

Вышеуказанное немного более эффективно.

Если можно изменить массив ORDER, то реализация, которая сортирует вектор ORDER и при каждой операции сортировки также меняет местами соответствующие элементы вектора значений, я думаю.

You could do it recursively, I guess - something like this (unchecked, but it gives the idea):

// 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);
    }
}

Of course, you do have the overhead of vecVisited. Thoughts on this approach, anyone?