Vacancy implementazione dell'algoritmo di monitoraggio in C ++

Question

Sto cercando di utilizzare i href="http://academic.research.microsoft.com/Paper/44653.aspx" per eseguire la trasposizione di array multidimensionali in C ++. Gli array sono puntatori nulli così sto usando la manipolazione indirizzo per eseguire le copie.

In sostanza, esiste un algoritmo che inizia con un offset e lavora la sua strada attraverso l'intera rappresentazione 1-D della matrice come il formaggio svizzero, battendo altri offset fino a quando non torna a quella originale. Quindi, è necessario avviare al prossimo, intatta offset e farlo di nuovo. Ripeti fino a quando tutti gli spostamenti sono stati toccati.

In questo momento, sto usando uno std :: set basta compilare tutti i possibili scostamenti (0 fino alla piega moltiplicativo delle dimensioni della matrice). Poi, come vado attraverso l'algoritmo, io cancellerò dal set. Immagino che questo sarebbe più veloce perché ho bisogno di accedere in modo casuale offset nell'albero / set ed eliminarli. Poi ho bisogno di trovare rapidamente il prossimo intatta / eliminate offset.

Prima di tutto, riempiendo il set è molto lento e sembra che ci deve essere un modo migliore. Si chiama singolarmente nuovo [] per ogni inserto. Quindi, se ho 5 milioni di offset, c'è 5 milioni di notizie, più riequilibrando l'albero costantemente che come sapete non è veloce per una lista pre-ordinato.

In secondo luogo, la cancellazione è lento pure.

In terzo luogo, assumendo i tipi di dati di 4 byte come int e float, sto utilizzando fino effettivamente la stessa quantità di memoria, come l'array per memorizzare questa lista di offset intatta.

In quarto luogo, determinare se ci sono eventuali compensazioni incontaminate e ottenere uno di loro è veloce - una buona cosa

.

Qualcuno ha suggerimenti per nessuno di questi problemi?

Answer 1

Ho trovato il modo migliore che è circa 12 volte più veloce rispetto al set. Io uso un rel="nofollow aumentare dynamic_bitset che mi permette di usare il bitset e decidere il numero di bit in fase di esecuzione.

Modifica: Nel caso qualcuno legge questo in futuro ... questo algoritmo non è più veloce di una copia standard e metodo write-back della trasposizione con elementi di dati che sono di dimensioni normali (4-8 byte). E 'veloce con i formati di dati più grandi (come se copiare grandi strutture ad esempio 128 byte).

Answer 2

Non avendo letto che la carta,

• set::insert è probabilmente il modo più efficace per aggiungere dati, se si accede al set prima della prossima insert
• D'altra parte, se si crea il set tutto in una volta, si sta meglio fuori usando un vector e sort.
• Cancellazione dal un vettore ordinato è facile se si aggiunge un puntatore a accanto al vettore elemento.
  • inizializzare next = NULL. Se next == NULL, elemento valido (non è stato rimosso).
  • Per rimuovere, impostare next = this+1.
  • Per ottenere il prossimo, iterare elementi vettoriali da this+1 al primo elemento in cui iter->next != iter+1. Poi if ( iter->next == NULL ) return iter; else return iter->next;
  • Aggiornamento (this+1)->next = iter (or) iter->next prima return per ottenere ammortizzato costante di tempo.
  • Aggiungi un elemento di guardia alla fine con next == this. Questo, non vector::end, segna la fine della sequenza.

Ecco una prima bozza, ho codificato in su. Non testato; sentitevi liberi di modificarlo o mi chiedono di farne un wiki. O fammi sapere gli insetti ... non posso garantire di trascorrere più tempo su di esso. Non ho finito attuazione clear sulla versione ordinata. E erase non distrugge gli oggetti ordinati; questo non accade fino a quando il sorted_skip_array viene distrutto.

#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

Io non sono sicuro al 100% qui, ma si potrebbe usare std::next_permutation on-the-fly di capire le informazioni che stavi archiviano nel set? L'algoritmo nel tuo link non sembra ha bisogno di una grande struttura di dati come uno std :: set per gestire questo genere di cose ...

Si potrebbe anche prendere in considerazione la creazione di una matrice fissa, invece di un set. Anche se tale matrice ha bisogno di memorizzare 3 volte il numero di elementi come il set di essere performante, ricordare che ogni nodo in uno std :: set è probabilmente prendendo almeno lo spazio di due puntatori, oltre all'elemento di dati in questione. Pertanto si dovrebbe risparmiare spazio e portare un sacco di velocità nelle allocazioni dinamiche.

Un vettore ordinato in combinazione con std::binary_search si esibirà meglio di un std::set per i casi in cui si inserisce un sacco di elementi e quindi leggere un sacco di elementi in seguito. std::set, in confronto, è ottimizzata per inserti intercalati e rimozioni. Se i vostri inserti e rimozioni sono separate solo ordinare il vettore e usare la ricerca binaria. Si potrebbe voler utilizzare una sorta di bandiera per contrassegnare eliminati dal vettore piuttosto che in realtà l'eliminazione di ogni tempo per ridurre la copia. Poi tutta vettore può essere distrutto in una sola volta.

La speranza che aiuta:)