Реализация алгоритма отслеживания вакансий в C ++

Question

Я пытаюсь использовать алгоритм отслеживания вакансий , чтобы выполнить транспонирование многомерных массивов в C ++. Массивы представляют собой пустые указатели, поэтому я использую манипулирование адресами для выполнения копий.

По сути, существует алгоритм, который начинается со смещения и проходит через все 1-мерное представление массива, как швейцарский сыр, отбрасывая другие смещения до тех пор, пока он не вернется к исходному. Затем вы должны начать со следующего, нетронутого смещения и сделать это снова. Вы повторяете, пока не будут затронуты все смещения.

Прямо сейчас я использую std :: set, чтобы просто заполнить все возможные смещения (от 0 до мультипликативной кратности размеров массива). Затем, проходя алгоритм, я стираю из набора. Я полагаю, что это будет быстрее, потому что мне нужно получить произвольный доступ к смещениям в дереве / наборе и удалить их. Затем мне нужно быстро найти следующее нетронутое / неосуществленное смещение.

Прежде всего, заполнение набора происходит очень медленно, и кажется, что должен быть лучший способ. Он индивидуально вызывает new [] для каждой вставки. Поэтому, если у меня есть 5 миллионов смещений, есть 5 миллионов новостей, плюс постоянная перебалансировка дерева, что, как вы знаете, не является быстрым для предварительно отсортированного списка.

Во-вторых, удаление также происходит медленно.

В-третьих, предполагая 4-байтовые типы данных, такие как int и float, я фактически использую тот же объем памяти, что и сам массив, для хранения этого списка нетронутых смещений.

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

У кого-нибудь есть предложения по любой из этих проблем?

Answer 1

Не прочитав эту газету,

• set::insert, вероятно, является наиболее эффективным способом добавления данных, если вы получите доступ к set до следующего insert
• С другой стороны, если вы строите набор сразу, лучше всего использовать vector и sort.
• Удаление из отсортированного вектора легко, если вы добавляете указатель на следующий за элементом вектора.
  • Инициализировать next = NULL. Если next == NULL, элемент действителен (не был удален).
  • Чтобы удалить, установите next = this+1.
  • Чтобы перейти к следующему, переберите элементы вектора от this+1 до первого элемента, где 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;
    }
};

Answer 2

Я нашел лучший способ, который примерно в 12 раз быстрее, чем набор. Я использую boost dynamic_bitset , который позволяет мне использовать битовый набор и определять количество битов во время выполнения.

Редактировать: В случае, если кто-нибудь прочтет это в будущем ... этот алгоритм не быстрее, чем стандартный метод копирования и обратной записи транспонирования с элементами данных нормального размера (4-8 байт). Это быстро с большими размерами данных (например, если вы копируете большие структуры, например 128 байт).

Answer 3

Я не уверен на 100%, но не могли бы вы использовать std::next_permutation на лету, чтобы выяснить информацию, которую вы хранили в наборе? Алгоритм в вашей ссылке не выглядит так, как будто ему нужна большая структура данных, например std :: set, для обработки подобных вещей ...

Вы также можете рассмотреть возможность создания фиксированного массива вместо набора. Даже если в этом массиве нужно хранить в 3 раза больше элементов, чем в наборе, который необходимо выполнить, помните, что каждый узел в std :: set, вероятно, занимает как минимум пространство двух указателей в дополнение к рассматриваемому элементу данных. Поэтому вы должны сэкономить место и значительно увеличить скорость при динамическом распределении.

Сортированный вектор в сочетании с std::binary_search будет работать лучше, чем std::set для случаев, когда вы вставляете много элементов, а затем читаете много элементов позже. std::set, для сравнения, оптимизирован для чередующихся вставок и удалений. Если ваши вставки и удаления разделены, просто сортируйте вектор и используйте бинарный поиск. Возможно, вы захотите использовать какой-нибудь флаг, чтобы пометить удаляемый из вектора, вместо того, чтобы фактически удалять каждый раз, чтобы уменьшить копирование. Тогда весь вектор может быть уничтожен сразу.

Надеюсь, это поможет:)