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

Question

저는 거대한 행렬의 조작, 특히 코퓰러 계산을 위한 피라미드 합산이 필요한 프로젝트를 진행 중입니다.

간단히 말해서, 행렬(다차원 배열)의 0 바다에서 상대적으로 적은 수의 값(일반적으로 1의 값, 드문 경우 1보다 큰 값)을 추적해야 합니다.

희소 배열을 사용하면 사용자는 소수의 값을 저장할 수 있으며 정의되지 않은 모든 레코드를 미리 설정된 값으로 가정할 수 있습니다.모든 값을 메모리에 저장하는 것은 물리적으로 불가능하므로 0이 아닌 소수의 요소만 저장하면 됩니다.이는 수백만 개의 항목일 수 있습니다.

속도는 매우 중요하며 런타임 시 클래스의 변수 수를 동적으로 선택하고 싶습니다.

저는 현재 항목을 저장하기 위해 이진 검색 트리(b-tree)를 사용하는 시스템에서 작업하고 있습니다.더 나은 시스템을 아는 사람이 있나요?

Answer 1

C++의 경우 지도가 잘 작동합니다.수백만 개의 개체는 문제가 되지 않습니다.1,000만 개의 항목을 처리하는 데 약 4.4초가 걸렸으며 내 컴퓨터에서는 약 57MB가 소요되었습니다.

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

#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

일반적인 조언으로 문자열을 인덱스로 사용하는 방법은 실제로 매우 느린.훨씬 더 효율적이지만 동등한 솔루션은 벡터/배열을 사용하는 것입니다.문자열에 인덱스를 작성할 필요가 전혀 없습니다.

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 실제로 균형 잡힌 이진 검색 트리 구현으로 인해 종종 효율적이지 않습니다.이 경우 더 나은 성능을 발휘하는 데이터 구조는 다음에서 제공하는 해시 테이블이 될 것입니다. std::unordered_map.

Answer 3

Boost에는 희소 행렬을 포함하는 uBLAS라는 BLAS의 템플릿 구현이 있습니다.

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

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

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

Answer 6

아이겐 C++ 선형 대수학 라이브러리입니다. 구현 희소 행렬.희소 행렬에 최적화된 행렬 연산 및 솔버(LU 분해 등)도 지원합니다.

Answer 7

전체 솔루션 목록은 Wikipedia에서 찾을 수 있습니다.편의상 관련 부분을 다음과 같이 인용했습니다.

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

키 사전(DOK)

Dok는 요소의 값에 매핑 (행, 열) 페어를지도하는 사전으로 구성됩니다.사전에서 누락 된 요소는 0이됩니다.이 형식은 희소 행렬을 임의 순서로 점진적으로 구성하는 데 적합하지만 사전 순서로 0이 아닌 값을 반복하기에는 불량합니다.하나는 일반적 으로이 형식으로 행렬을 구성 한 다음 처리를위한 또 다른 효율적인 형식으로 변환합니다. [1

목록의 목록(LIL)

Lil은 행당 하나의 목록을 저장하고 각 항목에는 열 인덱스와 값이 포함되어 있습니다.일반적으로 이러한 항목은 더 빠른 조회를 위해 열 인덱스별로 정렬됩니다.이것은 증분 매트릭스 구성에 좋은 또 다른 형식입니다. [2

좌표 목록(COO)

COO는 (행, 열, 값) 튜플 목록을 저장합니다.이상적으로는 랜덤 액세스 시간을 개선하기 위해 항목이 (행 색인, 열 인덱스) 정렬됩니다.이것은 증분 매트릭스 구성에 유용한 또 다른 형식입니다. [3

압축된 희소 행(CSR, CRS 또는 Yale 형식)

압축 된 스파 스로드 (CSR) 또는 압축 행 스토리지 (CRS) 형식은 각각 0이 아닌 값, 행의 범위 및 열 지수를 포함하는 3 개의 (1 차원) 배열만큼 행렬 M을 나타냅니다.COO와 비슷하지만 행 지수를 압축하므로 이름입니다.이 형식은 빠른 행 액세스 및 매트릭스 벡터 곱셈 (MX)을 허용합니다.

Answer 8

희소 행렬을 구현하는 가장 좋은 방법은 구현하지 않는 것입니다. 적어도 직접 구현하는 것은 아닙니다.나는 정말 거대한 행렬을 처리할 수 있는 BLAS(LAPACK의 일부라고 생각함)를 제안하고 싶습니다.

Answer 9

[a][b][c]...[w][x][y][z] 값만 중요하므로 인덱스 자체만 저장하고 거의 모든 곳에 있는 값 1은 저장하지 않습니다. 동일 + 해시할 방법이 없습니다.차원의 저주가 존재한다는 점을 염두에 두고 NIST나 Boost를 사용하여 불필요한 실수를 피하려면 최소한 해당 소스를 읽어 보시기 바랍니다.

작업이 알 수 없는 데이터 세트의 시간 의존성 분포와 매개변수적 경향을 포착해야 하는 경우 단일 값 루트가 있는 맵 또는 B-트리는 아마도 실용적이지 않을 것입니다.모든 1개 값에 대해 순서(표시에 대한 민감성)가 런타임 시 시간 영역 축소에 종속될 수 있는 경우 해시된 인덱스 자체만 저장할 수 있습니다.1 이외의 0이 아닌 값은 거의 없기 때문에 이에 대한 확실한 후보는 쉽게 찾고 이해할 수 있는 데이터 구조입니다.데이터 세트가 정말 광대한 크기라면 파일/디스크/영속성 관리를 직접 관리하는 일종의 슬라이딩 창을 제안하고 필요에 따라 데이터 부분을 범위로 이동합니다.(이해할 수 있는 코드 작성) 작업 그룹에 실제 솔루션을 제공하기로 약속한 경우 그렇게 하지 않으면 점심을 빼앗는 유일한 목표를 가진 소비자급 운영 체제의 자비에 빠지게 됩니다.

Answer 10

다음은 행/열의 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, 그러나 변경 가능하게 만들 수 있습니다.꼭 바꾸세요 std::vector 에게 std::set 합리적이고 효율적인 "삽입"(0을 0이 아닌 값으로 변경)을 원하는 경우.

Answer 11

나는 다음과 같은 일을 제안할 것입니다:

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인 모든 항목을 자동으로 건너뛰고 지웁니다.