संचयी मूल्यों को रखने के लिए एक अच्छा डेटास्ट्रक्चर क्या है?

Question

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

उदाहरण मेरी जरूरत के बारे में अधिक प्रकाश डाला सकता है:

मैं एक (2,3,5) मानों की सूची है। संचयी मूल्यों को देखते समय यह सूची (2,5,10) होगी।

अब मैं सूची की शुरुआत में 1 जोड़ूंगा और (1,2,3,5) और संचयी शर्तों (1,3,6,11) प्राप्त करूंगा।

मुझे केवल संचयी मूल्यों को देखने की आवश्यकता है, मुझे 1,2,3,5 में कोई दिलचस्पी नहीं है। मैं जल्दी से, की स्थिति में डालने की स्थिति को दूर करने के लिए सक्षम होना चाहिए और यह सब जल्दी से (संचयी सरणी अद्यतन करना चाहिए आदर्श पूरे सरणी भर पुनरावृत्ति और मूल्यों recalculating के बिना।

कोई भी विचार या संकेत?

@ क्रिस्टो (टिप्पणी करने में बहुत लंबा): यह स्पष्ट करने के लिए कि ऋणात्मक संख्या कुल योग मूल्य को अर्थहीन क्यों बनाती हैं, कृपया इस उदाहरण का पालन करें।

1 के बाद 1 डालें। Sum 0 से(1, - 1) // (1,0) डालने के बाद 3 डालें -3। योग 3 है तो 0. (1,3, -1, -3) // (1,4,3,0) डालने के बाद 2 डालें 2। योग 2 है 0. (1,3,2, -1, -2, -3) // (1,4,6,5,3,0)

यदि मेरा "जादू संख्या" 4 था कुल योग मुझे नहीं बताएगा कि मैंने इसे पार कर लिया है या नहीं।

पीएस: इसका मुख्य कारण यह बताने में सक्षम होना है कि क्या मैं एक निश्चित मूल्य और श्रृंखला में कहां गया हूं।

Answer 1

एकमात्र अनुकूलन जिसे मैं सोच सकता हूं संचयी सूची का 'आलसी' मूल्यांकन करना है।

स्रोत मानों की अपनी सूची के अतिरिक्त, सटीक संचयी सूची में उच्चतम स्थिति का ट्रैक रखें। यदि आपको उस से अधिक संख्या की आवश्यकता है तो आप सूची में चलते हैं, मानों को अपडेट करते हैं, और अनुक्रमणिका।

 
idx values  cumulative operation 
3 (2,3,5)  (2, 5, 10) 
0 (1,2,3,5) (X,X,X,X)  insert 1 at 0 
3 (1,2,3,5) (1,3,6,X)  look for value over 5  
3 (1,2,3,5,4) (1,3,6,X,X) insert 4 at 4 

कोर्स हैं, तो यह अभ्यस्त आप अच्छी की एक पूरी बहुत कुछ कर अगर आप आम तौर पर आइटम सूची में जल्दी एक द्विआधारी खोज वृक्ष अतिरिक्त संपत्ति को नोड्स को शामिल के साथ जोड़ रहे हैं ....

Answer 2

cumulative frequency table देखें।

Answer 3

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

1. मूल सूची रखें, और प्रत्येक परिवर्तन पर संचयी पुनर्मूल्यांकन करें।

2. केवल संचयी सूची रखने के लिए, और केवल इसे करने के लिए जोड़ सकते हैं या जैसे कार्यों का उपयोग करके हटा दें:

   • जोड़ें (आइटम, स्थिति डिफ़ॉल्ट सूची का अंत है) आइटम के मूल्य शुरू करने जोड़ना होगा स्थिति -1 से।
   • हटाएं (स्थिति) मूल मान की गणना दो संख्याओं को घटाएगी, फिर आइटम को हटाने से पहले शेष सूची से इस संख्या को कम कर देगा।

   जोड़ें 2: (2) रिक्त सूची में 2 जोड़ता है।

   जोड़ें 3: (2,5) सूची के अंत में पूर्व तत्व (2) में 3 जोड़ता है।

   जोड़ें 5: (2,5,10) पूर्व तत्व (5) में सूची के अंत में 5 जोड़ता है।

   प्रारंभ में 1 जोड़ें: (1,3,6,11) सूची की शुरुआत में 1 जोड़ता है, और 1 तक अंत तक वृद्धि (कोई पूर्व तत्व नहीं)।

   दूसरी स्थिति में 7 जोड़ें: (1,8,11,14,19) 7 जोड़ता है और अंत तक 7 तक वृद्धि करता है (कोई पूर्व तत्व नहीं)।

   3 स्थिति हटाएँ(): (1,8,3,8) , मूल्य मिलता है, इसे हटा आराम करने के लिए मूल्य जोड़ने।

इस तरह से मूल मूल्यों को बनाए रखने के बिना यह सब सिंक्रनाइज़ किया जाएगा।

Answer 4

सी ++ शर्तों का उपयोग करके, क्या आप डेटा के लिए std::list (मध्य में आसान आवेषण/हटाएं) या std::set (हमेशा सॉर्ट किए गए) और एक चर को योग रखने के लिए दूर कर सकते हैं? प्रत्येक सम्मिलित/निकालने पर, आप योग को उचित के रूप में संशोधित करते हैं। योग आपके संचयी सूची में उच्चतम संख्या का प्रतिनिधित्व करता है। केवल तभी जब आप अपने जादू संख्या को फेंक देते हैं, तो आपको यह पता लगाने के लिए कुछ एल्गोरिदमिक काम करने की आवश्यकता होती है कि आप कहां फेंकते हैं।

अद्यतन:

अपनी नई जानकारी के आधार पर मैंने कई शॉर्टकट उपलब्ध नहीं दिख रहा। आपको बीच से अक्सर डालने या निकालने की आवश्यकता होती है, जिससे कि कुछ प्रकार के लिंक किए गए सूची दृष्टिकोण का सुझाव मिलता है। आप बदली गई सूची के केवल हिस्सों को अपडेट करके गणना की थोड़ी सी बचत बचा सकते हैं। L मानों की सूची और n सूची में वांछित स्थान होने दें। स्थान n पर मूल्य x सम्मिलित करने के लिए:

• स्थान पर मूल्य x + L(n-1) डालें n
• इस नए n
• रोक के बाद सभी तत्वों को x जोड़े अगर आप अपने जादुई संख्या

खराब प्रक्रिया को हटाने के लिए एक ही है, सिवाय इसके कि आप सभी बाद के मूल्यों से घटाएं। इस तरह, यदि आप शुरुआत के करीब डालें तो आप केवल बहुत काम कर रहे हैं।

Answer 5

सी # में, मैं सभी वास्तविक मानों को एक सूची में रखूंगा, और संचयी मानों के माध्यम से लूप को कस्टम इटरेटर का उपयोग करूंगा।

आप केवल उस बिंदु तक फिर से गणना करेंगे जहां इटेटरेटर आपको बताता है कि आपने अपनी सीमा पार कर ली है (जाहिर है, आपको इसके लिए कोड करना होगा)।

मुझे लगता है कि मान यह है कि जब तक सूची में पुनरावृत्ति करने का समय न हो, तब तक आप कोई गणना किए बिना जोड़/हटा सकते हैं (जो मुझे लगता है कि आपको कट ऑफ नंबर खोजने के लिए वैसे भी करना है)।

Answer 6

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

Answer 7

• आप संचयी आवृत्ति के लिए एक डेटा संरचना देख सकते हैं Binary Indexed Trees

• आप तय सा श्रेणियों में अपने मूल्य सीमा तोड़ सकते हैं। पूर्व। 3 अंतराल:

  #define NUM (1<<24) // max value in your data set 
  #define BITS0 8 
  #define BITS1 8 
  int cum0[NUM >> (BITS0+BITS1)]; // sum of cum1 
  int cum1[NUM >> BITS1]; // sum of count 
  int count[NUM]; 
  
  int add(id, val) { // add a value 
      cum0[id >> (BITS0+BITS1)] += val; 
      cum1[id >> BITS1] += val; 
      count[id] += val;      
  } 
  
  int cumvalue(int id) { int cum = 0; // return cum value at index id   
      for(i = 0; i < (id >> (BITS0+BITS1));i++) cum += cum0[i]; i <<= BITS0; 
      for(i = (id & ~((1 << (BITS0+BITS1))-1)) >> BITS1; i < (id >> BITS1); i++) cum+= cum1[i]; i <<= BITS1; 
      for(i = id & ~((1 << BITS1) -1); i < id; i++) cum += count[i];    
      return cum; 
  }