RedBlackPy - पायथन में वैज्ञानिक और मात्रात्मक अनुसंधान के लिए तेज और स्केलेबल श्रृंखला

हम अपने नए ओपन सोर्स लाइब्रेरी RedBlackPy को पेश करना चाहते हैं। अब यह मैकओएस और लिनक्स (निकट भविष्य में विंडोज) पर पायथन 3.6+ के लिए उपलब्ध है।
यह अपाचे लाइसेंस 2.0 के तहत वितरित किया जाता है। आप इसे आसानी से पाइप के माध्यम से स्थापित कर सकते हैं:

>>> पाइप स्थापित करें redblackpy

लेख संरचना:

  • मुख्य विशेषताएं। RedBlackPy क्या है?
  • लाल-काले पेड़ क्यों? लाल-काले पेड़ों के संतुलन की सरल व्याख्या।
  • सीरीज और सीरीज़ेटर। सुविधाएँ, कोड उदाहरण और बेंचमार्क।

हाइलाइट

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

श्रृंखला 1-d डेटा रखने के लिए एक मानचित्रण डेटा संरचना है, जो:

  • डेटा को क्रम में रखता है, कुंजी द्वारा छांटा जाता है।
  • गतिशील डेटा के साथ काम करने के लिए तेजी से संचालन प्रदान करता है: प्रविष्टि, विलोपन, कुंजी द्वारा आइटम प्राप्त करें, कुंजी द्वारा आइटम सेट करें।
  • विशिष्ट संख्या में बिट्स के साथ सभी मूलभूत संख्यात्मक डेटा प्रकार प्रदान करता है (numpy का dtype analogue): अहस्ताक्षरित पूर्णांक, हस्ताक्षरित पूर्णांक,
    चल अंक। निश्चित रूप से, आप इस कंटेनर में किसी भी पायथन वस्तुओं को रख सकते हैं।
  • समय श्रृंखला या वैज्ञानिक मूल्यांकन के साथ काम करने के लिए आश्वस्त उपयोगकर्ता इंटरफ़ेस प्रदान करता है: प्रक्षेप का उपयोग करके किसी भी कुंजी द्वारा पहुंच। इंटरपोलेशन गेटिटेम ऑपरेटर में बनाया गया है और अतिरिक्त मेमोरी का उपयोग नहीं करता है। वैक्टर के लिए अंकगणित संचालन, सूचकांक पर डेटा स्थानांतरण।

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

हमारी टीम में हम भविष्य कहनेवाला मॉडलिंग समस्याओं से निपटने के लिए और वित्तीय समय श्रृंखला विश्लेषण कार्यों में इन डेटा संरचनाओं का उपयोग करते हैं।

लाल-काले पेड़ क्यों?

चित्र 1. wikipedia.org से लाल-काले वृक्ष का उदाहरण। पत्तियां NIL के रूप में विख्यात हैं।

लाल-काला पेड़ एक प्रसिद्ध डेटा संरचना है (उदाहरण के लिए, C ++ STL नक्शा और सेट लाल-काले पेड़ों पर आधारित है)। लाल-काले पेड़ों के बारे में बहुत सारी जानकारी है, इसलिए हम यहां सभी विवरणों के माध्यम से नहीं जाएंगे। हम केवल अवधारणा के मुख्य विचारों को पेश करेंगे ताकि इस संरचना से परिचित दर्शकों को आत्म संतुलन तर्क का विचार न मिले। यहाँ हम मानते हैं कि हमारा पाठक बाइनरी सर्च ट्री की मूल बातों से परिचित है। इस अनुभाग में दिए गए कथनों और प्रमाणों को निम्नलिखित वर्गों को समझने की आवश्यकता नहीं है।

परिभाषा 1. लाल-काला पेड़ एक स्व-संतुलन द्विआधारी खोज वृक्ष है जो निम्नलिखित स्थितियों को संतुष्ट करता है:

  1. प्रत्येक नोड या तो लाल या काला है।
  2. जड़ काली है।
  3. सभी पत्ते काले हैं।
  4. यदि एक नोड लाल है, तो उसके दोनों बच्चे काले हैं।
  5. जड़ से किसी भी पत्तियों नोड्स (चित्रा 1 पर NIL) के लिए हर सरल पथ में काले नोड्स की समान संख्या होती है।

एक स्व-संतुलन का मतलब है कि सम्मिलन और विलोपन कार्यों में पेड़ को संतुलित रखने के लिए कुछ संशोधन शामिल हैं। लेकिन वास्तव में इसका क्या मतलब है कि एक पेड़ संतुलित है?

