Implementação de algoritmo de rastreamento de vaga em C ++

Question

Estou tentando usar o Algoritmo de rastreamento de vagas para realizar a transposição de matrizes multidimensionais em C ++. As matrizes vêm como ponteiros vazios, por isso estou usando a manipulação de endereços para executar as cópias.

Basicamente, há um algoritmo que começa com um deslocamento e segue em toda a representação 1-D da matriz como queijo suíço, eliminando outras compensações até voltar ao original. Então, você deve começar no próximo deslocamento intocado e fazê -lo novamente. Você se repete até que todas as compensações tenham sido tocadas.

No momento, estou usando um std :: definido para preencher todas as compensações possíveis (0 até a dobra multiplicativa das dimensões da matriz). Então, ao passar pelo algoritmo, apagarei do conjunto. Acho que isso seria mais rápido, porque preciso acessar aleatoriamente compensações na árvore/conjunto e excluí -las. Então eu preciso encontrar rapidamente o próximo deslocamento intocado/não selecionado.

Primeiro de tudo, encher o conjunto é muito lento e parece que deve haver uma maneira melhor. É individualmente chamando novo [] para cada inserção. Portanto, se eu tiver 5 milhões de compensações, há 5 milhões de notícias, além de balancear a árvore constantemente que, como você sabe, não é rápido para uma lista pré-classificada.

Segundo, a exclusão também é lenta.

Terceiro, assumindo tipos de dados de 4 bytes como Int e Float, estou usando a mesma quantidade de memória que a própria matriz para armazenar esta lista de compensações intocadas.

Quarto, determinar se há compensações intocadas e conseguir um deles é rápido - uma coisa boa.

Alguém tem sugestões para algum desses problemas?

Answer 1

Encontrei a melhor maneira que é cerca de 12x mais rápida que o conjunto. Eu uso um Boost dynamic_bitset O que me permite usar o bitset e decidir o número de bits em tempo de execução.

EDIT: Caso alguém leia isso no futuro ... esse algoritmo não é mais rápido que um método de transposição de cópia e gravação padrão com elementos de dados que são de tamanho normal (4-8 bytes). É rápido com tamanhos de dados maiores (como se você for copiar grandes estruturas, por exemplo, 128 bytes).

Answer 2

Não tendo lido esse artigo,

• set::insert é provavelmente a maneira mais eficiente de adicionar dados se você acessar o set antes do próximo insert
• Por outro lado, se você construir o conjunto de uma só vez, é melhor usar um vector e sort.
• A remoção de um vetor classificada é fácil se você adicionar um ponteiro ao NEXT ao elemento vetorial.
  • Inicializar next = NULL. Se next == NULL, elemento é válido (não foi removido).
  • Para remover, definir next = this+1.
  • Para chegar a seguir, itera sobre elementos vetoriais de this+1 para o primeiro elemento onde iter->next != iter+1. Então if ( iter->next == NULL ) return iter; else return iter->next;
  • Atualizar (this+1)->next = iter (or) iter->next antes da return para alcançar um tempo constante amortizado.
  • Adicione um elemento de guarda no final com next == this. Isso não vector::end, marca o fim da sequência.

Aqui está um primeiro rascunho, eu o codifiquei. Não testado; Sinta -se à vontade para editá -lo ou me pedir para torná -lo um wiki. Ou deixe -me saber os bugs ... não posso garantir que gaste mais tempo com isso. Eu não terminei de implementar clear na versão classificada. E erase não destrói objetos classificados; Isso não acontece até o sorted_skip_array está destruído.

#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

Não tenho 100% de certeza aqui, mas você poderia usar std::next_permutation On-the-fly para descobrir as informações que você estava armazenando no set? O algoritmo em seu link não parece que precisa de uma grande estrutura de dados como um std :: definido para lidar com esse tipo de coisa ...

Você também pode considerar criar uma matriz fixa em vez de um conjunto. Mesmo que essa matriz precise armazenar 3 vezes mais elementos do que o conjunto de performance, lembre -se de que cada nó em um conjunto de std :: provavelmente está ocupando pelo menos o espaço de dois ponteiros, além do elemento de dados em questão. Portanto, você deve economizar no espaço e compensar muita velocidade em alocações dinâmicas.

Um vetor classificado combinado com std::binary_search terá um desempenho melhor do que um std::set Para casos em que você insere muitos elementos e depois lê muitos elementos posteriormente. std::set, em comparação, é otimizado para inserções e remoções intercaladas. Se suas inserções e remoções forem separadas, basta classificar o vetor e usar a pesquisa binária. Você pode usar algum tipo de sinalização para marcar excluído do vetor, em vez de realmente excluir cada vez para reduzir a cópia. Então todo o vetor pode ser destruído de uma vez.

Espero que ajude :)