C++에서 희소 배열을 만드는 가장 좋은 방법은 무엇입니까?

Question

나는 거대한 행렬의 조작을 요구하는 프로젝트, 특히 copula 계산을위한 피라미드 합계에 대해 연구 중이다.

요약하면 매트릭스 (다차원 배열)의 0의 바다에서 상대적으로 적은 수의 값 (일반적으로 1의 값, 드물게는 1보다 큰 값)을 추적해야합니다.

희소 배열을 사용하면 소수의 값을 저장하고 정의되지 않은 모든 레코드를 사전 설정 값으로 간주 할 수 있습니다. 메모리에 모든 값을 물리적으로 저장하는 것은 아니기 때문에 0이 아닌 몇 개의 요소 만 저장해야합니다. 이것은 수백만 항목 일 수 있습니다.

속도가 큰 우선 순위이며 런타임시 클래스의 변수 수를 동적으로 선택하고 싶습니다.

현재 이진 검색 트리 (b-tree)를 사용하여 항목을 저장하는 시스템에서 작업하고 있습니다. 누구든지 더 나은 시스템을 알고 있습니까?

Answer 1

C++의 경우 맵이 잘 작동합니다. 수백만 개의 물체가 문제가되지 않습니다. 내 컴퓨터에서 약 1 천만 항목이 약 4.4 초 및 약 57 메가를 차지했습니다. 다음과 같이

내 테스트 응용 프로그램은 다음과 같습니다

이제

#include <stdio.h> 
#include <stdlib.h> 
#include <map> 

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<triple,int> 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; 
} 

동적 변수의 수를 선택, 가장 쉬운 해결책은 문자열로 인덱스를 나타내며, 다음지도의 핵심으로 문자열을 사용하는 것입니다 . 예를 들어 [23] [55]에있는 항목은 "23,55"문자열을 통해 나타낼 수 있습니다. 우리는 더 높은 차원을 위해이 솔루션을 확장 할 수도 있습니다. 3 차원과 같이 임의의 인덱스는 "34,45,56"처럼 보일 것입니다. 이 기술의 간단한 구현은 다음과 같습니다.

std::map data<string,int> 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; 

Answer 2

해시 테이블에는 빠른 삽입 및 조회가 있습니다. 정수 쌍만 키로 처리한다는 것을 알고 있으므로 간단한 해시 함수를 작성할 수 있습니다.

Answer 3

스파 스 매트릭스를 구현하는 가장 좋은 방법은 최소한 구현하지 않는 것입니다. BLAS (정말 LAPACK의 일부라고 생각합니다)에게 정말 거대한 행렬을 처리 할 수있는 방법을 제안합니다.

Answer 4

색인 비교에서 작은 세부 사항.

a= (1, 2, 1); b= (2, 1, 2); 
(a<b) == (b<a) is true, but b!=a 

편집 : 당신은 그렇지 않으면 사전 편찬 비교를 할 필요가 그래서 비교는 아마되어야합니다 :

return lhs.x<rhs.x 
    ? true 
    : lhs.x==rhs.x 
     ? lhs.y<rhs.y 
      ? true 
      : lhs.y==rhs.y 
       ? lhs.z<rhs.z 
       : false 
     : false 

Answer 5

부스트 스파 스 매트릭스를 포함 uBLAS라는 BLAS의 템플릿 구현이있다. 그냥 조언으로

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

Answer 6

: 인덱스로 문자열을 사용하는 방법은 실제로 매우 느립니다. 훨씬 효율적이지만 동등한 솔루션은 벡터/배열을 사용하는 것입니다. 색인에 문자열을 쓸 필요가 전혀 없습니다.

typedef vector<size_t> index_t; 

