क्या पाइथन की मानक लाइब्रेरी में एवीएल या रेड-ब्लैक या किसी अन्य प्रकार के संतुलित बाइनरी पेड़ के लिए कोई मॉड्यूल है? मैंने एक खोजने की कोशिश की है, लेकिन असफल (मैं पाइथन के लिए अपेक्षाकृत नया हूं)।पायथन की मानक लाइब्रेरी - संतुलित बाइनरी पेड़ के लिए एक मॉड्यूल है?
नहीं, stdlib में संतुलित बाइनरी पेड़ नहीं है। हालांकि, आपकी टिप्पणियों से, ऐसा लगता है कि आपके पास कुछ अन्य विकल्प हो सकते हैं:
O(log n) खोजों की सूची के बजाय एक BST चाहते हैं। यदि खोज की आपको आवश्यकता है और आपका डेटा पहले ही सॉर्ट किया गया है, तो bisect मॉड्यूल सूचियों के लिए एक बाइनरी खोज एल्गोरिदम प्रदान करता है।यदि कोई समाधान आपके लिए अच्छा काम नहीं करता है, तो आपको किसी तृतीय पक्ष मॉड्यूल पर जाना होगा या अपना स्वयं का कार्यान्वयन करना होगा।
बहुत बहुत धन्यवाद! एक सेट का उपयोग करके मेरी समस्या हल हो गई। मुझे नहीं पता था कि उनके पास पाइथन में ओ (1) लुकअप है (मैंने हमेशा सोचा है कि सही सेट खोजने से पहले पूरे सेट को घुमाया जाना चाहिए - लेकिन जैसा कि मैंने कहा, मैं पाइथन के लिए नया हूं)। पायथन में सामान्य डेटा संरचनाओं के लिए आपकी व्याख्या के लिए भी धन्यवाद। – aeter
stdlib, as far as I can see में इस तरह का कुछ भी नहीं है, लेकिन quick look at pypi brings up a few alternative है:
एक तेज़-ए-सी भी है लेकिन शुद्ध-पायथन कार्यान्वयन [सॉर्टेड कंटेंटर्स] (http://www.grantjenks.com/docs/sortedcontainers /) डॉक्स में आपके द्वारा सूचीबद्ध विकल्पों के साथ एक अच्छा [प्रदर्शन तुलना] (http://www.grantjenks.com/docs/sortedcontainers/performance.html) है। – GrantJ
नहीं, लेकिन AVL Tree Objects for Python वहाँ और (बहुत पुरानी!) SourceForge पर एक (बंद) परियोजना - avl-trees for Python।
ऐसे कुछ उदाहरण हैं जहां मुझे उपयोगी होने के लिए heapq package (स्टैन्डर्ड लाइब्रेरी में) मिला है, खासकर अगर किसी भी समय आप अपने संग्रह में सबसे छोटे तत्व को ओ (1) एक्सेस टाइम चाहते हैं।
मेरे लिए, मैं टाइमर के संग्रह का ट्रैक रख रहा था और आमतौर पर यह जांचने में दिलचस्पी थी कि सबसे छोटा समय (जिसे पहले निष्पादित किया जाना है) अभी तक जाने के लिए तैयार था।
"बिंट्री" नामक एक नया पैकेज है जो उबला हुआ, एवीएल और आरबी पेड़ का समर्थन करता है। आप इसे here पा सकते हैं।
मैंने बिंट्री मॉड्यूल (2.0.1) स्थापित किया, लेकिन जब मैं इसे आयात करता हूं, तो मुझे संदेश मिलता है: 'चेतावनी: फास्टबिनरी ट्री पाइथन संस्करण बाइनरीट्री का उपयोग करके उपलब्ध नहीं है। कोई विचार यह कैसे ठीक करें? मैंने साइथन स्थापित किया, लेकिन यह अभी भी आयात पर उस त्रुटि को देता है। – yaraju
क्षमा करें, कोई विचार नहीं :( –
मुझे लगता है कि विंडोज़ पर, फास्टक्स्ट्री संस्करणों को एक सी संकलक की आवश्यकता है जैसे कि एमएसवीसी या मिंगव 32। मैंने इसे आजमाया नहीं है - क्योंकि मैं सबसे अधिक संभावना के लिए कस्टम पेड़ लागू करूंगा मेरा उद्देश्य – yaraju
Sorted Containers प्रोजेक्ट भी देखें। https://www.youtube.com/watch?v=7z2Ki44Vs4E
मैं सिर्फ सेट या शब्दकोशों का उपयोग करें:
यहाँ इसके बारे में एक PyCon बात है। अगर मुझे बेहतर हैशिंग रूटीन का उपयोग करने की ज़रूरत है, तो मैं '__hash __()' परिभाषित करता हूं। क्या आपको कुछ फैनसीयर चाहिए? यदि हां, तो क्यों? बीटीडब्लू, अगर आप इसे docs.python.org में नहीं ढूंढ पा रहे हैं, तो शायद यह मानक मॉड्यूल नहीं है। –
@ माइक - मैं प्रोजेक्ट यूलर से एक कार्य को हल करने की कोशिश कर रहा हूं। मुझे लगता है कि मेरे डेटा कंटेनर में से किसी एक के लिए एक सूची के बजाय एक संतुलित बाइनरी खोज पेड़ का उपयोग करके लॉगरिदमिक अनुपात (ओ (लॉगन) खोजों के कारण एल्गोरिदम को गति मिलेगी), जो मेरे कंप्यूटर को गर्म किए बिना कार्य को हल करेगी। इसके अलावा, मैं इसके बारे में सिर्फ उत्सुक था। – aeter
ओ (1) लुकअप – Mark