लिए सबसे कारगर तरीका सी ++

Question

का उपयोग कर मैं वर्तमान में एक समाधान है, लेकिन मुझे लगता है यह रूप में कुशल नहीं है के रूप में यह इस समस्या का हो सकता है दो क्रमबद्ध सरणियों में मिलान मूल्यों का सूचकांक लगता है, इसलिए मैं अगर वहाँ के लिए एक तेज तरीका है देखना चाहता हूँ इस।

मैं दो सरणियों (std :: उदाहरण के लिए वैक्टर) है। दोनों सरणी में केवल अद्वितीय पूर्णांक मान होते हैं जो क्रमबद्ध होते हैं लेकिन मूल्य में भिन्न होते हैं, यानी: 1,4,12,13 ... मैं जो पूछना चाहता हूं वह है कि मैं इंडेक्स को उन सरणी में से एक में ढूंढ सकता हूं जहां मूल्य समान हैं। उदाहरण के लिए, array1 में 1,4,12,13 मान हैं और array2 के मूल्य 2,12,14,16 हैं। पहला मिलान मूल्य सूचकांक array2 में 1 है। सरणी में इंडेक्स महत्वपूर्ण है क्योंकि मेरे पास अन्य एरे हैं जिनमें डेटा है जो इस इंडेक्स का उपयोग करेगा जो "मैचों" का उपयोग करेगा।

मैं सरणियों का उपयोग कर तक ही सीमित नहीं रहा हूँ, नक्शे के लिए संभव हो रहे हैं। मैं केवल एक बार दो सरणी की तुलना कर रहा हूं। पहले मिलान पास के बाद उन्हें फिर से उपयोग नहीं किया जाएगा। किसी भी सरणी में बड़ी संख्या में मूल्य (300,000+) हो सकते हैं, लेकिन हमेशा समान संख्या में मूल्य नहीं होते हैं (जो चीजों को अधिक आसान बनाते हैं)

खराब मामला एक रैखिक खोज ओ (एन^2 है))। मानचित्र का उपयोग करने से मुझे बेहतर ओ (लॉग एन) मिल जाएगा, लेकिन मैं अभी भी एक सरणी को मूल्य, सूचकांक जोड़े के मानचित्र में परिवर्तित कर दूंगा।

मैं वर्तमान में किसी भी कंटेनर प्रकार रूपांतरण नहीं कर करना है यह क्या है। दो सरणी के छोटे से ऊपर लूप। बड़े सरणी (array2) के वर्तमान तत्व के साथ छोटे सरणी (array1) के वर्तमान तत्व की तुलना करें। यदि array1 तत्व मान सरणी 2 तत्व मान से बड़ा है, तो सरणी 1 तत्व मान (जबकि लूप) से बड़ा नहीं है, तब तक सरणी 2 के लिए अनुक्रमणिका को बढ़ाएं। फिर, यदि array1 तत्व मान array2 तत्व से छोटा है, तो अगले लूप पुनरावृत्ति पर जाएं और फिर से शुरू करें। अन्यथा वे बराबर होना चाहिए और मेरे पास मिलान सूचकांक के सरणी के लिए मेरी अनुक्रमणिका है।

तो यह पाश में, मैं सबसे अच्छा हे (एन) यदि सभी मूल्यों मैच में और बदतर हे (2n) यदि कोई भी मैच में हूँ। तो मैं सोच रहा हूं कि वहां कुछ तेज है या नहीं? यह सुनिश्चित करना मुश्किल है कि कितने बार दो सरणी मिलेंगे, लेकिन मैं जिस तरह से अधिकतर सरणीओं की तरफ झुकता हूं, वैसे ही अधिकतर मैच नहीं होंगे।

मुझे आशा है कि मैं इस समस्या काफी अच्छी तरह से समझाया और मैं किसी भी प्रतिक्रिया या इस सुधारने की युक्तियों की सराहना करते हैं।

कोड उदाहरण:

std::vector<int> array1 = {4,6,12,34}; 
std::vector<int> array2 = {1,3,6,34,40}; 

for(unsigned int i=0, z=0; i < array1.size(); i++) 
{ 
    int value1 = array1[i]; 
    while(value1 > array2[z] && z < array2.size()) 
     z++; 

    if (z >= array2.size()) 
     break; // reached end of array2 

    if (value1 < array2[z]) 
     continue; 

    // we have a match, i and z indices have same value 

} 

परिणाम array1 = [1,3] के लिए और array2 = [2,3]

Answer 1

मैंने इस फ़ंक्शन के कार्यान्वयन को एक एल्गोरिदम का उपयोग करके लिखा है जो छोटे रैखिक विलय की तुलना में स्पैस वितरण के साथ बेहतर प्रदर्शन करता है।

