Подтвердить что ты не робот

Заменить вектор, используя вектор индексов

Я хотел бы изменить порядок элементов в векторе, используя другой вектор, чтобы указать порядок:

char   A[]     = { 'a', 'b', 'c' };
size_t ORDER[] = { 1, 0, 2 };

vector<char>   vA(A, A + sizeof(A) / sizeof(*A));
vector<size_t> vOrder(ORDER, ORDER + sizeof(ORDER) / sizeof(*ORDER));

reorder_naive(vA, vOrder);

// A is now { 'b', 'a', 'c' }

Ниже приведена неэффективная реализация, требующая копирования вектора:

void reorder_naive(vector<char>& vA, const vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());  
    vector vCopy = vA; // Can we avoid this?  
    for(int i = 0; i < vOrder.size(); ++i)  
        vA[i] = vCopy[ vOrder[i] ];  
}

Есть ли более эффективный способ, например, который использует swap()?

4b9b3361

ОТВЕТЫ

Ответ 1

Я улучшил алгоритм chmike. Эта функция согласуется с его для всех 11! перестановки (0..10), переданные как вектор переупорядочения. Также он не изменяет вектор переупорядочения.

template< class T >
void reorder(vector<T> &v, vector<size_t> const &order )  {   
    for ( int s = 1, d; s < order.size(); ++ s ) {
        for ( d = order[s]; d < s; d = order[d] ) ;
        if ( d == s ) while ( d = order[d], d != s ) swap( v[s], v[d] );
    }
}

Здесь версия стиля STL, в которую я приложил немного больше усилий. Это примерно на 47% быстрее (то есть почти в два раза быстрее (0,10)!), Потому что он делает все свопы как можно раньше, а затем возвращается. Вектор переупорядочения состоит из нескольких орбит, и каждая орбита переупорядочивается по достижении ее первого члена. Это быстрее, если последние несколько элементов не содержат орбиты.

template< typename order_iterator, typename value_iterator >
void reorder( order_iterator order_begin, order_iterator order_end, value_iterator v )  {   
    typedef typename iterator_traits< value_iterator >::value_type value_t;
    typedef typename iterator_traits< order_iterator >::value_type index_t;
    typedef typename iterator_traits< order_iterator >::difference_type diff_t;

    diff_t remaining = order_end - 1 - order_begin;
    for ( index_t s = index_t(), d; remaining > 0; ++ s ) {
        for ( d = order_begin[s]; d > s; d = order_begin[d] ) ;
        if ( d == s ) {
            -- remaining;
            value_t temp = v[s];
            while ( d = order_begin[d], d != s ) {
                swap( temp, v[d] );
                -- remaining;
            }
            v[s] = temp;
        }
    }
}

И, наконец, просто чтобы ответить на вопрос раз и навсегда, вариант, который уничтожает вектор переупорядочения. (Он заполняет -1.) Это примерно на 16% быстрее, чем предыдущая версия. Этот использует уродливый тип, но справляйтесь с ним. Это охватывает 11! ~ = 40 мил перестановки 11 символов за 4,25 секунды, не считая накладных расходов, на моем 2,2 ГГц ноутбуке.

template< typename order_iterator, typename value_iterator >
void reorder_destructive( order_iterator order_begin, order_iterator order_end, value_iterator v )  {
    typedef typename iterator_traits< value_iterator >::value_type value_t;
    typedef typename iterator_traits< order_iterator >::value_type index_t;
    typedef typename iterator_traits< order_iterator >::difference_type diff_t;

    diff_t remaining = order_end - 1 - order_begin;
    for ( index_t s = index_t(); remaining > 0; ++ s ) {
        index_t d = order_begin[s];
        if ( d == (diff_t) -1 ) continue;
        -- remaining;
        value_t temp = v[s];
        for ( index_t d2; d != s; d = d2 ) {
            swap( temp, v[d] );
            swap( order_begin[d], d2 = (diff_t) -1 );
            -- remaining;
        }
        v[s] = temp;
    }
}

Ответ 2

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

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.

Ответ 3

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

Ответ 4

Мне кажется, что vOrder содержит набор индексов в нужном порядке (например, вывод сортировки по индексу). Пример кода здесь следует за "циклами" в vOrder, где после поднабора (может быть все из vOrder) индексов будет циклически проходить через подмножество, заканчиваясь обратно первым индексом подмножества.

Вики статья о "циклах"

https://en.wikipedia.org/wiki/Cyclic_permutation

В следующем примере каждый своп помещает в свое место хотя бы один элемент. Этот пример кода эффективно переупорядочивает vA в соответствии с vOrder, при этом "разупорядочивая" или "не переставляя" vOrder обратно в исходное состояние (0 :: n-1). Если vA содержал значения от 0 до n-1 по порядку, то после переупорядочения vA заканчивал бы там, где начинался vOrder.

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 proper place
        while(       vOrder[i] !=   vOrder[vOrder[i]] )
        {
            swap( vA[vOrder[i]], vA[vOrder[vOrder[i]]] );
            swap(    vOrder[i],     vOrder[vOrder[i]] );
        }
    }
}

Это также может быть реализовано более эффективно, используя ходы вместо свопов. Временный объект необходим для удержания элемента во время ходов. Пример кода C, переупорядочивает A [] в соответствии с индексами в я [], также сортирует я []:

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

Ответ 5

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

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

    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 операций копирования или если вы действительно ограничены положением памяти.

Ответ 6

Вы можете сделать это рекурсивно, я думаю - что-то вроде этого (непроверено, но это дает идею):

// 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 at the next
    // position. Instead, we first move what 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);
    }
}

Конечно, у вас есть накладные расходы vecVisited. Мысли о таком подходе, кто-нибудь?

Ответ 7

Ваш код не работает. Вы не можете назначить 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;
}

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

Ответ 8

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

Ответ 9

Непонятно название и вопрос, следует ли упорядочить вектор с теми же шагами, которые требуется для заказа vOrder, или если vOrder уже содержит индексы нужного порядка. Первая интерпретация уже удовлетворительного ответа (см. Chmike и Potatoswatter), я добавляю некоторые мысли о последнем. Если ценность создания и/или копирования объекта T релевантна

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

Если стоимость создания вашего объекта мала, и память не вызывает беспокойства (см. 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
}

Обратите внимание, что две части кода в dribeas отвечают на разные вещи.

Ответ 10

Я пытался использовать решение @Potatoswatter для сортировки нескольких векторов третьей и очень запутался в результате использования вышеуказанных функций в векторе индексов, выводимых из Armadillo sort_index. Чтобы переключиться с векторного вывода из sort_index (ниже arma_inds vector) на тот, который может использоваться с решением @Potatoswatter (new_inds ниже), вы можете сделать следующее:

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

Ответ 11

Это интересное интеллектуальное упражнение для изменения порядка с O (1) пространством, но в 99,9% случаев более простой ответ будет отвечать вашим потребностям:

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

Помимо требований к памяти, единственный способ, которым я могу думать о том, что это медленнее, будет связано с тем, что память out находится на другой странице кеша, чем в values и indices.

Ответ 12

Я придумал это решение, которое имеет пространственную сложность O(max_val - min_val + 1), но оно может быть интегрировано с std::sort и имеет преимущество от std::sort O(n log n) приличной сложности времени.

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

Следующие предположения сделаны при написании этого кода:

  • Векторные значения начинаются с нуля.
  • Вектор не содержит повторяющихся значений.
  • У нас достаточно памяти, чтобы пожертвовать, чтобы использовать std::sort

Ответ 13

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

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