परिभाषा 2. एक द्विआधारी खोज वृक्ष को क्रम के संतुलित होने के लिए कहा जाता है tree अगर
सबसे लंबे सरल पथ की लंबाई और सबसे छोटे सरल पथ में अंतर (प्रत्येक पथ जड़ से पत्तियों तक जाता है) बराबर होता है।

क्या हम परिभाषा 1 की शर्तों के संबंध में किसी भी द्विआधारी खोज पेड़ को रंग सकते हैं? अगला प्रस्ताव इस प्रश्न का उत्तर देता है।

प्रस्ताव 1. चलो टी एक लाल-काला पेड़ है। तब T ऑर्डर m से संतुलित होता है,
जहां मीटर ≤ ऊंचाई (टी) / 2।
सबूत। टी में लंबाई की ऊँचाई (टी) के मनमाने सरल मार्ग पर विचार करें। इसके अलावा, जड़ से मनमाने अवकाश के नोड के लिए एक और सरल मार्ग पर विचार करें। शर्तों के अनुसार 2-4 (परिभाषा 1) in के बराबर ब्लैक नोड्स की न्यूनतम संभव संख्या तोहाइट (टी) / 2) के बराबर होती है। इसी समय, पथ black में काले नोड्स की अधिकतम संभव संख्या लंबाई (𝜼) के बराबर है। शर्त 5 के अनुसार हम आवश्यक दावा प्राप्त करते हैं। ◀ ︎

अब हम जानते हैं कि लाल-काले पेड़ में नोड्स से पत्तियों तक किसी भी दो सरल रास्तों की लंबाई दो बार से अधिक नहीं होती है। जैसा कि एक बाइनरी सर्च ट्री की ऊंचाई एक खोज ऑपरेशन की जटिलता को परिभाषित करती है, अगला सवाल प्रकट होता है। एक अनियंत्रित लाल-काले पेड़ की ऊंचाई के बारे में हम क्या कह सकते हैं?

प्रस्ताव 2. आज्ञा देना एक लाल-काला पेड़ है जिसमें n नोड्स हैं। फिर निम्नलिखित रखती है:
ऊँचाई (T) log 2 लॉग (n +1), जहाँ लॉग बाइनरी लॉगरिदम है।
सबूत। प्रस्ताव 1 द्वारा टी में जड़ से पत्तियों तक किसी भी सरल पथ की लंबाई ऊंचाई (टी) / 2 से कम नहीं है। इसलिए n फ़र्स्टहाइट (T) / 2 notlevels में नोड्स की संख्या से कम नहीं है (1 लेवल रूट है, 2nd रूट बच्चे हैं, आदि)।
इस प्रकार हम n के लिए स्पष्ट निचली सीमा प्राप्त करते हैं और यह कथन का अर्थ करता है:

◀ ︎

प्रस्ताव 2 द्वारा लाल-काले पेड़ों में खोज अभियान में आकार जटिलता में लघुगणक है। यह पता चलता है कि एक नोड डालने या हटाने के लिए एक कुशल एल्गोरिथ्म (लॉगरिदमिक जटिलता) है। इस एल्गोरिथ्म में परिभाषा 1 के साथ पेड़ को बनाए रखने के लिए संशोधन (तथाकथित घुमाव) शामिल हैं।

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

  • डेटा को क्रमबद्ध रखें (प्रक्षेप के लिए)
  • लाखों वस्तुओं तक संसाधित करने की क्षमता
  • तेजी से संशोधन संचालन
  • फास्ट आइटम एक्सेस, तेज पुनरावृत्ति
  • मूल्यों के निर्माण में सुविधाजनक असंवैधानिक और अनुकूलित प्रक्षेप विधि। हम कई प्रक्षेप शामिल हैं: फर्श, छत, रैखिक, चाबियाँ केवल (डॉक्स देखें)।
  • कई अतुल्यकालिक समय श्रृंखला के बारे में पुष्टि करते हुए
  • वेक्टर अंकगणितीय संचालन

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

सीरीज और सीरीज़ेटर

ध्यान दें। इस खंड में हम कुछ बेंचमार्क प्रस्तुत करते हैं। सभी परीक्षण मैकबुक प्रो (रेटिना, 13-इंच, 2015 की शुरुआत) 2,7 गीगाहर्ट्ज इंटेल कोर i5 पर किए गए हैं।

अब मुख्य कार्यों के लिए कुछ सरल उपयोग मामलों और बेंचमार्क पर विचार करते हैं। हम यह उल्लेख करना चाहेंगे कि हम पंडों की श्रृंखला के साथ प्रतिस्पर्धा नहीं करते हैं और प्रतिस्पर्धा के संदर्भ में RedBlackPy Series और Pandas Series की तुलना करना सही नहीं होगा क्योंकि उनकी मुख्य डेटा संरचनाएँ भिन्न हैं। बेंचमार्क परिणामों का प्रदर्शन करके हम यह दिखाना चाहते हैं कि विशिष्ट समस्या के लिए डेटा संरचना का उचित विकल्प आर एंड आर प्रक्रिया में एक महत्वपूर्ण कदम है।