वितरणों के लिए, कि इसी तरह ^† हैं, यह हे (एन) जटिलता है, लेकिन पर्वतमाला जहां वितरण बहुत अलग हैं, यह रेखीय नीचे प्रदर्शन करना चाहिए, आ हे (लॉग एन) इष्टतम मामलों में। हालांकि, मैं यह साबित करने में सक्षम नहीं था कि सबसे खराब मामला ओ (एन लॉग एन) से बेहतर नहीं है। दूसरी तरफ, मैं उस सबसे बुरे मामले को खोजने में सक्षम नहीं हूं।

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

^†तक समान वितरण, मेरा मतलब है कि सरणियों की जोड़ी कई क्रॉसिंग है। को पार करते हुए, मेरा मतलब एक बिंदु है जहां आप एक सरणी से दूसरे में स्विच करेंगे यदि आप दो सरणी क्रमबद्ध क्रम में एक साथ मर्ज करना चाहते थे।

#include <algorithm> 
#include <iterator> 
#include <utility> 

// helper structure for the search 
template<class Range, class Out> 
struct search_data { 
    // is any there clearer way to get iterator that might be either 
    // a Range::const_iterator or const T*? 
    using iterator = decltype(std::cbegin(std::declval<Range&>())); 
    iterator curr; 
    const iterator begin, end; 
    Out out; 
}; 

template<class Range, class Out> 
auto init_search_data(const Range& range, Out out) { 
    return search_data<Range, Out>{ 
     std::begin(range), 
     std::begin(range), 
     std::end(range), 
     out, 
    }; 
} 

template<class Range, class Out1, class Out2> 
void match_indices(const Range& in1, const Range& in2, Out1 out1, Out2 out2) { 
    auto search_data1 = init_search_data(in1, out1); 
    auto search_data2 = init_search_data(in2, out2); 

    // initial order is arbitrary 
    auto lesser = &search_data1; 
    auto greater = &search_data2; 

    // if either range is exhausted, we are finished 
    while(lesser->curr != lesser->end 
      && greater->curr != greater->end) { 
     // difference of first values in each range 
     auto delta = *greater->curr - *lesser->curr; 

     if(!delta) { // matching value was found 
      // store both results and increment the iterators 
      *lesser->out++ = std::distance(lesser->begin, lesser->curr++); 
      *greater->out++ = std::distance(greater->begin, greater->curr++); 
      continue; // then start a new iteraton 
     } 

     if(delta < 0) { // set the order of ranges by their first value 
      std::swap(lesser, greater); 
      delta = -delta; // delta is always positive after this 
     } 

     // next crossing cannot be farther than the delta 
     // this assumption has following pre-requisites: 
     // range is sorted, values are integers, values in the range are unique 
     auto range_left = std::distance(lesser->curr, lesser->end); 
     auto upper_limit = 
      std::min(range_left, static_cast<decltype(range_left)>(delta)); 

     // exponential search for a sub range where the value at upper bound 
     // is greater than target, and value at lower bound is lesser 
     auto target = *greater->curr; 
     auto lower = lesser->curr; 
     auto upper = std::next(lower, upper_limit); 
     for(int i = 1; i < upper_limit; i *= 2) { 
      auto guess = std::next(lower, i); 
      if(*guess >= target) { 
       upper = guess; 
       break; 
      } 
      lower = guess; 
     } 

     // skip all values in lesser, 
     // that are less than the least value in greater 
     lesser->curr = std::lower_bound(lower, upper, target); 
    } 
} 

#include <iostream> 
#include <vector> 

int main() { 
    std::vector<int> array1 = {4,6,12,34}; 
    std::vector<int> array2 = {1,3,6,34}; 

    std::vector<std::size_t> indices1; 
    std::vector<std::size_t> indices2; 

    match_indices(array1, array2, 
        std::back_inserter(indices1), 
        std::back_inserter(indices2)); 

    std::cout << "indices in array1: "; 
    for(std::vector<int>::size_type i : indices1) 
     std::cout << i << ' '; 

    std::cout << "\nindices in array2: "; 
    for(std::vector<int>::size_type i : indices2) 
     std::cout << i << ' '; 
    std::cout << std::endl; 
} 

Answer 2

के लिए अनुक्रमित मिलान किया जाएगा के बाद से पहले से ही सरणियों हल कर रहे हैं तो आप सिर्फ उपयोग कर सकते हैं विलय के विलय चरण की तरह कुछ बहुत कुछ। यह सिर्फ प्रत्येक सरणी के मुख्य तत्व को देखता है, और निचले तत्व को छोड़ देता है (अगला तत्व सिर बन जाता है)। जब आप एक मैच पाते हैं तो रोकें (या जब कोई सरणी समाप्त हो जाती है, तो कोई मिलान नहीं दर्शाता है)।

यह ओ (एन) है और सबसे तेज़ आप मनमाना विचलन के लिए कर सकते हैं। कुछ क्लस्टर्ड वितरणों के साथ हमेशा "आगे छोड़ें" दृष्टिकोण का उपयोग अगले तत्व को हमेशा देखने के बजाय किया जा सकता है। यह कुछ वितरण के लिए ओ (एन) चलने के समय से बेहतर हो सकता है। उदाहरण के लिए, एरे 1,2,3,4,5 और 10,11,12,13,14 दिए गए एक एल्गोरिदम निर्धारित कर सकता है कि एक तुलना के रूप में कम से कम कोई मिलान नहीं मिला (5 < 10)।

