Что такое лучший способ создать разреженный массив в C ++?

голоса
44

Я работаю над проектом, который требует манипуляции огромных матриц, в частности пирамидальных суммирований для расчета копулы.

Короче говоря, мне нужно следить за относительно небольшого числа значений (обычно значения 1, а в редких случаях более чем 1) в море нулей в матрице (многомерном массиве).

Разреженный массив позволяет пользователю хранить небольшое количество значений, и принимают на себя все неопределенные записи, чтобы быть предварительно установленным значением. Так как это физически не возможно хранить все значения в памяти, мне нужно хранить только несколько ненулевых элементов. Это может быть несколько миллионов записей.

Скорость является огромным приоритетом, и я также хотел бы динамически выбирать число переменных в классе во время выполнения.

Сейчас я работаю в системе, которая использует дерево двоичного поиска (б-дерево) для записей магазинов. Кто-нибудь знает о лучшей системе?

Задан 07/08/2008 в 03:29
источник пользователем
На других языках...                            


11 ответов

голоса
25

Для C ++, карта работает хорошо. Несколько миллионов объектов не будет проблемой. 10 миллионов элементов заняли около 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» строки. Мы можем также расширить это решение для более высоких измерений; такие , как для трех измерений произвольного индекса будет выглядеть как «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;
Ответил 07/08/2008 в 03:33
источник пользователем

голоса
16

Подобно тому , как советуют: метод с использованием строк в качестве индексов на самом деле очень медленно. Гораздо более эффективным , но в противном случае аналогичное решение было бы использовать векторы / массивы. Там совершенно нет необходимости писать индексы в строке.

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это на самом деле не очень эффективным , поскольку реализации с точки зрения сбалансированного двоичного дерева поиска. Гораздо лучшие структуры исполнительских данных в этом случае будут (рандомизировано) хэш - таблицей.

Ответил 02/09/2008 в 09:53
источник пользователем

голоса
11

Повышение имеет шаблонную реализацию BLAS называется uBLAS, который содержит разреженную матрицу.

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

Ответил 22/08/2008 в 00:45
источник пользователем

голоса
4

Небольшая деталь в сравнении индекса. Вы должны сделать лексикографическом сравнения, в противном случае:

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

Edit: Так что сравнение, вероятно, следует:

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
Ответил 19/08/2008 в 22:59
источник пользователем

голоса
3

Эйген является ++ линейной алгебры библиотеки C , которая имеет реализацию разреженной матрицы. Он даже поддерживает матричные операции и решатели (LU факторизации и т.д.), которые оптимизированы для разреженных матриц.

Ответил 29/12/2014 в 21:23
источник пользователем

голоса
3

Хэш-таблицы имеют быстрый ввод и посмотреть вверх. Вы можете написать простой хэш-функцию, так как вы знаете, вы иметь дело только с числовыми парами в качестве ключей.

Ответил 07/08/2008 в 04:13
источник пользователем

голоса
2

Полный список решений можно найти в википедии. Для удобства я цитировал соответствующие разделы следующим образом.

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

Словарь ключей (ДОК)

ДОК состоит из словаря, который отображает (строка, столбец) -пар к значению элементов. Элементы, которые отсутствуют в словаре принимаются равными нулю. Формат хорош для постепенного построения разреженной матрицы в случайном порядке, но плохой для итерации ненулевых значений в лексикографическом порядке. Один, как правило, строит матрицу, в этом формате, а затем преобразуется в другой, более эффективный формат для обработки. [1]

Список списков (LIL)

LIL хранит один список для каждой строки, с каждой записью, содержащей индекс столбца и значение. Как правило, эти записи сохранены сортируются по индексу столбца для более быстрого поиска. Это еще один формат хорошо для дополнительного построения матрицы. [2]

Координировать список (COO)

СОО хранит список (строка, столбец, значение) кортежей. В идеале, записи сортируются (по индексу строки, то индекс столбца), чтобы улучшить случайные моменты времени доступа. Это еще один формат, который хорош для инкрементного построения матрицы. [3]

Сжатые редкие строки (КСО, СКИ или Йельский формат)

Сжатый разреженным ряд (CSR), или в формате сжатого хранения строк (АСБ) представляет собой матрицу М на три (одномерных массивов), которые соответственно содержат ненулевые значения, экстенты строк и столбцов индексов. Это похоже на СОО, но сжимает индексы строк, отсюда и название. Этот формат обеспечивает быстрый доступ строки и матрично-векторные умножения (MX).

Ответил 07/12/2016 в 18:06
источник пользователем

голоса
1

Лучший способ реализации разреженных матриц не для их реализации - по крайней мере, не по своему усмотрению. Я хотел бы предложить BLAS (который я думаю, что это часть LAPACK), который может обрабатывать очень большие матрицы.

Ответил 08/08/2008 в 07:11
источник пользователем

голоса
0

Я предложил бы делать что-то вроде:

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.

Ответил 12/10/2016 в 01:31
источник пользователем

голоса
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если вы хотите разумную эффективную «вставку» (изменение нуля до ненулевого).

Ответил 23/06/2014 в 16:59
источник пользователем

голоса
0

Поскольку значения только с [а] [б] [с] ... [ш] [х] [у] [г] являются следствием, мы только хранить Indice сами по себе, а не значение 1, которое является почти везде - всегда то же + нет возможности хэш его. Отмечая, что проклятие размерности присутствует, предложить идти с некоторым установленным NIST инструмента или Boost, по крайней мере читать источники для этого, чтобы обойти ненужные маху.

Если работа должна фиксировать временные распределения зависимости и параметрические тенденции неизвестных наборов данных, а затем карта или B-Tree с унью-значным корнем, вероятно, не практично. Мы можем хранить только Indice себя, перемешанный при заказе (обидчивость для презентации) может подчинять к сокращению временной области во время выполнения для всех 1 значений. Поскольку ненулевые значения, кроме одного мало, очевидным кандидатом для тех, кто является то, что структура данных вы можете легко найти и понять. Если набор данных действительно огромная вселенная размером я предлагаю какую-то скользящее окно, которое управляет файл / диск / настойчивый-Io себя, движущихся частей данных в объеме, как это будет необходимо. (Написание кода, который вы можете понять) Если вы находитесь под обязательством обеспечить фактическое решение рабочей группы, неспособность сделать это оставляет вас на милость операционных систем потребительского класса, которые имеют единственную цель принимая ваш обед от вас.

Ответил 27/09/2009 в 18:52
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more