नेस्टेड छोरों सपाट/घटते जटिलता - पूरक जोड़े एल्गोरिथ्म

Question

मैं हाल ही में अजगर में कुछ कार्य हल करने की कोशिश कर रहा था और मैं समाधान हे की जटिलता के लिए लगता है कि मिल गया है (एन एन लॉग इन करें) गिनती है, लेकिन मैं इस पर विश्वास कुछ इनपुट के लिए बहुत अक्षम है (जैसे पहला पैरामीटर 0 और pairs शून्य की बहुत लंबी सूची होने के कारण)।

इसमें for लूप के तीन स्तर भी हैं। मेरा मानना ​​है कि यह अनुकूलित किया जा सकता है, लेकिन इस समय मैं इसे और अधिक अनुकूलित नहीं कर सकते, मैं शायद अभी-अभी कुछ स्पष्ट याद आ रही है;)

तो, मूल रूप से, समस्या इस प्रकार है:

पूर्णांक को देखते हुए सूची (values), समारोह अनुक्रमित 'जोड़े निम्नलिखित शर्त पूरी करने की संख्या वापस जाने के लिए की जरूरत है:

• , मान लें एक सूचकांक जोड़ी (index1, index2) की तरह एक टपल है की सुविधा देता है
तो
• values[index1] == complementary_diff - values[index2] मैं सच है,

उदाहरण: हैं [1, 3, -4, 0, -3, 5]values के रूप में और 1complementary_diff के रूप में की तरह एक सूची दी, समारोह 4 लौटना चाहिए (जो अनुक्रमित 'जोड़े की निम्न सूची की लंबाई है: [(0, 3), (2, 5), (3, 0), (5, 2)])। जैसा कि मैंने कहा - - कुछ मामलों में यह इसकी जटिलता के सन्निकटन O (n लॉग ऑन n के बावजूद बहुत धीरे धीरे चला सकते हैं,

यह वही है मैं अब तक है, यह पूरी तरह से समय की सबसे काम करना चाहिए, लेकिन है) (ऐसा लगता है कि निराशावादी जटिलता ओ (एन^2)) है।

def complementary_pairs_number (complementary_diff, values): 
    value_key = {} # dictionary storing indexes indexed by values 
    for index, item in enumerate(values): 
     try: 
      value_key[item].append(index) 
     except (KeyError,): # the item has not been found in value_key's keys 
      value_key[item] = [index] 
    key_pairs = set() # key pairs are unique by nature 
    for pos_value in value_key: # iterate through keys of value_key dictionary 
     sym_value = complementary_diff - pos_value 
     if sym_value in value_key: # checks if the symmetric value has been found 
      for i1 in value_key[pos_value]: # iterate through pos_values' indexes 
       for i2 in value_key[sym_value]: # as above, through sym_values 
        # add indexes' pairs or ignore if already added to the set 
        key_pairs.add((i1, i2)) 
        key_pairs.add((i2, i1)) 
    return len(key_pairs) 

दिया उदाहरण के लिए यह है कि तरह बर्ताव करता है:

>>> complementary_pairs_number(1, [1, 3, -4, 0, -3, 5]) 
4 

आप देखते हैं कि कैसे कोड "चपटा" किया जा सकता है या "सरल", मुझे पता है करें।

मुझे यकीन नहीं है कि सिर्फ complementary_diff == 0 आदि की जांच करना सबसे अच्छा तरीका है - यदि आपको लगता है कि कृपया मुझे बताएं।

संपादित करें: मैंने उदाहरण को सही किया है (धन्यवाद, unutbu!)।

Answer 1

मैं इस O(n) को जटिलता को बेहतर बनाता है लगता है:

• value_key.setdefault(item,[]).append(index) try..except ब्लॉकों का उपयोग की तुलना में तेजी है। यह collections.defaultdict(list) का उपयोग करने से भी तेज़ है। (मैंने ipython% timeit के साथ इसका परीक्षण किया।)
• मूल कोड दो बार हर समाधान पर जाता है। प्रत्येक pos_value value_key में, pos_value से जुड़ा एक अद्वितीय sym_value है। समाधान हैं जब sym_value value_key में भी है।लेकिन जब हम value_key, pos_value में चाबियों पर फिर से सक्रिय होते हैं तो अंततः sym_value के मान को आवंटित किया जाता है, जो कोड को पहले से ही गणना की गई गणना को दोहराता है। तो पुराने sym_value के बराबर से pos_value को रोक सकते हैं, तो आप आधे में काम काट सकते हैं। मैंने seen = set() के साथ sym_value एस के ट्रैक को लागू करने के लिए लागू किया।

