सी ++ में स्पैस सरणी बनाने का सबसे अच्छा तरीका क्या है?

मैं एक ऐसे प्रोजेक्ट पर काम कर रहा हूं जिसके लिए विशाल मैट्रिस के हेरफेर की आवश्यकता होती है, विशेष रूप से कोपाला गणना के लिए पिरामिड सारांश।

संक्षेप में, मुझे मैट्रिक्स (बहुआयामी सरणी) में शून्य के समुद्र में अपेक्षाकृत कम संख्या में मूल्यों (आमतौर पर 1 का मान, और दुर्लभ मामलों में 1 से अधिक) का ट्रैक रखने की आवश्यकता है।

एक स्पैस सरणी उपयोगकर्ता को कुछ छोटी संख्याओं को स्टोर करने की अनुमति देती है, और सभी अपरिभाषित रिकॉर्ड को पूर्व निर्धारित मान मानती है। चूंकि यह स्मृति में सभी मानों को संग्रहीत करने के लिए शारीरिक रूप से संभवतः नहीं है, इसलिए मुझे केवल कुछ गैर-शून्य तत्वों को स्टोर करने की आवश्यकता है। यह कई मिलियन प्रविष्टियां हो सकती है।

गति एक बड़ी प्राथमिकता है, और मैं रनटाइम पर कक्षा में चर की संख्या को गतिशील रूप से चुनना भी चाहूंगा।

मैं वर्तमान में ऐसी प्रणाली पर काम करता हूं जो प्रविष्टियों को संग्रहीत करने के लिए बाइनरी सर्च पेड़ (बी-पेड़) का उपयोग करता है। क्या किसी को बेहतर प्रणाली के बारे में पता है?

0
ro fr bn

11 उत्तर

हैश टेबल में तेजी से सम्मिलन होता है और देखो। आप एक सरल हैश फ़ंक्शन लिख सकते हैं क्योंकि आप जानते हैं कि आप चाबियाँ के रूप में केवल पूर्णांक जोड़े से निपटेंगे।

0
जोड़ा

सी ++ के लिए, एक नक्शा अच्छी तरह से काम करता है। कई मिलियन वस्तुएं कोई समस्या नहीं होगी। 10 मिलियन वस्तुओं में लगभग 4.4 सेकंड और मेरे कंप्यूटर पर लगभग 57 मेगापिक्सल लिया गया।

मेरा परीक्षण आवेदन निम्नानुसार है:

#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<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 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;
0
जोड़ा
चूंकि इसे एक विस्तारित समय के लिए तय नहीं किया गया था, इसलिए मैंने इसे सही कार्यान्वयन के साथ बदलने की स्वतंत्रता ली।
जोड़ा लेखक celtschk, स्रोत
इस से तत्व सीमा प्राप्त करने के प्रदर्शन के बारे में क्या है या यह जांच रहा है कि सीमा सरणी में पूरी तरह से है या नहीं?
जोड़ा लेखक Ivan G., स्रोत
ऑपरेटर का कार्यान्वयन <�गलत है। ट्रिपल {1,2,3} और ट्रिपल {3,2,1} पर विचार करें, न तो दूसरे से कम होगा। एक सही कार्यान्वयन x के बाद फिर से सभी की बजाय अनुक्रमिक रूप से z जांच करेगा।
जोड़ा लेखक Whanhee, स्रोत
केवल एक लाख तत्वों के लिए सेकंड? यह काफी बुरा लगता है। आप एक हैशिंग समारोह और unordered_map उपयोग करने पर विचार करना चाहिए। बाहर github.com/victorprad/InfiniTAM चेक वे हैश का उपयोग ((एक्स * 73856093u) ^ (y * 19349669u) ^ (जेड * 83492791u)) और अच्छे फ़्रेमदर में एक विरल 3 डी ग्रिड में नमूने के लाखों लोगों को एकीकृत कर सकते हैं।
जोड़ा लेखक masterxilo, स्रोत

स्पैस मैट्रिस को लागू करने का सबसे अच्छा तरीका यह है कि उन्हें लागू न करें - कम से कम अपने आप पर नहीं। मैं बीएलएएस को सुझाव दूंगा (जो मुझे लगता है कि लैपैक का हिस्सा है) जो वास्तव में विशाल मैट्रिक्स को संभाल सकता है।

