3

我正在尝试使用空缺跟踪算法在 C++ 中执行多维数组的转置。数组以 void 指针的形式出现，因此我使用地址操作来执行副本。

基本上，有一种算法从偏移量开始，并像瑞士奶酪一样遍历数组的整个一维表示，剔除其他偏移量，直到它恢复到原始偏移量。然后，您必须从下一个未触及的偏移量开始，然后再做一次。你重复直到所有的偏移都被触及。

现在，我正在使用 std::set 来填充所有可能的偏移量（0 到数组维度的乘法折叠）。然后，当我通过算法时，我从集合中删除。我认为这将是最快的，因为我需要随机访问树/集中的偏移量并删除它们。然后我需要快速找到下一个未触及/未删除的偏移量。

首先，填充集合非常缓慢，似乎必须有更好的方法。它为每个插入单独调用 new[] 。因此，如果我有 500 万个偏移量，就会有 500 万个新闻，再加上不断地重新平衡树，如您所知，这对于预先排序的列表来说并不快。

其次，删除也很慢。

第三，假设像 int 和 float 这样的 4 字节数据类型，我实际上使用了与数组本身相同数量的内存来存储这个未触及的偏移量列表。

第四，确定是否有任何未触及的偏移量并快速获得其中一个——这是一件好事。

有人对这些问题有任何建议吗？

4

3 回答 3

1

没看过那篇论文，

  • set::insert如果您将set在下一个之前访问，可能是添加数据的最有效方式insert
  • 另一方面，如果您一次构建所有集合，则最好使用vectorand sort。
  • 如果您在向量元素上添加一个指向下一个的指针，那么从已排序的向量中删除是很容易的。
    • 初始化next = NULL. 如果next == NULL，元素是有效的（没有被删除）。
    • 要删除，请设置next = this+1.
    • 接下来，遍历向量元素 fromthis+1到第一个元素 where iter->next != iter+1。然后if ( iter->next == NULL ) return iter; else return iter->next;
    • 更新(this+1)->next = iter (or) iter->next前return实现摊销常数时间。
    • 在最后添加一个保护元素next == this。这，不是vector::end，标志着序列的结束。

这是初稿，我把它编码了。未测试；随意编辑它或让我把它变成一个维基。或者让我知道这些错误……我不能保证会花更多时间在上面。我没有完成clear对排序版本的实施。并且erase不会破坏已排序的对象；sorted_skip_array在被销毁之前不会发生这种情况。

#include <vector>

template< class T, class Alloc >
class skip_array_base {
protected:
    struct node {
        node *prev, *next;
        T val;

        node( T const &x = T() ) : prev(), next(), val(x) {}
    };
    typedef typename Alloc::template rebind< node >::other allocator_type;

    typedef std::vector< node, allocator_type > vector_type;
    typedef typename vector_type::iterator vector_iterator;
    vector_type v;

    skip_array_base( allocator_type const &a = allocator_type() ) : v( a ) {}
    skip_array_base( skip_array_base const &in ) : v( in.v ) {}
    skip_array_base( typename vector_type::size_type s,
        typename vector_type::value_type const &x, allocator_type const &a )
        : v( s, x, a ) {}

    template< class Tcv >
    struct iter : vector_iterator {
        typedef T value_type;
        typedef Tcv &reference;
        typedef Tcv *pointer;

        iter() {}
        iter( vector_iterator const &in )
            : vector_iterator( in ) {}

        reference operator*() { return vector_iterator::operator*().val; }
        pointer operator->() { return &vector_iterator::operator*().val; }
        reference operator[]( typename vector_iterator::difference_type n )
            { return vector_iterator::operator[]( n ).val; }

        iter &operator++() { vector_iterator::operator++(); return *this; }
        iter operator++(int) { return vector_iterator::operator++(0); }
        iter &operator--() { vector_iterator::operator--(); return *this; }
        iter operator--(int) { return vector_iterator::operator--(0); }

        iter &operator+=( typename vector_iterator::difference_type n )
            { vector_iterator::operator+=( n ); return *this; }
        iter operator+( typename vector_iterator::difference_type n )
            { return vector_iterator::operator+( n ); }
        iter &operator-=( typename vector_iterator::difference_type n )
            { vector_iterator::operator-=( n ); return *this; }
        iter operator-( typename vector_iterator::difference_type n )
            { return vector_iterator::operator-( n ); }
    };

public:
    typedef typename vector_type::size_type size_type;

    void swap( skip_array_base &r ) { v.swap( r.v ); }
    skip_array_base &operator=( skip_array_base const &x ) {
        v = x.v;
        return *this;
    }

    size_type size() const { return v.size() - 2; }
    size_type max_size() const { return v.max_size() - 2; }
    bool empty() const { return v.size() > 2; }

    bool operator== ( skip_array_base const &r ) const { return v == r.v; }
    bool operator!= ( skip_array_base const &r ) const { return v != r.v; }
    bool operator< ( skip_array_base const &r ) const { return v < r.v; }
    bool operator> ( skip_array_base const &r ) const { return v > r.v; }
    bool operator<= ( skip_array_base const &r ) const { return v <= r.v; }
    bool operator>= ( skip_array_base const &r ) const { return v >= r.v; }

    void clear() { v.erase( ++ v.begin(), -- v.end() ); }
};

template< class T, class Alloc >
class sorted_skip_array;

template< class T, class Alloc = std::allocator<T> >
class skip_array_prelim : public skip_array_base< T, Alloc > {
    typedef skip_array_base< T, Alloc > base;
    typedef typename base::vector_type vector_type;
    using skip_array_base< T, Alloc >::v;

public:
    typedef T value_type;
    typedef typename Alloc::reference reference;
    typedef typename Alloc::const_reference const_reference;
    typedef typename base::template iter< value_type > iterator;
    typedef typename base::template iter< const value_type > const_iterator;
    typedef typename vector_type::difference_type difference_type;
    typedef typename vector_type::size_type size_type;
    typedef typename vector_type::allocator_type allocator_type;

