दो बार एक सरणी के माध्यम से चरणबद्ध करना (उसी सरणी पर नेस्टेड लूप)

Question

मेरे पास डेटा का एक बड़ा सेट है जिसे मैं समय-समय पर 'डी 1' से एक बिंदु से डेटा सेट पर विभिन्न आंकड़ों को निर्धारित करने के लिए चक्र बनाना चाहता हूं भविष्य में समय में 'डी 2'। मूल रूप से, मैं एक डेटाबेस के लिए हर बार जोड़ने के लिए मूल्यों के बीच का अंतर 10 उदाहरण के लिए तुलना में बड़ा है चाहता हूँ:

Datum[] data = x; 
for(Datum d1 : data){ 
    Datum[] tail = y; //From d1 up to 10 elements ahead 
    for(Datum d2 : tail){ 
     //Calculate difference 
     if((d2.val - d1.val) > 10){ 
      //Insert into database 
     } 
    } 
} 

मेरे सवाल है, वहाँ एक बेहतर एल्गोरिथ्म/विधि ऐसा करने के लिए है? चूंकि बाहरी लूप के अगले पुनरावृत्ति में पूंछ के 9 तत्वों का पुन: उपयोग किया जाता है, क्या मैं इससे किसी भी तरह से लाभ उठा सकता हूं? मेरा लक्ष्य यह था कि यह (बिग-ओ नोटेशन) ओ (एन) से बहुत कम हो गया है, लेकिन मैं इसके चारों ओर अपने सिर को लपेट नहीं सकता। आम तौर पर एक डी 1, डी 2 जोड़ी को मानते हैं जो मानदंडों को पूरा करता है इसका मतलब है कि अगले डी 1 तत्व के साथ मेल खाने का एक बड़ा मौका भी होगा। क्या मैं इसका उपयोग अपने लाभ के लिए कर सकता हूं?

मैं इसे यथासंभव कुशल होने की कोशिश कर रहा हूं क्योंकि डेटा सेट इतना बड़ा है।

Answer 1

लूप के लिए एक इंडेक्स-आधारित एक इटरेटर से बेहतर प्रदर्शन कर सकता है, क्योंकि आप सीधे मूल सरणी को इंडेक्स कर सकते हैं और एक नई सरणी में कॉपी करने से बच सकते हैं। आपके पास बहुत बेहतर मेमोरी इलाके, झूठी साझा करने की कम संभावना, आदि

Answer 2

आपके जूते में, पहली चीज जो मैं करूँगा वह एक सामान्य डेटासेट प्रोफाइल है और पता चल रहा है कि समय कहां जा रहा है। इससे कुछ संकेत दिए जाएंगे कि आपके अनुकूलन प्रयासों को कहां केंद्रित किया जाए।

गणना मानना ​​घटाव/तुलना के रूप में सरल है, और सरणी को तुरंत एक्सेस किया जाता है, तो डेटाबेस में बचत अनुकूलित करने के आपके सुझाव को अगली प्राथमिकता दी जानी चाहिए। उदाहरण के लिए, एक टेक्स्ट फ़ाइल लिखना और थोक सम्मिलन का उपयोग करके व्यक्तिगत सम्मिलन विवरणों की तुलना में बहुत तेज प्रदर्शन प्रदान कर सकते हैं। यदि आप अलग-अलग आवेषणों का उपयोग करना चाहते हैं, और जेडीबीसी का उपयोग कर रहे हैं, तो बैच अपडेट बहुत मददगार होंगे, क्योंकि वे डेटाबेस के साथ संवाद करने में विलंबता से बचते हैं।

यदि यह अभी भी पर्याप्त तेज़ नहीं है, तो सरणी को एन विभाजन में विभाजित करने पर विचार करें, और प्रत्येक विभाजन को अलग थ्रेड द्वारा संसाधित किया गया है। प्रोसेसिंग सीपीयू बाध्य होने पर यह विशेष रूप से प्रभावी होगा।

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

यदि तत्वों की संख्या 10 से बड़ी है, और गंभीर रूप से, सीपीयू कैश में फिट होने से अधिक, यह छोटे ब्लॉक में स्कैनिंग को तोड़ने के लिए और अधिक कुशल होगा। उदाहरण के लिए, डेटा 2 से 1000 तत्व स्कैन करने के बजाय, इसे 100 के 10 स्कैन (कहें) में विभाजित करें, प्रत्येक 10 स्कैन डी 1 के एक अलग मूल्य का उपयोग करते हुए। यह समान है कि मैट्रिक्स बहुविकल्पीय को ब्लॉक फैशन में कैसे कार्यान्वित किया जाता है और सीपीयू कैश का बेहतर उपयोग करता है।

हालांकि आप दो लूप का उपयोग कर रहे हैं, जो आम तौर पर ओ (एन^2) एल्गोरिदम है, दूसरे लूप का एक निश्चित आकार - 10 तत्व होता है, इसलिए यह एक साधारण स्थिर कारक तक कम हो जाता है - आप मोटे तौर पर एक कारक कर रहे हैं 10 और काम

