क्या मैं इसके लिए एक पेड़ की तुलना में एक तेज डेटा संरचना का उपयोग कर सकता हूं?

Question

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

मैं इस पेड़ पर बड़ी संख्या में लुकअप कर रहा हूं (प्रदर्शन विश्लेषण के अनुसार लगभग 17% निष्पादन समय (संपादित करें: अन्य क्षेत्रों को अनुकूलित करने के बाद यह लगभग 40% है), और मुझे आश्चर्य है कि क्या मैं/लुकअप की गति में सुधार के लिए एक अलग डेटा संरचना का उपयोग करना चाहिए।

किसी प्रकार की हैश तालिका का उपयोग नहीं किया जा सकता है, क्योंकि इनपुट सीधे पत्ती नोड पर मैप नहीं करते हैं, लेकिन मैं सोच रहा था कि किसी के पास पेड़ के स्थान पर उपयोग की जाने वाली विधियों और डेटा-संरचनाओं के रूप में कोई सुझाव था (या साथ ही?) लुकअप की गति में सुधार करने के लिए।

मेमोरी एक चिंता है, लेकिन गति से चिंता का कम है।

कोड वर्तमान में सी # में लिखा गया है, लेकिन जाहिर है कि किसी भी विधि को लागू किया जा सकता है।

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

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

मैं iterator यहाँ के प्रदर्शन के बारे में प्रश्न पोस्ट:

Micro optimisations iterating through a tree in C#

लेकिन मुझे लगता है मैं डेटा संरचना में ही देखने के लिए प्रदर्शन में सुधार करने के लिए आगे की आवश्यकता हो सकती।

मैं यहां जितना संभव हो उतना प्रदर्शन करने का लक्ष्य रख रहा हूं। मैं मशीन सीखने की एक नई विधि पर काम कर रहा हूं, और पेड़ फीडबैक लूप का उपयोग कर खुद बढ़ता है। जिस प्रक्रिया के लिए मैं काम कर रहा हूं, उसके लिए मुझे लगता है कि यह कई महीनों तक चल रहा है, इसलिए यहां कुछ% बचत और भारी है। अंतिम लक्ष्य बहुत अधिक स्मृति का उपयोग किए बिना गति है।

Answer 1

यह मानकर निर्णय एक 50/50 मौका है:

कल्पना कीजिए कि आप दो द्विआधारी निर्णय था, संभव पथ 00, 01, 10, 11

कल्पना करें कि पेड़ के बजाय आपके पास चार परिणामों के साथ एक सरणी थी; आप फ्लोट की अपनी सरणी को बाइनरी नंबर में बदल सकते हैं जो इस सरणी में इंडेक्स होगा।

Answer 2

यदि मैं सही ढंग से समझता हूं, तो आपके पास निर्णय लेने के लिए फ़्लोटिंग पॉइंट रेंज हैं। इस तरह कुछ:

 x <= 0.0  : Decision A 
0.0 < x <= 0.5  : Decision B 
0.5 < x <= 0.6  : Decision C 
0.6 < x    : Decision D 

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

यदि पेड़ संतुलित नहीं है, तो आप आवश्यकतानुसार कहीं अधिक तुलना कर सकते हैं। सबसे बुरे मामले में: ओ (एन)। तो मैं पेड़ों को देखता हूं और देखता हूं कि वे कितने गहरे हैं। यदि एक ही पेड़ बार-बार उपयोग किया जाता है, तो एक बार फिर से विद्रोह करने की लागत कई लुकअप पर अमूर्त हो सकती है।

यदि इनपुट मानों को समान रूप से वितरित नहीं किया जाता है (और आप समय से पहले जानते हैं), तो आप तुलना के क्रम को विशेष मामले में लेना चाहेंगे ताकि सबसे आम मामलों का पता चल सके। पेड़ की जांच करने से पहले आप पेड़ में हेरफेर करके या कोड में विशेष मामलों को जोड़कर ऐसा कर सकते हैं।

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

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