Vacancy Tracking Algorithm implementation in C++

Question

I'm trying to use the vacancy tracking algorithm to perform transposition of multidimensional arrays in C++. The arrays come as void pointers so I'm using address manipulation to perform the copies.

Basically, there is an algorithm that starts with an offset and works its way through the whole 1-d representation of the array like swiss cheese, knocking out other offsets until it gets back to the original one. Then, you have to start at the next, untouched offset and do it again. You repeat until all offsets have been touched.

Right now, I'm using a std::set to just fill up all possible offsets (0 up to the multiplicative fold of the dimensions of the array). Then, as I go through the algorithm, I erase from the set. I figure this would be fastest because I need to randomly access offsets in the tree/set and delete them. Then I need to quickly find the next untouched/undeleted offset.

First of all, filling up the set is very slow and it seems like there must be a better way. It's individually calling new[] for every insert. So if I have 5 million offsets, there's 5 million news, plus re-balancing the tree constantly which as you know is not fast for a pre-sorted list.

Second, deleting is slow as well.

Third, assuming 4-byte data types like int and float, I'm using up actually the same amount of memory as the array itself to store this list of untouched offsets.

Fourth, determining if there are any untouched offsets and getting one of them is fast -- a good thing.

Does anyone have suggestions for any of these issues?

Answer 1

I'm not 100% sure here, but could you use std::next_permutation on-the-fly to figure out the information you were storing in the set? The algorithm in your link doesn't look like it needs a large data structure like a std::set to handle these sorts of things...

You might also want to consider creating a fixed array instead of a set. Even if that array needs to store 3 times as many elements as the set to be performant, remember that each node in a std::set is probably taking up at least the space of two pointers in addition to the data element in question. Therefore you should save on space and make up lots of speed in dynamic allocations.

A sorted vector combined with std::binary_search will perform better than a std::set for cases where you insert a lot of elements and then read a lot of elements later. std::set, in comparison, is optimized for interleaved inserts and removals. If your inserts and removals are seperated just sort the vector and use binary search. You might wish to use some sort of flag to mark deleted from the vector rather than actually deleting each time to reduce copying. Then the whole vector can be destroyed at once.

Hope that helps :)

Answer 2

Not having read that paper,

• set::insert is likely the most efficient way to add data if you will access the set before the next insert
• On the other hand, if you build the set all at once, you're best off using a vector and sort.
• Removal from a sorted vector is easy if you add a pointer-to-next to the vector element.
  • Initialize next = NULL. If next == NULL, element is valid (has not been removed).
  • To remove, set next = this+1.
  • To get next, iterate over vector elements from this+1 to the first element where iter->next != iter+1. Then if ( iter->next == NULL ) return iter; else return iter->next;
  • Update (this+1)->next = iter (or) iter->next before return to achieve amortized constant time.
  • Add a guard element at the very end with next == this. This, not vector::end, marks the end of the sequence.

Here's a first draft, I coded it up. Not tested; feel free to edit it or ask me to make it a wiki. Or let me know the bugs… I can't guarantee to spend more time on it. I didn't finish implementing clear on the sorted version. And erase doesn't destroy sorted objects; that doesn't happen until the sorted_skip_array is destroyed.

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

Answer 3

I found the best way which is about 12x faster than the set. I use a boost dynamic_bitset which lets me use the bitset and decide on the number of bits at runtime.

Edit: In case anyone reads this in the future... this algorithm is not faster than a standard copy and write-back method of transposition with data elements that are normal sized (4-8 bytes). It is fast with larger data sizes (like if you are copy large structures e.g. 128 bytes).