Qual é a melhor maneira de criar um array esparso em C ++?

Eu estou trabalhando em um projeto que requer a manipulação de matrizes enormes, especificamente sumtórios piramidais para um cálculo da cópula.

Em suma, eu preciso manter um número relativamente pequeno de valores (geralmente um valor de 1 e, em casos raros, mais de 1) em um mar de zeros na matriz (array multidimensional).

Uma matriz esparsa permite que o usuário armazene um pequeno número de valores e assuma que todos os registros indefinidos sejam um valor predefinido. Como não é fisicamente possível armazenar todos os valores na memory, preciso armazenar apenas os poucos elementos diferentes de zero. Isso poderia ser vários milhões de inputs.

A velocidade é uma grande prioridade, e eu também gostaria de escolher dinamicamente o número de variables ​​na class em tempo de execução.

Eu atualmente trabalho em um sistema que usa uma tree de pesquisa binária (b-tree) para armazenar inputs. Alguém sabe de um sistema melhor?

    Para C ++, um mapa funciona bem. Vários milhões de objects não serão um problema. 10 milhões de itens demoraram cerca de 4,4 segundos e cerca de 57 MB no meu computador.

    Minha aplicação de teste é a seguinte:

    #include  #include  #include  class triple { public: int x; int y; int z; bool operator<(const triple &other) const { if (x < other.x) return true; if (other.x < x) return false; if (y < other.y) return true; if (other.y < y) return false; return z < other.z; } }; int main(int, char**) { std::map data; triple point; int i; for (i = 0; i < 10000000; ++i) { point.x = rand(); point.y = rand(); point.z = rand(); //printf("%d %d %d %d\n", i, point.x, point.y, point.z); data[point] = i; } return 0; } 

    Agora, para escolher dinamicamente o número de variables, a solução mais fácil é representar o índice como uma sequência e, em seguida, usar a sequência de caracteres como uma chave para o mapa. Por exemplo, um item localizado em [23] [55] pode ser representado por meio da string "23,55". Nós também podemos estender esta solução para dimensões mais altas; por exemplo, para três dimensões, um índice arbitrário será semelhante a "34,45,56". Uma implementação simples desta técnica é a seguinte:

     std::map data data; char ix[100]; sprintf(ix, "%d,%d", x, y); // 2 vars data[ix] = i; sprintf(ix, "%d,%d,%d", x, y, z); // 3 vars data[ix] = i; 

    Apenas como um conselho: o método usando strings como índices é realmente muito lento. Uma solução muito mais eficiente, porém equivalente, seria usar vetores / matrizes. Não há absolutamente nenhuma necessidade de escrever os índices em uma string.

     typedef vector index_t; struct index_cmp_t : binary_function { bool operator ()(index_t const& a, index_t const& b) const { for (index_t::size_type i = 0; i < a.size(); ++i) if (a[i] != b[i]) return a[i] < b[i]; return false; } }; map data; index_t i(dims); i[0] = 1; i[1] = 2; // … etc. data[i] = 42; 

    No entanto, usar um map não é realmente muito eficiente devido à implementação em termos de uma tree de pesquisa binária balanceada. Estruturas de dados muito melhores neste caso seriam uma tabela de hash (randomizada).

    O Boost tem uma implementação modelada de BLAS chamada uBLAS que contém uma matriz esparsa.

    http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/index.htm

    Pequeno detalhe na comparação do índice. Você precisa fazer uma comparação lexicográfica, caso contrário:

     a= (1, 2, 1); b= (2, 1, 2); (a 

    Edit: Então a comparação provavelmente deve ser:

     return lhs.x 

    Tabelas de hash têm uma inserção rápida e procuram. Você poderia escrever uma function hash simples, já que você sabe que estaria lidando apenas com pares inteiros como chaves.

    Eigen é uma biblioteca de álgebra linear C ++ que possui uma implementação de uma matriz esparsa. Ele ainda suporta operações de matriz e solucionadores (fatoração LU etc) que são otimizados para matrizes esparsas.

    Lista completa de soluções pode ser encontrada na wikipedia. Por conveniência, eu citei seções relevantes como segue.

    https://en.wikipedia.org/wiki/Sparse_matrix#Dictionary_of_keys_.28DOK.29

    Dicionário de chaves (DOK)

    O DOK consiste em um dictionary que mapeia (linha, coluna) pares para o valor dos elementos. Elementos que estão faltando no dictionary são considerados como zero. O formato é bom para construir incrementalmente uma matriz esparsa em ordem aleatória, mas pobre para iterar sobre valores diferentes de zero em ordem lexicográfica. Geralmente, uma constrói uma matriz nesse formato e, em seguida, converte em outro formato mais eficiente para processamento. [1]

    Lista de listas (LIL)

    O LIL armazena uma lista por linha, com cada input contendo o índice da coluna e o valor. Normalmente, essas inputs são mantidas classificadas pelo índice da coluna para uma pesquisa mais rápida. Esse é outro formato bom para a construção de matriz incremental. [2]

    Lista de coordenadas (COO)

    O COO armazena uma lista de tuplas (linha, coluna, valor). Idealmente, as inputs são classificadas (por índice de linha, depois por índice de coluna) para melhorar os tempos de access random. Este é outro formato que é bom para construção de matriz incremental. [3]

    Linha esparsa comprimida (formato CSR, CRS ou Yale)

    O formato compactado de linha esparsa (CSR) ou armazenamento de linha compactada (CRS) representa uma matriz M por três matrizes (unidimensionais), que contêm respectivamente valores diferentes de zero, a extensão de linhas e índices de coluna. É semelhante ao COO, mas comprime os índices de linha, daí o nome. Esse formato permite access rápido a linhas e multiplicações vetoriais (Mx).

    A melhor maneira de implementar matrizes esparsas é não implementá-las – pelo menos não por conta própria. Gostaria de sugerir ao BLAS (que eu acho que é uma parte do LAPACK), que pode lidar com matrizes realmente enormes.

    Como apenas os valores com [a] [b] [c] … [w] [x] [y] [z] são conseqüentes, armazenamos apenas o próprio índice, não o valor 1, que é praticamente qualquer lugar – sempre o mesmo + não há maneira de hash isso. Observando que a maldição da dimensionalidade está presente, sugira que vá com alguma ferramenta estabelecida NIST ou Boost, pelo menos leia as fonts para que isso possa contornar erros desnecessários.

    Se o trabalho precisar capturar as distribuições de dependência temporal e as tendências paramétricas de conjuntos de dados desconhecidos, então um Mapa ou Árvore B com raiz de valor não é provavelmente prático. Podemos armazenar apenas o próprio índice, com hash se a ordenação (sensibilidade para apresentação) puder ser subordinada à redução do domínio de tempo em tempo de execução, para todos os 1 valores. Como valores diferentes de zero são diferentes, um candidato óbvio para eles é qualquer estrutura de dados que você possa encontrar facilmente e entender. Se o dataset for verdadeiramente de tamanho grande para o universo, sugiro algum tipo de janela deslizante que gerencie arquivo / disco / persistente-io, movendo partes dos dados para o escopo, conforme necessário. (código de escrita que você pode entender) Se você está comprometido em fornecer uma solução real para um grupo de trabalho, deixar de fazê-lo deixa você à mercê de sistemas operacionais que tenham o único objective de levar seu almoço para longe de você.

    Aqui está uma implementação relativamente simples que deve fornecer uma pesquisa rápida razoável (usando uma tabela de hash), bem como uma iteração rápida sobre elementos diferentes de zero em uma linha / coluna.

     // Copyright 2014 Leo Osvald // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. #ifndef UTIL_IMMUTABLE_SPARSE_MATRIX_HPP_ #define UTIL_IMMUTABLE_SPARSE_MATRIX_HPP_ #include  #include  #include  #include  #include  #include  #include  // A simple time-efficient implementation of an immutable sparse matrix // Provides efficient iteration of non-zero elements by rows/cols, // eg to iterate over a range [row_from, row_to) x [col_from, col_to): // for (int row = row_from; row < row_to; ++row) { // for (auto col_range = sm.nonzero_col_range(row, col_from, col_to); // col_range.first != col_range.second; ++col_range.first) { // int col = *col_range.first; // // use sm(row, col) // ... // } template class SparseMatrix { struct PointHasher; typedef std::map< Coord, std::vector > NonZeroList; typedef std::pair Point; public: typedef T ValueType; typedef Coord CoordType; typedef typename NonZeroList::mapped_type::const_iterator CoordIter; typedef std::pair CoordIterRange; SparseMatrix() = default; // Reads a matrix stored in MatrixMarket-like format, ie: //    //    // ... // Note: the header (lines starting with '%' are ignored). template void Init(InputStream& is) { rows_.clear(), cols_.clear(); values_.clear(); // skip the header (lines beginning with '%', if any) decltype(is.tellg()) offset = 0; for (char buf[max_line_length + 1]; is.getline(buf, sizeof(buf)) && buf[0] == '%'; ) offset = is.tellg(); is.seekg(offset); size_t n; is >> row_count_ >> col_count_ >> n; values_.reserve(n); while (n--) { Coord row, col; typename std::remove_cv::type val; is >> row >> col >> val; values_[Point(--row, --col)] = val; rows_[col].push_back(row); cols_[row].push_back(col); } SortAndShrink(rows_); SortAndShrink(cols_); } const T& operator()(const Coord& row, const Coord& col) const { static const T kZero = T(); auto it = values_.find(Point(row, col)); if (it != values_.end()) return it->second; return kZero; } CoordIterRange nonzero_col_range(Coord row, Coord col_from, Coord col_to) const { CoordIterRange r; GetRange(cols_, row, col_from, col_to, &r); return r; } CoordIterRange nonzero_row_range(Coord col, Coord row_from, Coord row_to) const { CoordIterRange r; GetRange(rows_, col, row_from, row_to, &r); return r; } Coord row_count() const { return row_count_; } Coord col_count() const { return col_count_; } size_t nonzero_count() const { return values_.size(); } size_t element_count() const { return size_t(row_count_) * col_count_; } private: typedef std::unordered_map::type, PointHasher> ValueMap; struct PointHasher { size_t operator()(const Point& p) const { return p.first << (std::numeric_limits::digits >> 1) ^ p.second; } }; static void SortAndShrink(NonZeroList& list) { for (auto& it : list) { auto& indices = it.second; indices.shrink_to_fit(); std::sort(indices.begin(), indices.end()); } // insert a sentinel vector to handle the case of all zeroes if (list.empty()) list.emplace(Coord(), std::vector(Coord())); } static void GetRange(const NonZeroList& list, Coord i, Coord from, Coord to, CoordIterRange* r) { auto lr = list.equal_range(i); if (lr.first == lr.second) { r->first = r->second = list.begin()->second.end(); return; } auto begin = lr.first->second.begin(), end = lr.first->second.end(); r->first = lower_bound(begin, end, from); r->second = lower_bound(r->first, end, to); } ValueMap values_; NonZeroList rows_, cols_; Coord row_count_, col_count_; }; #endif /* UTIL_IMMUTABLE_SPARSE_MATRIX_HPP_ */ 

    Por simplicidade, é immutable , mas você pode torná-lo mutável; não se esqueça de mudar std::vector para std::set se você quiser uma “inserção” razoavelmente eficiente (mudar um zero para um diferente de zero).

    Eu sugeriria fazer algo como:

     typedef std::tuple coord_t; typedef boost::hash coord_hash_t; typedef std::unordered_map sparse_array_t; sparse_array_t the_data; the_data[ { x, y, z } ] = 1; /* list-initialization is cool */ for( const auto& element : the_data ) { int xx, yy, zz, val; std::tie( std::tie( xx, yy, zz ), val ) = element; /* ... */ } 

    Para ajudar a manter seus dados esparsos, você pode escrever uma subclass de unorderd_map , cujos iteradores pulam automaticamente (e apagam) quaisquer itens com um valor de 0.