0
जोड़ा
LAPACK घने matrices के लिए एक पुस्तकालय है। मानक बीएलएएस घने मैट्रिस के लिए भी है। एक स्पैस ब्लास पैकेज (एनआईएसटी के माध्यम से) है लेकिन मानक बीएलएएस के बाद यह अलग है।
जोड़ा लेखक codehippo, स्रोत

यहां एक अपेक्षाकृत सरल कार्यान्वयन है जो एक उचित तेज़ लुकअप (हैश तालिका का उपयोग करके) के साथ-साथ पंक्ति / कॉलम में गैर-शून्य तत्वों पर तेज़ पुनरावृत्ति प्रदान करना चाहिए।

// 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, // 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 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, i.e.: //    //    // ... // 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_ */ 

सादगी के लिए, यह अपरिवर्तनीय है, लेकिन आप इसे उत्परिवर्तनीय बना सकते हैं; यदि आप एक उचित कुशल "सम्मिलन" (एक शून्य को शून्य में बदलना) चाहते हैं तो std :: vector को std :: set में बदलना सुनिश्चित करें।

0
जोड़ा

विकिपीडिया में समाधान की पूरी सूची मिल सकती है। सुविधा के लिए, मैंने प्रासंगिक खंडों को निम्नानुसार उद्धृत किया है।

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

कुंजी का शब्दकोश (DOK)

DOK में एक शब्दकोश होता है जो मानचित्र (पंक्ति, कॉलम) -पियर को जोड़ता है   तत्वों का मूल्य। तत्व जो गायब से गायब हैं   शून्य होने के लिए लिया जाता है। प्रारूप वृद्धि के लिए अच्छा है   यादृच्छिक क्रम में एक स्पैर मैट्रिक्स का निर्माण, लेकिन पुनरावृत्ति के लिए गरीब   शब्दावली क्रम में गैर-शून्य मानों पर। एक आम तौर पर   इस प्रारूप में एक मैट्रिक्स बनाता है और फिर दूसरे में परिवर्तित होता है   प्रसंस्करण के लिए कुशल प्रारूप। [1]

सूचियों की सूची (एलआईएल)

एलआईएल कॉलम युक्त प्रत्येक प्रविष्टि के साथ प्रति पंक्ति एक सूची स्टोर करता है   सूचकांक और मूल्य। आम तौर पर, इन प्रविष्टियों को क्रमबद्ध रखा जाता है   तेजी से लुकअप के लिए कॉलम सूचकांक। यह एक और प्रारूप के लिए अच्छा है   वृद्धिशील मैट्रिक्स निर्माण। [2]

निर्देशांक सूची (सीओओ)

सीओओ (पंक्ति, कॉलम, मूल्य) tuples की एक सूची स्टोर करता है। आदर्श रूप से, प्रविष्टियां   यादृच्छिक पहुंच में सुधार के लिए क्रमबद्ध (पंक्ति सूचकांक, फिर कॉलम अनुक्रमणिका द्वारा) क्रमबद्ध हैं   बार। यह एक और प्रारूप है जो वृद्धिशील मैट्रिक्स के लिए अच्छा है   निर्माण। [3]

संपीड़ित स्पैस पंक्ति (सीएसआर, सीआरएस या येल प्रारूप)

संपीड़ित स्पैस पंक्ति (सीएसआर) या संपीड़ित पंक्ति भंडारण (सीआरएस) प्रारूप   तीन (एक-आयामी) सरणी द्वारा एक मैट्रिक्स एम का प्रतिनिधित्व करता है   क्रमशः nonzero मूल्य, पंक्तियों के विस्तार, और स्तंभ शामिल हैं   सूचकांक। यह सीओओ के समान है, लेकिन इसलिए पंक्ति सूचकांक को संपीड़ित करता है   नाम। यह प्रारूप तेजी से पंक्ति पहुंच और मैट्रिक्स-वेक्टर की अनुमति देता है   गुणा (एमएक्स)।

0
जोड़ा

Eigen is a C++ linear algebra library that has an implementation of a sparse matrix. It even supports matrix operations and solvers (LU factorization etc) that are optimized for sparse matrices.

0
जोड़ा

एक सलाह के रूप में: इंडेक्स के रूप में तारों का उपयोग करने की विधि वास्तव में बहुत धीमी है। वैक्टर / सरणी का उपयोग करने के लिए एक बहुत अधिक कुशल लेकिन अन्यथा समकक्ष समाधान होगा। स्ट्रिंग में इंडेक्स लिखने की बिल्कुल आवश्यकता नहीं है।

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;