प्रक्षेप

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

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

चित्रा 2. प्रक्षेप उदाहरण। प्रारंभिक डेटा 5 बिंदुओं के साथ एक असतत संकेत द्वारा प्रस्तुत किया जाता है।

SeriesIterator

SeriesIterator वर्ग कई श्रृंखला वस्तुओं की कुंजियों के क्रमबद्ध संघ पर कुशल पुनरावृत्ति प्रदान करता है। यह वर्ग भी लाल-काले पेड़ की अवधारणा पर आधारित है। लाल-काले पेड़ का उपयोग आगे चलने वाले के मामले में न्यूनतम ढेर के रूप में किया जाता है और उलटा चलने वाले के मामले में अधिकतम-ढेर के रूप में। यह हीप k मेमोरी सेल्स का उपयोग करता है, जहां k श्रृंखला की वस्तुओं की संख्या है। नीचे दिए गए आंकड़े योजनाबद्ध रूप से SeriesIterator के काम का वर्णन करते हैं।

अब हम यादृच्छिक डेटा के साथ दस सीरीज़ ऑब्जेक्ट बनाते हैं और पुनरावृति लूप के निष्पादन समय का मूल्यांकन करते हैं। नीचे दिए गए कोड स्निपेट में हम श्रृंखला की सूची से SeriesIterator बनाते हैं, प्रत्येक श्रृंखला वस्तु में 100 000 आइटम होते हैं। आरंभीकरण के बाद हम आगे और पीछे इन श्रृंखला वस्तुओं की कुंजियों के क्रमबद्ध संघटन पर ध्यान दे रहे हैं।

दस सीरीज़ ऑब्जेक्ट्स के लिए प्रत्येक में 100 000 तत्व होते हैं, फॉरवर्ड और रिवर्स लूप क्रमशः 0.95 सेकंड और 0.92 सेकंड लेते हैं। यह समय मैकबुक प्रो (रेटिना, 13-इंच, 2015 की शुरुआत) पर प्राप्त किया गया है।

कोर संचालन बेंचमार्क

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

प्रत्येक फ़ंक्शन को निम्नलिखित आकारों के कंटेनरों पर परीक्षण किया जाता है: 10⁴, 10⁵, 10⁶, 10 containers।
परिणामों की साजिश करने के लिए हमने समय अक्ष के लघुगणक पैमाने का उपयोग किया है।

जैसा कि हम RedBlackPy के नतीजों में पंडों को प्रविष्टि, विलोपन और खोज (आइटम प्राप्त करें) संचालन के नीचे देख सकते हैं। उदाहरण के लिए, दस लाख कुंजियों की सूची पर कॉल करने और गेटीम ऑपरेटर को कॉल करने के लिए पंडों के लिए 11.8 सेकंड और रेडब्लैकपी के लिए 2.7 सेकंड का समय लगा। चाबियाँ की यादृच्छिक सूची के मामले में। लेकिन पंडों ने लगातार मेमोरी आवंटन के कारण सीरीज से अधिक पुनरावृति करने में रेडब्लैकपी को पीछे छोड़ दिया। उन्हीं कारणों से अंकगणित संचालक पंडों की तुलना में RedBlackPy धीमे काम करते हैं। आधुनिक प्रोसेसर वेक्टर निर्देशों (एसएसई, एवीएक्स) का समर्थन करते हैं और संरेखित और निरंतर आवंटित मेमोरी का उपयोग वैक्टर के लिए अंकगणितीय ऑपरेटरों का अनुकूलन प्रदान करता है।

चित्रा 3. RedBlackPy और पंडों श्रृंखला मानक

यदि आप चाबियों की क्रमबद्ध सूची से अधिक पुनरावृत्ति कर रहे हैं और गेटआईटम ऑपरेटर को कॉल कर रहे हैं, तो यह RedBlackPy श्रृंखला के तथाकथित 'इटर्मोड' का उपयोग करने के लिए समझ में आता है। कोड स्निपेट के मिलियन आइटम निष्पादन के साथ एक श्रृंखला के लिए नीचे 0.5 सेकंड लगे। बस एक विधि को कॉल करें और एक अच्छा स्पीडअप प्राप्त करें (इस मामले में पंडों की तुलना में लगभग 20 गुना तेज)।

यहां ओपन सोर्स RedBlackPy रिपॉजिटरी है। हम परियोजना पर किसी भी प्रतिक्रिया के लिए आभारी होंगे। धन्यवाद!