• कोड केवल len(key_pairs) पर ध्यान देता है, न कि key_pairs स्वयं। तो जोड़े के ट्रैक रखने के बजाय ( set के साथ), हम केवल गिनती का ट्रैक रख सकते हैं (num_pairs के साथ)। इसलिए हम

  num_pairs += 2*len(value_key[pos_value])*len(value_key[sym_value]) 
  

  या आधे के साथ दो आंतरिक के लिए-छोरों की जगह ले सकता है कि "अद्वितीय विकर्ण" मामले, pos_value == sym_value में।

---

def complementary_pairs_number(complementary_diff, values): 
    value_key = {} # dictionary storing indexes indexed by values 
    for index, item in enumerate(values): 
     value_key.setdefault(item,[]).append(index) 
    # print(value_key) 
    num_pairs = 0 
    seen = set() 
    for pos_value in value_key: 
     if pos_value in seen: continue 
     sym_value = complementary_diff - pos_value 
     seen.add(sym_value) 
     if sym_value in value_key: 
      # print(pos_value, sym_value, value_key[pos_value],value_key[sym_value]) 
      n = len(value_key[pos_value])*len(value_key[sym_value]) 
      if pos_value == sym_value: 
       num_pairs += n 
      else: 
       num_pairs += 2*n 
    return num_pairs 

Answer 2

आप इस तरह के कम करने के रूप में कार्यात्मक प्रोग्रामिंग मुहावरों, इस पर गौर कर सकते हैं, आदि

कई बार, नेस्टेड सरणी तर्क कार्यों को कम पसंद का उपयोग कर, नक्शे द्वारा सरल किया जा सकता, अस्वीकार, आदि

उदाहरण के लिए (जावास्क्रिप्ट में) अंडरस्कोर जेएस देखें। मैं पाइथन में बहुत स्मार्ट नहीं हूं, इसलिए मुझे नहीं पता कि वे कौन सी लाइब्रेरी उपलब्ध हैं।

Answer 3

मुझे लगता है कि (कुछ या सभी) इससे मदद करेंगे, लेकिन मुझे यकीन नहीं है कि मैं इसे कैसे साबित करूंगा।

1) मान ले लो और मूल्यों की एक अलग सेट करने के लिए इसे कम करने, प्रत्येक तत्व की गणना (O (n))

2) जिसके परिणामस्वरूप सरणी सॉर्ट रिकॉर्डिंग। (एन लॉग एन)

3) यदि आप बहुत सारी मेमोरी आवंटित कर सकते हैं, तो मुझे लगता है कि आप मूल्यों के साथ एक स्पैस सरणी पॉप्युलेट करने में सक्षम हो सकते हैं - इसलिए यदि मानों की श्रेणी -100: +100 है, तो आवंटित करें [201] की सरणी और कम सेट में मौजूद कोई भी मान बड़े स्पैस सरणी में मान सूचकांक पर एक को पॉप करता है।

4) कोई भी मान जिसे आप जांचना चाहते हैं कि यह आपकी स्थिति को पूरा करता है, अब एक्स-वाई संबंध के अनुसार स्पैस सरणी में इंडेक्स को देखना है और देखें कि कोई मान मौजूद है या नहीं।

5) जैसा कि unutbu ने बताया, यह मामूली सममित है, इसलिए यदि {ए, बी} एक जोड़ी है, तो {बी, ए} है।

Answer 4

मुझे लगता है कि आप खोज से बीजगणित भाग को अलग करके और बेहतर डेटा संरचनाओं का उपयोग करके इसे बेहतर बना सकते हैं।

1. सूची में जाएं और सूची में प्रत्येक आइटम के लिए पूरक diff से घटाएं।

   resultlist[index] = complementary_diff - originallist[index] 
   

   आप या तो मानचित्र या साधारण लूप का उपयोग कर सकते हैं। ->ओ (एन) समय लेता है।

2. देखें कि परिणामी सूची में संख्या मूल सूची में मौजूद है या नहीं।

   • यहाँ, एक अनुभवहीन सूची के साथ, आप वास्तव में O (n^2) मिलेगा, क्योंकि आप जिसके परिणामस्वरूप सूची में आइटम प्रति पूरे मूल सूची के लिए खोज खत्म कर सकते हैं।

   • हालांकि, इस से आपके डेटा को व्यवस्थित करने के बेहतर तरीके हैं। आप मूल सूची अनुसार क्रमबद्ध हो, तो आपकी खोज समय ओ (nlogn + nlogn) = ओ (nlogn), nlogn प्रकार के लिए, और nlogn तत्व प्रति द्विआधारी खोज के लिए को कम करता है।

   • आप आप एक शब्दकोश (या हैश तालिका) में अपनी सूची बना सकते हैं भी होशियार होना चाहते थे और उसके बाद इस कदम हो जाता है O (n + एन) = हे (एन), n शब्दकोश में प्रत्येक तत्व को खोजने के लिए शब्दकोश और * n बनाने के लिए। (* संपादित करें:। * जब से तुम मूल सूची में प्रत्येक मूल्य की विशिष्टता कल्पना नहीं कर सकते आप कितनी बार प्रत्येक मान मूल सूची में प्रकट की गिनती रखने के लिए चाहते हो सकता है।)