    skip_array_prelim( allocator_type const &a = allocator_type() )
        : base( 2, value_type(), a ) {}
    skip_array_prelim( skip_array_prelim const &in )
        : base( in ) {}
    skip_array_prelim( size_type s, value_type const &x = value_type(),
        allocator_type const &a = allocator_type() )
        : base( s + 2, x, a ) {}

    template< class I >
    skip_array_prelim( I first, I last,
        allocator_type const &a = allocator_type(),
        typename I::pointer = typename I::pointer() )
        : base( 1, value_type(), a ) {
        v.insert( v.end(), first, last );
        v.push_back( value_type() );
    }

    iterator begin() { return ++ v.begin(); }
    iterator end() { return -- v.end(); }
    const_iterator begin() const { return ++ v.begin(); }
    const_iterator end() const { return -- v.end(); }

    reference operator[]( size_type n ) { return v[ n + 1 ]; }
    const_reference operator[]( size_type n ) const { return v[ n + 1 ]; }

    iterator insert( iterator pos, value_type const &x )
        { return v.insert( pos, x ); }
    iterator insert( iterator pos, size_type n, value_type const &x )
        { return v.insert( pos, n, x ); }
    template< class I >
    iterator insert( iterator pos, I first, I last,
        typename I::pointer = typename I::pointer() )
        { return v.insert( pos, first, last ); }

    iterator erase( iterator i ) { return v.erase( i ); }
    iterator erase( iterator first, iterator last )
        { return v.erase( first, last ); }
};

template< class T, class Alloc = std::allocator<T> >
class sorted_skip_array : public skip_array_base< T, Alloc > {
    typedef skip_array_base< T, Alloc > base;
    typedef typename base::vector_type vector_type;
    typedef typename vector_type::iterator vector_iterator;
    typedef typename base::node node;
    using skip_array_base< T, Alloc >::v;

    template< class Tcv >
    struct iter : base::template iter< Tcv > {
        typedef std::bidirectional_iterator_tag iterator_category;
        typedef Tcv &reference;
        typedef Tcv *pointer;

        iter() {}
        iter( vector_iterator const &x ) : base::template iter< Tcv >( x ) {}

        iter &operator++() { increment< &node::next, 1 >(); return *this; }
        iter operator++(int)
            { iter r = *this; increment< &node::next, 1 >(); return r; }
        iter &operator--() { increment< &node::prev, -1 >(); return *this; }
        iter operator--(int)
            { iter r = *this; increment< &node::prev, -1 >(); return r; }

    private:
        template< node *node::*link, int inc >
        void increment() {
            vector_iterator memo = *this; // un-consts a const_iterator
            node *pen = &*( memo += inc );
            while ( pen->*link && pen->*link != pen ) pen = pen->*link;
            *this = iter( vector_iterator( (*memo).*link = pen ) );
        }
    };

public:
    typedef T value_type;
    typedef typename Alloc::reference reference;
    typedef typename Alloc::const_reference const_reference;
    typedef iter< T > iterator;
    typedef iter< const T > const_iterator;
    typedef typename vector_type::difference_type difference_type;
    typedef typename vector_type::size_type size_type;

    sorted_skip_array( skip_array_prelim<T,Alloc> &x ) {
        sort( x.begin(), x.end() );
        swap( x );
    }

    iterator begin() { return ++ iterator( v.begin() ); }
    iterator end() { return iterator( -- v.end() ); }
    const_iterator begin() const { return ++ const_iterator( v.begin() ); }
    const_iterator end() const { return const_iterator( -- v.end() ); }

    iterator erase( iterator i ) {
        vector_iterator vi = i;
        vi->prev = &* vi[-1];
        vi->next = &* vi[1];
        //vi->val->~value_type(); // don't bother with allocator rigmarole
        return ++ i;
    }
    iterator erase( iterator first, iterator last ) {
        if ( first != last ) {
            vector_iterator vf = first, vl = last - 1;
            vl->prev = &* vf[-1];
            vf->next = &* vl[1];
        }
        return last;
    }
};
于 2010-03-24T21:25:20.870 回答
0

我在这里不是 100% 确定的，但是您可以std::next_permutation即时使用来找出您存储在集合中的信息吗？您链接中的算法看起来不需要像 std::set 这样的大型数据结构来处理这些事情......

您可能还想考虑创建一个固定数组而不是一个集合。即使该数组需要存储 3 倍于集合的元素才能发挥性能，但请记住，std::set 中的每个节点除了所讨论的数据元素外，还可能至少占用两个指针的空间。因此，您应该节省空间并在动态分配中提高速度。

std::binary_search在std::set插入大量元素然后读取大量元素的情况下，与 std::set相比之下，针对交错插入和删除进行了优化。如果您的插入和删除是分开的，只需对向量进行排序并使用二进制搜索。您可能希望使用某种标志来标记从向量中删除，而不是每次都实际删除以减少复制。然后可以立即销毁整个向量。

希望有帮助:)

于 2010-03-24T21:24:47.070 回答
0

我找到了比设置快 12 倍的最佳方式。我使用了boost dynamic_bitset，它让我可以使用 bitset 并决定运行时的位数。

编辑：万一有人在将来读到这个……这个算法并不比标准的复制和回写转换方法快，数据元素是正常大小（4-8 字节）。较大的数据大小（例如，如果您要复制大型结构，例如 128 字节），速度很快。

于 2010-03-25T15:02:01.403 回答