हालांकि, एक संतुलित बाइनरी खोज पेड़ के संदर्भ में कार्यान्वयन के कारण map का उपयोग वास्तव में बहुत प्रभावी नहीं है। इस मामले में बहुत बेहतर प्रदर्शन डेटा संरचना एक (यादृच्छिक) हैश तालिका होगी।

0
जोड़ा
@Andrew काफी नहीं है। यह उत्तर सी ++ 11 की भविष्यवाणी करता है, और इसके परिणामस्वरूप std :: unordered_map , लंबे समय तक। आजकल मैं बाद वाले का उपयोग करने की अनुशंसा करता हूं लेकिन यह मेरे उत्तर के लिए ड्रॉप-इन प्रतिस्थापन नहीं है क्योंकि std :: vector std :: हैश के लिए उपयुक्त कार्यान्वयन प्रदान नहीं करता है । उस ने कहा, जब तक कि सूचकांक वास्तव में परिवर्तनीय आकार (जो असंभव है), एक std :: unordered_map > वास्तव में बॉक्स से बाहर काम करना चाहिए (हालांकि इंटरफ़ेस निश्चित रूप से सुधार किया जा सकता है)।
जोड़ा लेखक Konrad Rudolph, स्रोत
उर्फ। unordered_map
जोड़ा लेखक Andrew, स्रोत

बूस्ट में यूबीएलएएस नामक बीएलएएस का एक टेम्पलेट कार्यान्वयन होता है जिसमें एक स्पैर मैट्रिक्स होता है।

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

0
जोड़ा

चूंकि [ए] [बी] [सी] ... [डब्ल्यू] [एक्स] [वाई] [जेड] के साथ केवल मूल्य ही हैं, हम केवल इंडिस को ही स्टोर करते हैं, न कि मूल्य 1 जो कि हर जगह है - हमेशा वही + हैश करने के लिए कोई रास्ता नहीं है। यह देखते हुए कि आयाम का अभिशाप मौजूद है, सुझाव दें कि कुछ स्थापित उपकरण एनआईएसटी या बूस्ट के साथ जाएं, कम से कम अनजान गलती को रोकने के लिए स्रोतों को पढ़ें।

यदि काम को अज्ञात डेटा सेटों के अस्थायी निर्भरता वितरण और पैरामीट्रिक प्रवृत्तियों को कैप्चर करने की आवश्यकता है, तो यूनी-मूल्यवान रूट के साथ एक मानचित्र या बी-ट्री शायद व्यावहारिक नहीं है। हम केवल इंडिस को ही स्टोर कर सकते हैं, अगर ऑर्डरिंग (प्रस्तुति के लिए संवेदनशीलता) सभी 1 मानों के लिए रन-टाइम पर समय डोमेन को कम करने के अधीन हो सकती है। चूंकि गैर-शून्य मान एक से कम हैं, इसलिए उन लोगों के लिए एक स्पष्ट उम्मीदवार जो भी डेटा-संरचना है जिसे आप आसानी से समझ सकते हैं और समझ सकते हैं। यदि डेटा सेट वास्तव में विशाल-ब्रह्मांड आकार का है, तो मैं कुछ प्रकार की स्लाइडिंग विंडो का सुझाव देता हूं जो फ़ाइल / डिस्क / लगातार-अपने आप को प्रबंधित करता है, डेटा के हिस्सों को दायरे में ले जाने की आवश्यकता होती है। (लेखन कोड जिसे आप समझ सकते हैं) यदि आप किसी कार्यकारी समूह को वास्तविक समाधान प्रदान करने के लिए प्रतिबद्ध हैं, तो ऐसा करने में विफलता आपको उपभोक्ता ग्रेड ऑपरेटिंग सिस्टम की दया पर छोड़ देती है, जिसमें आपका लंच आपके से दूर ले जाने का एकमात्र लक्ष्य है।

0
जोड़ा

सूचकांक तुलना में छोटे विवरण। आपको एक शब्दावली तुलना करने की ज़रूरत है, अन्यथा:

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

संपादित करें: तो तुलना शायद यह होनी चाहिए:

return lhs.x
0
जोड़ा

मैं कुछ ऐसा करने का सुझाव दूंगा:

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;
    /* ... */
}

अपने डेटा को स्पैस रखने में मदद के लिए, आप unorderd_map का उप-वर्ग लिखना चाहेंगे, जिसके इटरेटर स्वचालित रूप से 0 के मान वाले किसी आइटम को छोड़कर (मिटा दें)।

0
जोड़ा