Suivi Vacancy mise en œuvre dans l'algorithme C ++

Question

Je suis en train d'utiliser les pour effectuer la transposition de tableaux multidimensionnels en C ++. Les tableaux sont des pointeurs comme vide alors j'utilise la manipulation d'adresse pour effectuer les copies.

En fait, il existe un algorithme qui commence par un décalage et son chemin à travers toute la représentation 1-d du tableau comme le fromage suisse, assommant d'autres compensations jusqu'à ce qu'il revienne à l'original. Ensuite, vous devez commencer à la suivante, intacte offset et le faire à nouveau. Vous répétez jusqu'à ce que tous les décalages ont été touchés.

En ce moment, je suis sur un std :: set juste remplir toutes les compensations possibles (0 à la fois multiplicatif des dimensions du tableau). Puis, comme je passe par l'algorithme, j'efface de l'ensemble. Je figure que ce serait plus rapide parce que je dois accéder au hasard des décalages dans l'arborescence / set et les supprimer. Ensuite, je dois trouver rapidement la prochaine intacte / UNDELETED offset.

Tout d'abord, en remplissant l'ensemble est très lent et il semble que il doit y avoir une meilleure façon. Il est d'appeler individuellement nouveau [] pour chaque insert. Donc, si j'ai 5 millions de compensations, il y a 5 millions de nouvelles, plus rééquilibrant l'arbre constamment comme vous le savez n'est pas rapide pour une liste pré-triés.

En second lieu, la suppression est lent aussi bien.

En troisième lieu, en supposant des types de données de 4 octets comme int et float, je l'utilise en fait la même quantité de mémoire que le tableau lui-même pour stocker cette liste des compensations intactes.

En quatrième lieu, déterminer s'il y a des compensations intactes et d'obtenir un d'entre eux est rapide - une bonne chose

.

Quelqu'un at-il des suggestions pour l'une de ces questions?

Answer 1

J'ai trouvé la meilleure façon qui est d'environ 12x plus rapide que l'ensemble. J'utilise un stimuler dynamic_bitset qui me permet d'utiliser les BITSET et décider du nombre de bits lors de l'exécution.

Edit: Au cas où quelqu'un se lit à l'avenir ... cet algorithme est pas plus rapide qu'une copie standard et méthode write-back de la transposition des éléments de données qui sont de taille normale (4-8 octets). Il est rapide avec des tailles de données plus volumineux (comme si vous copiez de grandes structures par exemple 128 octets).

Answer 2

Ne pas avoir lu ce document,

• set::insert est probablement le moyen le plus efficace d'ajouter des données si vous accédez à la set avant la prochaine insert
• D'autre part, si vous construisez le jeu à la fois, vous êtes mieux à l'aide d'un vector et sort.
• Suppression d'un vecteur est facile si Sorted vous ajoutez un pointeur à côté de l'élément vectoriel.
  • Initialiser next = NULL. Si next == NULL, élément est valide (n'a pas été supprimé).
  • Pour supprimer, mettre next = this+1.
  • Pour obtenir ensuite itérer sur des éléments de vecteur de this+1 au premier élément où iter->next != iter+1. Puis if ( iter->next == NULL ) return iter; else return iter->next;
  • Mise à jour (this+1)->next = iter (or) iter->next avant return pour obtenir un temps constant après amortissement.
  • Ajouter un élément de garde à la fin avec next == this. Ce, non vector::end, marque la fin de la séquence.

Voici un premier projet, je codé vers le haut. Pas testé; ne hésitez pas à le modifier ou me demander de faire un wiki. Ou laissez-moi savoir les bugs ... Je ne peux pas garantir de passer plus de temps. Je n'ai pas fini la mise en œuvre clear sur la version triée. Et erase ne détruit pas les objets triés; cela ne se produit pas jusqu'à ce que la sorted_skip_array est détruite.

#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

Je ne suis pas sûr à 100%, mais pourriez-vous utiliser std::next_permutation sur la volée pour trouver les informations que vous stockez dans l'ensemble? L'algorithme de votre lien ne ressemble pas besoin d'une grande structure de données comme un std :: set pour gérer ce genre de choses ...

Vous pouvez également envisager de créer un tableau fixe au lieu d'un ensemble. Même si ce tableau a besoin de stocker 3 fois autant d'éléments que l'ensemble pour être performant, rappelez-vous que chaque noeud dans un std :: set prend probablement au moins l'espace de deux pointeurs, en plus de l'élément de données en question. Par conséquent, vous devriez économiser de l'espace et faites beaucoup de vitesse dans les allocations dynamiques.

Un vecteur trié combiné avec std::binary_search interprétera mieux qu'un std::set pour les cas où vous insérez beaucoup d'éléments et lu beaucoup d'éléments plus tard. std::set, par comparaison, est optimisée pour les inserts intercalaires et les renvois. Si vos inserts et les renvois sont séparés simplement trier le vecteur et utiliser la recherche binaire. Vous voudrez peut-être utiliser une sorte de drapeau marqueur supprimé du vecteur plutôt que de supprimer en fait à chaque fois pour réduire la copie. Ensuite, le vecteur entier peut être détruit à la fois.

Hope qui aide:)