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

一尘不染

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

algorithm

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

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（）？

阅读 276

2020-07-28

共1个答案

一尘不染

该算法基于chmike，但是重排序索引的向量为const。此功能与他所有11个功能相同！[0..10]的排列。的复杂度为O（N ^
2），以N作为该输入的大小，或更精确地，最大的尺寸的轨道。

有关修改输入的优化O（N）解决方案，请参见下文。

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 std::iterator_traits< value_iterator >::value_type value_t;
    typedef typename std::iterator_traits< order_iterator >::value_type index_t;
    typedef typename std::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填充）。对于[0..10]的排列，它比以前的版本快16％。因为覆盖输入可以进行动态编程，所以它是O（N），对于序列较长的某些情况，渐近速度更快。

template< typename order_iterator, typename value_iterator >
void reorder_destructive( order_iterator order_begin, order_iterator order_end, value_iterator v )  {
    typedef typename std::iterator_traits< value_iterator >::value_type value_t;
    typedef typename std::iterator_traits< order_iterator >::value_type index_t;
    typedef typename std::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;
    }
}

2020-07-28