ما هي أفضل طريقة لإنشاء متفرق مجموعة في C++?

Question

أنا أعمل على مشروع يتطلب التلاعب هائلة المصفوفات ، على وجه التحديد الهرمي الجمع عن حباك الحساب.

باختصار, لا تحتاج إلى تتبع عدد صغير نسبيا من القيم (عادة ما تكون القيمة 1 و في حالات نادرة أكثر من 1) في بحر من الأصفار في المصفوفة (صفيف متعددة الأبعاد).

متفرق مجموعة يسمح للمستخدم بتخزين عدد قليل من القيم ، وتحمل كل معرف السجلات قيمة محددة مسبقا.لأنه ليس جسديا وربما لتخزين جميع القيم في الذاكرة ، أحتاج إلى مخزن فقط عدد قليل من العناصر غير الصفر.هذا يمكن أن يكون عدة ملايين.

السرعة هي أولوية كبيرة ، كما أود أن حيوي اختيار عدد من المتغيرات في الصف في وقت التشغيل.

أنا أعمل حاليا على نظام يستخدم شجرة البحث الثنائية (b-شجرة) لتخزين الإدخالات.لا أحد يعرف أفضل ؟

Answer 1

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;

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

دفعة لديه قالب تنفيذ بلاس يسمى uBLAS الذي يحتوي على مصفوفة متفرق.

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

Eigen هو C++ الجبر الخطي المكتبة التي لديه تنفيذ من مصفوفة متفرق.حتى أنها تدعم مصفوفة العمليات يحلون (لو التعميل الخ) التي هي الأمثل متفرق المصفوفات.

Answer 7

قائمة كاملة من الحلول التي يمكن العثور عليها في ويكيبيديا.للراحة, لقد نقلت الفروع ذات الصلة على النحو التالي.

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

قاموس مفاتيح (دوك)

دوك يتكون من القاموس الذي خرائط (صف وعمود)-أزواج قيمة العناصر.العناصر المفقودة من قاموس تعتبر صفر.شكل جيد تدريجيا بناء مصفوفة متفرق في ترتيب عشوائي ، ولكن الفقراء بالتكرار على القيم غير الصفرية في المعجمية النظام.عادة ما يبني مصفوفة في هذا الشكل ثم يحول إلى آخر أكثر كفاءة تنسيق للمعالجة.[1]

قائمة من قوائم (ليل)

ليل مخازن قائمة واحدة في صف واحد مع كل دخول تحتوي على عمود مؤشر القيمة.عادة, هذه الإدخالات يتم الاحتفاظ بها مرتبة حسب عمود مؤشر لسرعة البحث.هذا هو شكل آخر جيد تدريجي مصفوفة البناء.[2]

تنسيق قائمة (COO)

COO بتخزين قائمة (صف أو عمود القيمة) الصفوف.ومن الناحية المثالية, إدخالات يتم فرز (قبل الصف المؤشر ، ثم عمود مؤشر) إلى تحسين الوصول العشوائي مرات.هذا هو شكل آخر وهو أمر جيد بالنسبة تدريجي مصفوفة البناء.[3]

مضغوط متفرق صف (المسؤولية الاجتماعية للشركات ، CRS أو ييل تنسيق)

المضغوط متفرق صف (CSR) أو مضغوط الصف التخزين (CRS) الشكل تمثل مصفوفة M قبل ثلاثة (أحادية البعد) المصفوفات ، على التوالي تحتوي على قيم صفرية, حدود الصفوف والأعمدة المؤشرات.فإنه يشبه سجع ، ولكن يضغط على التوالي المؤشرات ، ومن ثم الاسم.هذا الشكل يسمح الصف سريع الوصول إلى مصفوفة-ناقلات الضرب (Mx).

Answer 8

أفضل طريقة لتنفيذ متفرق المصفوفات هو عدم تنفيذها - على الأقل ليس على الجهاز الخاص بك.أود أن أقترح أن بلاس (والتي أعتقد أنها جزء من LAPACK) والتي يمكن التعامل مع ضخمة حقا المصفوفات.

Answer 9

منذ فقط القيم [أ][ب][ج]...[w][خ][ذ][ض] هي نتيجة, نحن فقط تخزين indice أنفسهم ، وليس القيمة 1 الذي هو في كل مكان تقريبا - دائما نفس + لا توجد طريقة تجزئة ذلك.مشيرا إلى أن لعنة الأبعاد هو الحاضر ، أقترح الذهاب مع بعض إنشاء أداة نيست أو دفعة على الأقل قراءة المصادر أن للتحايل وغني عن خطأ.

إذا كان العمل يحتاج إلى التقاط الزمنية الاعتماد توزيع و حدودي ميول غير معروف مجموعات البيانات ، ثم خريطة أو ب-شجرة مع uni-قيمة الجذر هو على الارجح ليست عملية.يمكننا تخزين فقط indice أنفسهم ، تجزئته إذا طلب ( حساسية للعرض ) يمكن أن تخضع إلى الحد من الوقت المجال في وقت التشغيل ، لكل 1 القيم.لأن القيم غير الصفرية غير قليلة من مرشح واضح لمن هو مهما البيانات هيكل يمكنك أن تجد بسهولة وفهم.إذا كانت مجموعة البيانات واسع الكون الحجم أقترح نوعا من انزلاق النافذة التي تدير ملف / قرص / الثابتة-io نفسك تتحرك أجزاء من البيانات في النطاق حسب الحاجة.( كتابة التعليمات البرمجية التي يمكنك أن تفهم ) إذا كنت تحت التزام أن توفر الحل الفعلي لمجموعة العمل ، عدم القيام بذلك يترك لك في رحمة المستهلك الصف أنظمة التشغيل التي يكون الهدف الوحيد من تناول الغداء الخاص بك بعيدا عنك.

Answer 10

هنا هو بسيط نسبيا التنفيذ التي يجب أن توفر معقول سريع بحث (باستخدام جدول تجزئة) وكذلك التكرار السريع على العناصر غير الصفر في الصف/العمود.

// 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 إذا كنت تريد معقول كفاءة "الملاحق" (تغيير صفر إلى غير الصفر).

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.