मनमानी उप सरणी में सभी वस्तुओं का योग खोजने के लिए सबसे अच्छा एल्गोरिदम क्या है

Question

मुझे कोई समस्या है, और एक ओके-आश समाधान। मुझे आशा है कि वहां एक बेहतर समाधान होगा।

समस्या

मैं लगभग 200,000 पूर्णांकों के साथ एक सरणी है। दो सूचकांक, i1 और i2 को देखते हुए, मुझे i1 और i2 के बीच सभी तत्वों की योग की गणना करने की आवश्यकता है। सरणी में प्रत्येक पूर्णांक 1 और 4 के बीच है। उदाहरण के लिए:

a = [1, 3, 2, 4, 3, 2, 4, 1]; 
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2) 

यह ऑपरेशन लगभग 200,000 बार किया जाएगा, इसलिए बहुत तेज़ होने की आवश्यकता है। लूप के लिए एक साधारण काउंटर ओ (एन) है, और बहुत धीमा है। सरणी निर्माण के बाद कभी संशोधित नहीं होती है, इसलिए अपेक्षाकृत महंगी प्री-प्रोसेसिंग चरण होना ठीक है।

पहले पैड इसकी लंबाई तक शून्य से मूल सरणी दो की एक शक्ति है:

मेरे सबसे अच्छा समाधान अब तक

इस एल्गोरिथ्म हे (लॉग एन) समय में काम करता है। इसके बाद, सरणी को दो बराबर भागों में विभाजित करें और प्रत्येक के योग को संग्रहित करें। फिर सरणी को क्वार्टर में विभाजित करें और प्रत्येक के योग को स्टोर करें। फिर आठवां ऐसा तब तक जारी रखें जब तक कि सरणी को 2 तत्वों में विभाजित नहीं किया जाता है। ऊपर 8-तत्व वाली सरणी के लिए, यह दो कदम उठा लेता:

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])] 
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])] 

फिर दो सूचकांकों को देखते हुए, यह अब हे में subsection_sum बाहर काम करने के (लॉग एन) समय संभव है। उदाहरण के लिए, subsection_sum (ए, 2, 7) == क्वार्टर [1] + हिस्सों [1]।

Answer 1

एक सहायक सरणी पेश करें जिसमें संचयी योग शामिल है। यही है, सहायक सरणी के तत्व i में मूल सरणी के i तत्वों का योग है। उपर्युक्त योग सहायक सहायक सरणी से केवल दो तत्वों का अंतर है। यह परिणाम निरंतर समय, O(1) में परिणाम देगा।

इस प्रश्न में दिए गए subsection_sum समारोह में एक अपरिवर्तनीय पर निर्भर करता है ,:

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2) 

जहाँ मैं i1 <= i2 संभालने हूँ। उलटफेर करने पर, हमने:

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1) 

ध्यान दें कि दाएँ हाथ की ओर पर रकम दोनों 0 से शुरू करते हैं। सभी i के लिए सहायक सरणी को शून्य, subsection_sum(a, 0, i) से रकम के मानों को कैशिंग के रूप में देखा जा सकता है।

Answer 2

आप O(n) अतिरिक्त भंडारण खर्च कर सकते हैं, तो आप एक लुकअप तालिका जिसका i वें तत्व तत्वों के इनपुट सरणी में के माध्यम से i (सम्मिलित) सूचकांक 0 पर योग है बना सकते हैं। स्यूडोकोड में:

def computeLookupTable(arr): 
    let n = arr.length 
    let lookupTable = new Array() 

    lookupTable[0] = arr[0] 

    for i=1 to n: 
     lookupTable[i] = arr[i] + lookupTable[i-1] 

    return lookupTable 

तो फिर तुम अंतर

lookupTable[i2] - lookupTable[i1] 

जो निरंतर समय लगता है लेने के द्वारा i1 और i2 के बीच array के सभी तत्वों का योग की गणना करने के इस तालिका का उपयोग कर सकते हैं।