इस के साथ

तो अब आप ओ (एन) कुल रनटाइम प्राप्त करते हैं।

अपने उदाहरण का उपयोग करना:

1, [1, 3, -4, 0, -3, 5], 

1. परिणाम सूची उत्पन्न: अब

   >>> resultlist 
   [0, -2, 5, 1, 4, -4]. 
   

2. हम खोज:

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

     >>> original_table 
     {(1,0), (3,1), (-4,2), (0,3), (-3,4), (5,5)} 
     

   • , हैश तालिका में खोज और टपल बनाते हैं।:

     (resultlist_index, original_table[resultlist[resultlist_index]]) 
     

     यह आपके उदाहरण के समाधान जैसा दिखना चाहिए।

3. अब आप केवल टुपल्स की परिणामी सूची की लंबाई पाते हैं।

   example_diff = 1 
   example_values = [1, 3, -4, 0, -3, 5] 
   example2_diff = 1 
   example2_values = [1, 0, 1] 
   
   def complementary_pairs_number(complementary_diff, values): 
       """ 
        Given an integer complement and a list of values count how many pairs 
        of complementary pairs there are in the list. 
       """ 
       print "Input:", complementary_diff, values 
       # Step 1. Result list 
       resultlist = [complementary_diff - value for value in values] 
       print "Result List:", resultlist 
   
       # Step 2. Flatten into dictionary 
       original_table = {} 
       for original_index in xrange(len(values)): 
        if values[original_index] in original_table: 
         original_table[values[original_index]].append(original_index) 
        else: 
         original_table[values[original_index]] = [original_index] 
       print "Flattened dictionary:", original_table 
   
       # Step 2.5 Search through dictionary and count up the resulting pairs. 
       pair_count = 0 
       for resultlist_index in xrange(len(resultlist)): 
        if resultlist[resultlist_index] in original_table: 
         pair_count += len(original_table[resultlist[resultlist_index]]) 
       print "Complementary Pair Count:", pair_count 
   
       # (Optional) Step 2.5 Search through dictionary and create complementary pairs. Adds O(n^2) complexity. 
       pairs = [] 
       for resultlist_index in xrange(len(resultlist)): 
        if resultlist[resultlist_index] in original_table: 
         pairs += [(resultlist_index, original_index) for original_index in 
          original_table[resultlist[resultlist_index]]] 
       print "Complementary Pair Indices:", pairs 
   
       # Step 3 
       return pair_count 
   
   if __name__ == "__main__": 
       complementary_pairs_number(example_diff, example_values) 
       complementary_pairs_number(example2_diff, example2_values) 
   

   आउटपुट::

   $ python complementary.py 
   Input: 1 [1, 3, -4, 0, -3, 5] 
   Result List: [0, -2, 5, 1, 4, -4] 
   Flattened dictionary: {0: 3, 1: 0, 3: 1, 5: 5, -4: 2, -3: 4} 
   Complementary Pair Indices: [(0, 3), (2, 5), (3, 0), (5, 2)] 
   Input: 1 [1, 0, 1] 
   Result List: [0, 1, 0] 
   Flattened dictionary: {0: [1], 1: [0, 2]} 
   Complementary Pair Count: 4 
   Complementary Pair Indices: [(0, 1), (1, 0), (1, 2), (2, 1)] 
   

   धन्यवाद

अब यहाँ कोड है!

Answer 5

संशोधन @unutbu द्वारा प्रदान समाधान:

समस्या 2 इन शब्दकोशों की तुलना करने के लिए कम किया जा सकता:

1. मूल्यों

2. के लिए (complementary_diff पूर्व-परिकलित शब्दकोश - मूल्यों [ i])

   def complementary_pairs_number(complementary_diff, values): 
       value_key = {} # dictionary storing indexes indexed by values 
       for index, item in enumerate(values): 
        value_key.setdefault(item,[]).append(index) 
   
       answer_key = {} # dictionary storing indexes indexed by (complementary_diff - values) 
       for index, item in enumerate(values): 
        answer_key.setdefault((complementary_diff-item),[]).append(index) 
   
       num_pairs = 0 
       print(value_key) 
       print(answer_key) 
       for pos_value in value_key: 
        if pos_value in answer_key: 
         num_pairs+=len(value_key[pos_value])*len(answer_key[pos_value]) 
       return num_pairs