जावा पर डिजस्ट्रा: एक फाइबोनैकी ढेर बनाम दिलचस्प परिणाम का उपयोग करके दिलचस्प परिणाम प्राप्त करना

Question

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

Running Dijkstra's with 8 nodes and 27 links 
- Execution time with binary heap: 1 miliseconds 
- Execution time with Fibonacci heap: 4 miliseconds 

वैसे, मैं इस समय डेटा सेट पर कम, ऊपर ग्राफ मेरा सबसे बड़ा होने के साथ कर रहा हूँ (मैं और अधिक जल्द ही बनाने पर विचार किया)। लेकिन क्या इसका कोई मतलब है? मैंने हमेशा सोचा है कि फिबोनाची ढेर अन्य डेटा संरचनाओं की तुलना में अपने अमूर्त चलने वाले समय के कारण अन्य डेटा संरचनाओं की तुलना में तेज़ थे। मुझे सच में यकीन नहीं है कि यह 3-मिलीसेकंद अंतर कहाँ से आ रहा है। (मैं इसे इंटेल कोर आइवी ब्रिज i7-3630M प्रोसेसर पर चला रहा हूं, अगर यह मदद करता है।)

नोट: मैं this thread पर ठोकर खा रहा हूं जो इस मुद्दे को समझा सकता है, हालांकि मैं अभी भी स्पष्ट नहीं हूं कि फाइबोनैकी ढेर क्यों संस्करण अधिक समय ले रहा है। उस धागे के अनुसार, ऐसा इसलिए हो सकता है क्योंकि मेरा ग्राफ पर्याप्त घना नहीं है और इसलिए कमी की संख्या-कुंजी संचालन वास्तव में चमकने के लिए फाइबोनैकी ढेर के प्रदर्शन के लिए पर्याप्त नहीं है। क्या यह एकमात्र व्यावहारिक निष्कर्ष होगा, या क्या मैं कुछ और याद कर रहा हूं?

Answer 1

फिबोनैकी ढेर हैं asymptotically द्विआधारी ढेर (जावा की प्राथमिकता कतार में इस्तेमाल किया डेटा संरचना), कि डिज्कस्ट्रा एल्गोरिथ्म में हे लेने (m + n लॉग ऑन एन) एक फाइबोनैचि ढेर लेकिन हे (एम लॉग n के साथ समय होगा की तुलना में तेजी) एक बाइनरी ढेर के साथ। इसका मतलब है कि बड़े, घने ग्राफों के लिए, सबसे बुरे मामले में, फाइबोनैकी ढेर तेज हो जाएगा।

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

दूसरा, एसिम्प्टोटिक रनटाइम्स (ओ (एम + एन लॉग एन) बनाम ओ (एम लॉग एन) की तुलना करें)। यदि आप जिस ग्राफ का उपयोग कर रहे हैं वह स्पैस है (यानी, एम = ओ (एन)), तो इन दोनों एसिम्पटोटिक रनटाइम एक ही हैं (ओ (एन लॉग एन))। उस स्थिति में, फाइबोनैकी ढेर का सैद्धांतिक लाभ मौजूद नहीं है और बाइनरी ढेर बेहतर विकल्प हो सकता है।

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

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

Answer 2

फाइबोनैकी ढेर में तेजी से एसिम्प्टोटिक्स है, लेकिन उनके निरंतर कारक जरूरी नहीं हैं। एक लाख या उससे अधिक की लज्जास्पद रूप से भारी इनपुट पर, वे तेजी से हो सकते हैं, लेकिन छोटे इनपुट के लिए बाइनरी ढेर काफी तेज होने की संभावना है।