मुझे उत्सुकता है कि एल्गोरिदम लूआ का डिफ़ॉल्ट table.sort उपयोग करता है, केवल इसलिए कि यह कुछ अन्य सॉर्टिंग एल्गोरिदम से धीमा है जो मैंने पार किया है। मैं भी उत्सुक हूं अगर लुआ के table.sort इंजन में सी में लिखा गया है, या यदि यह लुआ में लाइब्रेरी में है।table.sort का क्या एल्गोरिदम उपयोग करता है?
table.sort का क्या एल्गोरिदम उपयोग करता है?
comment in tablib.c (थोड़ा ऊपर स्क्रॉल) में कहा गया
/*
** {======================================================
** Quicksort
** (based on `Algorithms in MODULA-3', Robert Sedgewick;
** Addison-Wesley, 1993.)
** =======================================================
*/
आप लिंक मैं प्रदान की पर स्रोत कोड पढ़ सकते हैं।
मैं भी उत्सुक हूं अगर लूआ का table.sort इंजन में सी में लिखा गया है, या यदि यह लुआ में लाइब्रेरी में है।
इस समय, सभी पुस्तकालयों कि सीधे लुआ के साथ आते हैं (io, table, math, ...) सी में लिखे गए हैं
आंतरिक रूप से, table.sort quicksort का उपयोग करता है, और यह सी नोट में लिखा है कि quicksort स्थिर नहीं है। और मेरे लिए थोड़ा आश्चर्यजनक रूप से, लुआ ने सी के qsort() का उपयोग नहीं किया।
प्रदर्शन के रूप में, यह कहना मुश्किल है क्योंकि विभिन्न कारक हैं, उदाहरण के लिए, कौन सी भाषा और आप किस एल्गोरिदम की तुलना कर रहे हैं, और किस प्रकार का डेटा परीक्षण किया जा रहा है।
लुआ का उपयोग करके, मुझे कुछ एल्गोरिदम मिले हैं जो डिफ़ॉल्ट रूप से थोड़ा तेज़ हैं। यदि आकार काफी कम है, कॉकटेल सॉर्ट और बबल सॉर्ट डिफ़ॉल्ट रूप से वास्तव में तेज़ हैं। यदि आकार बड़ा है, तो एलएसडी रैडिक्स सॉर्ट, जैसा कि मैंने दो अन्य के साथ कहा, तेज़ हैं। मैं इसे विभिन्न प्रकार के डेटा, जैसे रिवर्स किए गए सरणी, यादृच्छिक सरणी और यहां तक कि ज्यादातर सॉर्ट किए गए सरणी के साथ परीक्षण कर रहा हूं, लेकिन प्रत्येक परीक्षण के लिए, डिफ़ॉल्ट प्रकार अभी भी थोड़ा धीमा है। – jocopa3
@ jocopa3 जहां तक मैं देखता हूं, यह लुआ की समस्या नहीं है, बल्कि क्विकॉर्ट्स है। उदाहरण के लिए, quicksort क्रमबद्ध सरणी और उल्टा सरणी पर खराब प्रदर्शन करता है। यदि आपको विशिष्ट समस्याओं पर सॉर्टिंग करने की आवश्यकता है, और लुआ का डिफ़ॉल्ट प्रकार पर्याप्त रूप से पर्याप्त काम नहीं करता है, तो शायद सी में एक विशिष्ट प्रकार एल्गोरिदम लिखना एक अच्छा विचार है। –
@YuHao लिंक किए गए स्रोत को देखने से, लुआ का qsort हर समय पिवट के रूप में मध्य का चयन कर रहा है। यह qsort के आदर्श मामले के करीब होना चाहिए और इसे खराब प्रदर्शन नहीं करना चाहिए। मुझे संदेह है कि उन सभी लुआ एपीआई कॉल हो सकती हैं जो चीजों को धीमा कर रही हैं लेकिन यह सुनिश्चित नहीं हो सकती है कि यह प्रोफाइल न हो। – greatwolf
ध्यान दें कि लुआजिट [smoothsort] (http://en.wikipedia.org/wiki/Smoothsort) पर स्विच करने पर विचार कर रहा है, और इसके कई पुस्तकालय कार्यों को अब लुआ बाइटकोड में लागू किया गया है (जो वास्तव में फायदेमंद है क्योंकि यह तब हो सकता है जेआईटी को बेहतर संकलित करें) –