struct index_cmp_t : binary_function<index_t, index_t, bool> { 
    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<index_t, int, index_cmp_t> data; 
index_t i(dims); 
i[0] = 1; 
i[1] = 2; 
// … etc. 
data[i] = 42; 

그러나, map를 사용하여 때문에 균형 이진 검색 트리의 측면에서 구현 실제로 매우 효율적이지 않습니다.이 경우 훨씬 더 우수한 성능의 데이터 구조는 (임의의) 해시 테이블이됩니다.

Answer 7

값이 [a] [b] [c] ... [w] [x] [y] [z] 인 경우에만 값이되므로 값 1이 아니라 인디 스 자체 만 저장합니다. 언제 어디서나 - 항상 해쉬 할 수있는 방법은 없습니다. 차원의 저주가 존재한다는 것을 주목하고, NIST 나 Boost의 도구를 사용하여 최소한 불필요한 실수를 피할 수있는 출처를 읽으십시오.

작업이 알 수없는 데이터 세트의 시간 종속성 분포 및 매개 변수 경향을 캡처해야하는 경우, 단일 값 루트가있는 맵 또는 B- 트리가 아마도 실용적이지 않습니다. 우리는 indice 만 저장할 수 있습니다. 즉, 표시 (표현의 감수성)가 런타임에 시간 도메인 축소에 종속 될 수 있다면 해시됩니다. 1이 아닌 0이 아닌 값이 적기 때문에 쉽게 찾을 수있는 데이터 구조가 무엇이든간에 확실한 후보가됩니다. 데이터 세트가 실제로 광대 한 유니버설 크기라면 필자는 파일/디스크/퍼시스턴스 - io를 직접 관리하고 필요에 따라 데이터 범위를 데이터 범위로 이동시키는 슬라이딩 윈도우를 제안합니다. (이해할 수있는 코드 작성) 실무 그룹에 실제 솔루션을 제공하겠다는 약속을 지키지 않는다면, 그렇게하지 않으면 점심을 먹지 않는 유일한 목표 인 소비자 용 운영 체제가 제공됩니다.

Answer 8

다음은 행/열의 0이 아닌 요소에 대한 빠른 반복뿐만 아니라 합리적인 빠른 검색 (해시 테이블 사용)을 제공해야하는 비교적 간단한 구현입니다. 편의상

// 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 <algorithm> 
#include <limits> 
#include <map> 
#include <type_traits> 
#include <unordered_map> 
#include <utility> 
#include <vector> 

// A simple time-efficient implementation of an immutable sparse matrix 
// Provides efficient iteration of non-zero elements by rows/cols, 
// e.g. 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<typename T = double, class Coord = int> 
class SparseMatrix { 
    struct PointHasher; 
    typedef std::map< Coord, std::vector<Coord> > NonZeroList; 
    typedef std::pair<Coord, Coord> Point; 

public: 
    typedef T ValueType; 
    typedef Coord CoordType; 
    typedef typename NonZeroList::mapped_type::const_iterator CoordIter; 
    typedef std::pair<CoordIter, CoordIter> CoordIterRange; 

    SparseMatrix() = default; 

    // Reads a matrix stored in MatrixMarket-like format, i.e.: 
    // <num_rows> <num_cols> <num_entries> 
    // <row_1> <col_1> <val_1> 
    // ... 
    // Note: the header (lines starting with '%' are ignored). 
    template<class InputStream, size_t max_line_length = 1024> 
    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<T>::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<Point, 
          typename std::remove_cv<T>::type, 
          PointHasher> ValueMap; 

    struct PointHasher { 
    size_t operator()(const Point& p) const { 
     return p.first << (std::numeric_limits<Coord>::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>(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_ */ 

, 그것은 immutable,하지만 당신은 변경할 수 있습니다; 합리적인 효율적인 "삽입"(0을 0이 아닌 값으로 변경)을 원하면 std::vector을 std::set으로 변경하십시오.

Answer 9

Eigen은 희소 행렬이 implementation 인 C++ 선형 대수 라이브러리입니다. 스파 스 매트릭스에 최적화 된 행렬 연산 및 솔버 (LU 인수 분해 등)도 지원합니다.

Answer 10

나는 같은 일을 제안 : 스파 스 데이터를 유지할 수 있도록

typedef std::tuple<int, int, int> coord_t; 
typedef boost::hash<coord_t> coord_hash_t; 
typedef std::unordered_map<coord_hash_t, int, c_hash_t> 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; 
    /* ... */ 
} 

, 당신은 누구의 반복자 자동으로 건너 unorderd_map의 서브 클래스를 작성하려면 (및 삭제) 수의 값을 가진 모든 항목을 0

Answer 11

전체 솔루션 목록은 위키피디아에서 찾을 수 있습니다. 편의를 위해 다음과 같이 관련 섹션을 인용했습니다. 키

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

사전 (DOK)

DOK가지도 (행, 열)의 요소의 값 -pairs 사전 구성된다. 사전 에서 누락 된 요소는 0으로 간주됩니다. 형식은 점차적으로 점진적으로 희소 행렬을 임의의 순서로 구성하지만 은 사전 식으로 0이 아닌 값을 반복하는 데 적합하지 않습니다. 일반적으로 은이 형식의 행렬을 구성한 다음 더 효율적인처리 형식으로 변환합니다.목록 (LIL)

LIL 점포 [1]

에서 열 인덱스 및 값을 포함하는 각각의 엔트리와 행당 하나 개의리스트. 일반적으로 이러한 항목은 빠른 검색을 위해 열 인덱스별로 정렬 된 상태로 유지됩니다. 이것은 인크 리 멘탈 (incremental) 행렬 구조에 좋은 또 다른 형식입니다. [2]

업무리스트 (COO)

COO 저장소 (행, 열 값) 튜플리스트. 이상적으로는 항목이 (행 색인별로, 그리고 열 색인별로) 정렬되어 임의 액세스를 향상시킵니다. 번. 이는 증분 행렬 구성에 적합한 또 다른 형식입니다. [3]

는

압축 성긴 행 (CSR은 CRS 예일 포맷)

압축 희소 행 (CSR) 또는 압축 로우 스토리지 (CRS)의 형식 세에 의해 행렬 M (액형를 나타낸다 에는 각각 0이 아닌 값, 행의 범위 및 색인이 들어 있습니다. 이것은 COO와 유사하지만 행 인덱스를 압축하므로 이름. 이 형식은 빠른 행 액세스와 행렬 벡터 곱셈 (Mx)을 허용합니다.