Answer 3

आपके पास क्लासिक स्वीपलाइन एल्गोरिदम है जो ओ (के * एन) के साथ "ओवरलैप" या आंतरिक भाग लूप के भाग के साथ होता है। आपके मामले में यह अधिकतम है 10 कोई बात नहीं क्या n

Datum[] data = x; 
for(int i=0;i<data.length;i++){ 
    Datum d1=data[i]; 
    Datum[] tail = y; //From d1 up to 10 elements ahead 
    for(int j=i+1;j<Math.min(i+10,data.length);i++){ 
     d2 = data[j]; 
     //Calculate difference 
     if((d2.val - d1.val) > 10){ 
      //Insert into database 

      break;//inner loop 
     } 
    } 
} 

Answer 4

वहाँ एक इस समस्या को हल करने के लिए asymptotically तेज़ तरीका है, लेकिन मैं के रूप में है कि क्या यह इसलिए है क्योंकि आपके विंडो का आकार व्यवहार में तेजी से काम कर सके गंभीर संदेह है (10) बहुत छोटा है।यदि आप इस आकार को बढ़ाना चाहते हैं - जिसे मैं बड़ा कहूंगा - तो आप निम्न जैसे दृष्टिकोण को चुनने पर विचार करना चाहेंगे।

1. एक नए तत्व डालें, हटाना उतना सबसे पुराने:

   आप इस कलन विधि का उपयोग कर रहे हैं, आप कश्मीर तत्वों कि दो आपरेशन का समर्थन करता है की एक खिड़की को बनाए रखने की जरूरत है।

2. कुछ मूल्यों से अधिक सभी तत्व लौटाता है।

ऐसा करने का एक तरीका एक संतुलित बाइनरी खोज पेड़ और एक कतार संयोजन डेटा संरचना में आपके सभी तत्वों को स्टोर करना होगा। कतार में क्रमशः सभी अनुक्रमों को संग्रहीत किया जाता है जिसमें वे मूल अनुक्रम में दिखाई देते हैं, और इसका उपयोग किया जाता है ताकि हम याद कर सकें कि हमें कौन सा तत्व बेदखल करना है जब हमें एक नया तत्व जोड़ने की आवश्यकता है। संतुलित बीएसटी क्रमबद्ध क्रम में संग्रहीत उन तत्वों में से प्रत्येक की एक प्रति स्टोर करता है। इसका मतलब है कि आप इस तरह से ऊपर के संचालन को लागू कर सकते हैं:

1. एक नए तत्व सम्मिलित करें, सबसे पुराना हटाना उतना: कतार और BST करने के लिए नए तत्व जोड़ें। फिर, कतार से सबसे पुराना तत्व प्राप्त करने के लिए, फिर इसे बीएसटी से हटा दें। रनटाइम: ओ (लॉग के), क्योंकि बीएसटी में इसके तत्व हैं।
2. कुछ मानों से अधिक सभी तत्वों को वापस लौटें: बीएसटी का उपयोग करके, कम से कम तत्व को O (लॉग n) समय में उस मान के रूप में बड़ा करें। फिर, बीएसटी में स्कैन करें और उस तत्व के रूप में कम से कम सभी तत्वों को सूचीबद्ध करें। यह ओ (जेड) समय लेता है, जहां जेड पाए गए मैचों की कुल संख्या है।

सामूहिक रूप से, यदि आपके पास एन तत्व हैं और डेटाबेस में सम्मिलित करने के लिए आपको कुल जेड जोड़े हैं, तो यह एल्गोरिदम ओ (एन लॉग के + जेड) समय लेगा। इसे देखने के लिए, ध्यान दें कि हम ऑपरेशन की कुल प्रतियां (1) करते हैं, जो प्रत्येक (ओ के लॉग) समय लेता है। हम संचालन की प्रतियां (2) भी करते हैं, जो उत्तराधिकारी खोजने के लिए ओ (एन लॉग के) समय लेता है और फिर सभी मिलान करने वाले जोड़े को सूचीबद्ध करने के लिए सभी पुनरावृत्तियों में ओ (जेड) कुल समय लेता है।

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

यदि आपके द्वारा संग्रहीत मूल्य एक छोटी सी सीमा (कहें, 0 - 10,000) में पूर्णांक हैं, तो आप van Emde Boas tree जैसे पूर्णांक के लिए अनुकूलित डेटा संरचना के साथ संतुलित बीएसटी को प्रतिस्थापित करके इसे और भी तेज कर सकते हैं, इसे ओ (एन लॉग लॉग के + जेड) को कम कर देता है। दोबारा, यह केवल असम्बद्ध रूप से है, और यदि आप 10 पर स्थिरांक रखते हैं तो यह लगभग निश्चित रूप से इसके लायक नहीं है।

आशा है कि इससे मदद मिलती है!