使用索引向量重新排序向量

Question

我想重新排序向量中的项目,使用另一个向量来指定顺序:

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()？

Answer 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个!在我的2.2 GHz笔记本电脑上,在4.25秒内完成了11个字符的40密耳排列,不计算开销.

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

Answer 2

在我看来，vOrder 包含一组按所需顺序排列的索引（例如按索引排序的输出）。此处的代码示例遵循 vOrder 中的“循环”，其中遵循索引的子集（可能是 vOrder 的所有）将循环遍历子集，并在子集的第一个索引处结束。

关于“循环”的维基文章

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

在以下示例中，每次交换至少将一个元素放置在适当的位置。此代码示例根据 vOrder 有效地重新排序 vA，同时“取消排序”或“取消排列” 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's proper place
        while(       vOrder[i] !=   vOrder[vOrder[i]] )
        {
            swap( vA[vOrder[i]], vA[vOrder[vOrder[i]]] );
            swap(    vOrder[i],     vOrder[vOrder[i]] );
        }
    }
}

这也可以使用移动而不是交换来更有效地实现。在移动过程中需要一个临时对象来保存元素。示例 C 代码，根据 I[] 中的索引对 A[] 重新排序，也对 I[] 进行排序：

void reorder(int *A, int *I, int n)
{    
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 < n; 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;
        }
    }
}

Answer 3

这是正确的代码

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次交换，因为每次交换都会将元素移到其最终位置。而且，我们最多必须在vOrder上进行2N次测试。