हर बार राशियों और औसत का पुनरावर्तन कैसे न करें

कल्पना करें कि हमारे पास एक इलेक्ट्रॉनिक भुगतान प्रणाली है, और इसमें डेटाबेस में संचालन की एक तालिका है। और हम गणना करना चाहते हैं, उदाहरण के लिए, औसत ऑपरेशन किस आकार का है। आसान है, यहाँ अनुरोध है, इसे पूरा होने में केवल एक लंबा समय लगता है:

> SELECT avg(amount) FROM transfer;
65.125965782378
generated in 3850 seconds

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

साइकिल की सवारी करने वालों को आश्चर्य हो सकता है कि यह साइकलिंग कंप्यूटर औसत गति को कितनी लंबी और हर सेकंड की गणना कर सकता है, लेकिन सभी गति मूल्यों को संग्रहीत नहीं करता है। अब, निश्चित रूप से, एक माइक्रोएसडी कार्ड बाइक कंप्यूटर में प्रवेश करेगा, लेकिन उन्होंने उसी तरह से काम किया जब सालों पहले ऐसी कोई मेमोरी नहीं थी।

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

अन्य रूपांतरण

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



यदि हम d ₁ नहीं जानते हैं, तो कुछ भी नहीं किया जाएगा।

यदि हम कुछ मूल्य को बदलते हैं जो पहले से ही ध्यान में रखा गया है, तो हम दो बार एक ही काम करते हैं: पुराने मूल्य को औसत से हटा दें और एक नया जोड़ें।



जो लोग गणित जानते हैं वे आसानी से ऐसे सूत्रों में विचरण कर सकते हैं, जैसे कि विचरण, उत्पाद, यहां तक ​​कि प्रत्येक द्वारा प्रत्येक मात्रा का उत्पाद (या सहसंयोजक)। व्यवहार में इस तरह के ज्ञान को लागू करना एक उदाहरण है।

प्रोफाइल

उपयोगकर्ता विभिन्न प्रश्नों से एक प्रश्नावली भरते हैं, जहां वे 1 से 100 के पैमाने पर समझौते का संकेत देते हैं (मजबूत समझौते से पूरी तरह असहमत)। 2 उपयोगकर्ताओं के बीच अंतर की गणना करना आवश्यक था, अर्थात्, संबंधित प्रश्नों के उत्तर के बीच मानक विचलन:



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

अनुकूलन के बिना डेटाबेस की क्वेरी निम्नानुसार थी:

  का चयन करें
         avg (शक्ति (my_answer.value - his_answer.value, 2))

     से
         उत्तर as my_answer
             INNER JOIN जवाब my_answer as my_answer.question_id = his_answer.question_id पर लिखें

     कहां
         my_answer.user_id = X AND
         his_answer.user_id = Y 

कई उपयोगकर्ताओं के लिए, आपको बस स्थिति बदलने की आवश्यकता है:

  ...
     कहां
         उसका_शब्द.सेर_िड इन (जेड) और
         ... 

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

पहली पंक्ति में इस सूत्र पर फैलाव सूत्र है, अधिक सटीक रूप से वह हिस्सा जिसे अनुकूलित करने की आवश्यकता है। X _q इस उपयोगकर्ता का उत्तर है (जिसके लिए संकेतक माना जाता है) q को प्रश्न करने के लिए, V _qu एक ही प्रश्न q के लिए उपयोगकर्ता u का उत्तर है। हम उपयोगकर्ताओं और प्रश्नों को एकत्र करते हैं। यदि कुछ प्रश्न हैं (m) 50), तो कई प्रश्नावली (n) 10,000) हैं। दूसरी पंक्ति में वही सूत्र है जहाँ उपयोगकर्ताओं के लिए योग (n, 10,000) को अलग किया गया है। इस पूरी अभिव्यक्ति पर q-sum ओवरहैंग करता है, अर्थात, डेटा को प्रश्नों से तोड़ दिया जाना चाहिए, और आपको हर बार उन्हें एग्रीगेट करना होगा, लेकिन यह केवल 50 लाइनें हैं। और 10,000 उपयोगकर्ताओं की मात्रा, यू, हम अलग-थलग हैं और गणना और स्टोर कर सकते हैं। यदि हम प्रश्न का उत्तर देने के योग को एस क्यू के रूप में निरूपित करते हैं, और वर्गों के योग को आर _{क्यू के} रूप में कहते हैं, तो हमें एक बहुत ही संक्षिप्त विवरण मिलता है:



S _q और R _q को एक अलग तालिका में पहले से गणना और संग्रहीत किया जा सकता है।

माप