Answer 3

संग्रहित संख्याओं की सीमा क्या है?

मेरा मतलब है, आप कहते हैं कि संख्या पूर्णांक, क्रमबद्ध, और स्पैस (यानी अनुक्रमिक) हैं, और उनमें से 300,000 से अधिक हो सकते हैं, लेकिन उनकी वास्तविक सीमा क्या है?

कारण यह है कि मैं पूछता हूँ कि, अगर वहाँ एक यथोचित छोटे ऊपरी सीमा, यू, है (जैसे कि, यू = 500,000), सबसे तेज और सबसे समीचीन समाधान सिर्फ सूचकांक के रूप में मानों का उपयोग कर हो सकता है । हां, आप स्मृति बर्बाद कर सकते हैं, लेकिन 4 * u वास्तव में बहुत सारी मेमोरी है? यह आपके एप्लिकेशन और आपके लक्षित प्लेटफ़ॉर्म पर निर्भर करता है (यानी यदि यह स्मृति-बाधित एम्बेडेड सिस्टम के लिए है, तो आपके पास 32 जीआईबी रैम वाला लैपटॉप होने की तुलना में एक अच्छा विचार होने की संभावना कम है)।

बेशक, यदि मूल्य 0-2^31-1 से अधिक समान रूप से फैले हुए हैं, तो यह कच्चा विचार आकर्षक नहीं है, लेकिन शायद इनपुट मानों के गुण हैं जिन्हें आप अन्य का शोषण कर सकते हैं सीमा से। आप एक काफी सरल हैश फ़ंक्शन को हाथ से लिखने में सक्षम हो सकते हैं।

इस बात पर विचार करने योग्य एक और बात यह है कि क्या आपको वास्तव में सूचकांक को तुरंत पुनर्प्राप्त करने में सक्षम होना चाहिए या यदि यह केवल यह बताने में मदद करता है कि सूचकांक अन्य सरणी में मौजूद है या नहीं। किसी विशेष इंडेक्स में कोई मान मौजूद है या नहीं, केवल एक बिट की आवश्यकता है, इसलिए आपके पास 32x कम मेमोरी (यानी 5 एलएसबी से मास्क का उपयोग करके इनपुट मानों की सीमा का बिटमैप हो सकता है और थोड़ी स्थिति के रूप में इसका उपयोग करें, फिर शेष को स्थानांतरित करें 27 बिट्स 5 स्थानों को सही और एक सरणी अनुक्रमणिका के रूप में उपयोग करें)।

अंत में, एक हाइब्रिड दृष्टिकोण पर विचार करने लायक हो सकता है, जहां आप तय करते हैं कि आप कितनी मेमोरी का उपयोग करने के लिए तैयार हैं (कहें कि आप 256 केआईबी तय करते हैं, जो कि 64 केआई 4-बाइट पूर्णांक के अनुरूप है) तो इसे लुकअप-टेबल के रूप में उपयोग करें बहुत छोटी उप-समस्याओं में। मान लें कि आपके पास 300,000 मूल्य हैं जिनके एलएसबी बहुत समान रूप से वितरित किए जाते हैं। फिर आप 16 एलएसबी का उपयोग इंडेक्स के रूप में सूचियों की एक लुकअप-टेबल में कर सकते हैं जो औसत (केवल औसतन) 4 या 5 तत्व लंबे होते हैं, जिन्हें आप अन्य माध्यमों से खोज सकते हैं। कुछ साल पहले, मैंने कुछ सिमुलेशन सॉफ़्टवेयर पर काम किया था जिसमें 200,000,000 कोशिकाएं थीं, प्रत्येक सेल आईडी के साथ; कुछ उपयोगिता कार्यक्षमता आईडी द्वारा कोशिकाओं की पहचान करने के लिए एक बाइनरी खोज का उपयोग किया। हम इस रणनीति के साथ इसे महत्वपूर्ण और गैर-घुसपैठ कर सकते थे। एक आदर्श समाधान नहीं है, लेकिन एक महान सुधार है। (यदि एलएसबी समान रूप से वितरित नहीं होते हैं, तो हो सकता है कि यह एक ऐसी संपत्ति है जिसका आप शोषण कर सकते हैं या हो सकता है कि आप बिट्स की एक श्रृंखला चुन सकें, या कुछ हैशिंग करें।)

मुझे लगता है कि अपशॉट "किसी प्रकार पर विचार करें हैशिंग ", यहां तक ​​कि" पहचान हैश "या सरल मास्किंग/मॉड्यूलो थोड़ा सा" आपका समाधान पूरी तरह से सामान्य नहीं होना चाहिए "और कुछ" आपका समाधान पूरी तरह से अंतरिक्ष कुशल नहीं होना चाहिए "सॉस पर शीर्ष।