यह महसूस करने के लिए कि सिस्टम कितनी तेजी से काम कर सकता है, मैंने एक स्क्रिप्ट बनाई जो अमूर्त उपयोगकर्ताओं से अमूर्त प्रश्नों के यादृच्छिक उत्तर उत्पन्न करती है। स्क्रिप्ट केवल एक तालिका भरती है, उत्तर। हमें अन्य तालिकाओं की आवश्यकता नहीं है।

  आयात sys, sqlite3, यादृच्छिक, itertools

 USERS = xrange (100000)
 प्रश्न = xrange (50)

 con = sqlite3.connect ('एकत्रीकरण.सक्लाइट 3')
 cur = conn.cursor ()

 cur.execute ('ड्रॉप टेबल यदि मौजूद है तो उत्तर');
 cur.execute ('तालिका उत्तर (user_id पूर्णांक, question_id पूर्णांक, मान पूर्णांक) बनाएँ)'

 यू के लिए, itertools.product में q (USERS, प्रश्न):
	 cur.execute ('उत्तर मानों में डालें (?,?)?', (u, q, random.randint (1, 100)))

 # हम डेटा प्रविष्टि के बाद सूचकांक बनाते हैं,
 # ताकि बाइनरी पेड़ को पुन: सम्मिलन के दौरान एक बार फिर से न बनाया जाए
 cur.execute ('उत्तर पर अनुक्रमणिका answer_user बनाएं (user_id)')
 cur.execute ('उत्तर पर अनुक्रमणिका answer_question बनाएँ (question_id)')
 con.commit ()

 cur.execute ("")
	 के रूप में तालिका answer_summary बनाएं
	 question_id, sum (मान) value, sum (मान * value) value_square, count (*) num चुनें
	 उत्तर से
	 question_id द्वारा समूह
	 "" ")

 cur.execute ('answer_summary (question_id) पर अद्वितीय सूचकांक answer_question बनाएं') 

100,000 उपयोगकर्ताओं के लिए 50 प्रतिक्रियाएं - 5 मिलियन रिकॉर्ड। मेरे कमजोर लैपटॉप (1.5 गीगाहर्ट्ज x2 और 2 जीबी मेमोरी) पर, टेबल लगभग आधे घंटे में बनाए गए थे, और रिकॉर्ड की संख्या के आधार पर फाइल दसियों से सैकड़ों मेगाबाइट तक निकली थी।

मैंने कई प्रश्नों और वर्गों के योगों के साथ कई प्रश्न किए, जिनकी व्यक्तिपरक संवेदनाएं मैं नीचे देता हूं। महत्वपूर्ण बात यह है कि लिनक्स डेटाबेस फ़ाइल को पूरी तरह से मेमोरी में कैश्ड करता है। यही है, केवल एक चीज जो केवल गणना धीमा कर देती है: सूचकांक खोज और जोड़।

और यहां परिणाम हैं, अगर हम उत्तरों में अंतर के आंकड़ों पर विचार करते हैं:

	अनुकूलन के बिना	अनुकूलन के साथ
सभी के लिए	सेकंड	तुरंत
प्रत्येक को	मिनट	तुरंत

साइड इफेक्ट

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

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

राशि अपडेट उसी तरह से किया जा सकता है: आपको टेबल जॉइन के साथ जटिल अद्यतन प्रश्नों को लिखने की आवश्यकता नहीं है, आप डेटा का चयन कर सकते हैं, इसे जोड़ सकते हैं और फिर इसे INSERT या REPLACE का उपयोग करके अपडेट कर सकते हैं।

जहां दृष्टिकोण काम नहीं करता है

स्पीडोमीटर उदाहरण पर वापस चलते हैं। हमारी किलोमीटर प्रति घंटे में औसत गति है। हम इसे रैखिक रूप से मीटर प्रति सेकंड में परिवर्तित कर सकते हैं। यदि हम किमी / घंटा से एम / एस तक गिने जाते हैं, और केवल तब एकत्र होते हैं, तो वही बात होती।

यदि हम औसत स्टोर करते हैं, और हम औसत वायु प्रतिरोध (गति के वर्ग के आनुपातिक) की गणना करना चाहते हैं, तो हम सफल नहीं होंगे, क्योंकि मूल्यों के वर्गों का योग मानों के योग से बाहर काम नहीं करता है। हमें प्रारंभिक टिप्पणियों की आवश्यकता है।

इतना जटिल नहीं है

वास्तव में, यदि आपके पास ओएलएपी नहीं है, लेकिन सिर्फ ओआरएम है, तो आपको एसक्यूएल क्वेरी शीट लिखने की आवश्यकता नहीं है, जिसे आपको बाद में बनाए रखने की आवश्यकता होगी और सबसे खराब, दूसरे व्यक्ति को समझें। इस तरह के अनुकूलन संबंधित मॉडल के रूप में किए जा सकते हैं। यहाँ कैसे Django में मॉडल को व्यवस्थित करने के लिए है:

  कक्षा प्रश्न (मॉडल):
     पाठ = चारField ()


 कक्षा उत्तर (मॉडल):
     उपयोगकर्ता = विदेशीके (उपयोगकर्ता)
     प्रश्न = विदेशीके (प्रश्न)
     मान = IntegerField ()


 वर्ग उत्तरअनुरूप (मॉडल):
     सवाल = विदेशीके (प्रश्न, संबंधित_नाम = 'समुच्चय')
     सम = इंटेगरफिल्ड ()
     sum_of_squares = IntegerField ()
     answer_count = IntegerField ()


 def add_to_aggregates (* kwargs):
     उत्तर = क्वार्ग्स ['उदाहरण']
     answer.question.aggregates.update (
         sum = F ('sum') + answer.value,
         sum_of_squares = F ('sum_of_squares') + answer.value ** 2,
         answer_count = F ('answer_count') + 1
     )


 def remove_from_aggregates (* kwargs):
     उत्तर = क्वार्ग्स ['उदाहरण']
     answer.question.aggregates.update (
         sum = F ('sum') - answer.value,
         sum_of_squares = F ('sum_of_squares') - answer.value ** 2,
         answer_count = F ('answers_count') - 1
     )


 signal.post_add.connect (add_to_aggregates, model = Answer)
 signal.pre_update.connect (remove_from_aggregates, मॉडल = उत्तर)
 signal.post_update.connect (add_to_aggregates, model = Answer)
 signal.pre_delete.connect (remove_from_aggregates, मॉडल = उत्तर)

जब हम एक उत्तर बनाते हैं, तो हम इसे अलग-अलग मात्रा में जोड़ते हैं। निकालने के लिए, आपको बस मूल्यों को घटाना होगा। बदलने के लिए, हम पुराने को घटाते हैं और नया मान जोड़ते हैं।

एक आकर्षक होमवर्क के रूप में, आप ORM या SQL के माध्यम से एक क्वेरी लिख सकते हैं, जो ऊपर दिए गए सूत्र से मानक विचलन की गणना करता है।

मूल्य में सुधार

इस तरह की गणनाओं को अनुकूलित करना कितना समीचीन है एक अलग मुद्दा है। प्रश्नावली के साथ उदाहरण में, रिपोर्ट में कुछ हज़ार उपयोगकर्ताओं के साथ भी धीमा होना शुरू हुआ, और दस हज़ार के साथ इस तरह के प्रत्येक अनुरोध को कुछ सेकंड के लिए पूरा किया गया। एक छोटी सी परियोजना पर भी डेटा की इतनी मात्रा काफी प्राप्त होती है, और एक व्यावसायिक उद्यम पर भी। नियमित डेटाबेस आज ऐसे अनुकूलन स्वचालित रूप से नहीं करते हैं। अनुकूलन OLAP डेटाबेस में बनाए जाते हैं, लेकिन एक छोटे उद्यम के लिए वे महंगे और भारी होते हैं। इसलिए, इस तरह के छोटे अनुकूलन एक अच्छा समाधान हो सकते हैं।

ऐसे अनुकूलन की कीमत होगी:

1. फार्मूलाबद्ध करें और उन्हें समझें, इसके लिए आपको गणितीय आँकड़ों का अच्छा ज्ञान होना चाहिए।
2. ORM में एक ट्रिगर या प्रक्रिया लिखें और इसे डीबग करें।
3. सिस्टम को विस्तार से दस्तावेज दें ताकि आपके बाद नया कर्मचारी सामान्य कुल कार्यों का उपयोग शुरू न करें।

परिणाम

सबसे पहले, जैसा कि माप से देखा जा सकता है, इकाइयों में मुख्य ब्रेक (एसयूएम, एवीजी) डिस्क पढ़ने में बिल्कुल नहीं है, बल्कि संक्षेप में है।

दूसरे, यहां तक ​​कि जटिल एकत्रित कार्य भी विघटित हो सकते हैं और समुच्चय को उनमें प्रतिष्ठित किया जा सकता है। मैंने दिखाया कि कैसे अंतर के वर्ग को घटकों में विघटित किया जा सकता है और इसमें प्रतिष्ठित किया जा सकता है मात्रा और उनके वर्गों का योग। राशियों की गणना पूर्व और संग्रहीत तैयार की जा सकती है।

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

तीसरा, आप नए डेटा को जोड़ सकते हैं, पुराने को पूरी तरह से एकत्र किए बिना पुराने को संपादित और हटा सकते हैं। पुनर्गणना के संसाधन उपभोग में भी O (n) समय की कमी होगी।

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

अंत तक पढ़ने वालों के लिए: लेख की शुरुआत में लिस्टिंग काल्पनिक है।