जावास्क्रिप्ट में (कुछ हद तक लागू कहीं भी), जहां आप नहीं जानते कि आपका कोड किस लक्ष्य कार्यान्वयन पर चल रहा है, क्या यह पता लगाने का एक तरीका है कि अंतर्निहित सॉर्टिंग एल्गोरिदम (Array.sort) स्थिर है या नहीं, केवल यह जानकर the specification का पालन करता है?क्या सॉर्टिंग एल्गोरिदम स्थिर है या नहीं, यह पता लगाने के लिए कोई ब्लैक बॉक्स विधि है?
मुझे वेबकिट (1)(2) में 2 परीक्षण मिल सकते हैं, लेकिन ये परीक्षण कितने विश्वसनीय हैं? (क्या यह चेक PCP के साथ किया जा सकता है?) मैं ऐसे समाधान की तलाश में हूं जो गणितीय रूप से ध्वनि होगी।
यह एक मुश्किल समस्या है, क्योंकि एक अधिक उन्नत सॉर्टिंग एल्गोरिदम स्रोत सरणी (जैसे टिमसोर्ट) की लंबाई के आधार पर सबलगोरिदम बदल सकता है। मैं उलझन में हूं क्योंकि मैंने जो भी परीक्षण चलाया है, वह Google क्रोम के प्रकार को स्थिर होने के लिए दिखाता है, लेकिन मैंने जो दस्तावेज देखा है, उसने कहा है कि यह अस्थिर है (the source आपको बताएगा क्यों)।
(आमतौर पर, मैं this strategy का उपयोग अपने प्रकार स्थिर बनाने के लिए, यह एक छोटी लेकिन कभी कभी उल्लेखनीय प्रदर्शन प्रभाव पड़ता है) विभिन्न कार्यान्वयन में छँटाई के लिए
स्रोत कोड:
आप केवल इस तरह का दृढ़ संकल्प कर सकते हैं: उदाहरण के लिए, मैं एक प्रकार एल्गोरिदम 'एस' परिभाषित कर सकता हूं जो इनपुट 'I' लेता है। आम तौर पर, 'एस' कुछ स्थिर सॉर्टलगोरिदम 'टी', * पर वास्तविक सॉर्टिंग कार्य को दूर करता है, लेकिन * जब' i' कुछ विशेष मान' I 'के बराबर होता है, तो यह इसके बजाय एक गैर-स्थिर प्रकार 'यू' का उपयोग करता है।आप कभी साबित नहीं करेंगे कि 'एस' गैर-स्थिर है जब तक आप भाग्य से बाहर नहीं होते और इनपुट के रूप में 'I'' पास नहीं करते हैं। अधिक वास्तविकता से, शायद 'एस' स्थिर प्रकार का उपयोग करता है जब तक कि 'I' बहुत लंबा न हो। फिर, यदि आप उचित रूप से लंबे इनपुट पर परीक्षण करते हैं तो आप केवल गैर-स्थिर प्रकार का निरीक्षण करेंगे। – apsillers
यदि स्पेक कहता है कि यह स्थिर नहीं है, तो इसका मतलब यह नहीं है कि जब आप सरणी को सॉर्ट करते हैं तो आइटम ऑर्डर करने की अपेक्षा कर सकते हैं, लेकिन इसके बजाय आप उस पर भरोसा नहीं कर सकते; कोई वादा नहीं है। कि (वर्तमान) कार्यान्वयन स्थिर होने के लिए होता है इसका मतलब यह नहीं है कि यह हमेशा होगा, या सभी प्लेटफॉर्म क्रोम चलने के लिए। – frozenkoi
मैं @MarZab से सहमत हूं कि यह एक रोकथाम समस्या है। यदि आप इसे '[कंप्यूटर-विज्ञान]' और/या '[कंप्यूटर-विज्ञान-सिद्धांत]' टैग करते हैं तो आप कुछ और ध्यान देख सकते हैं। – apsillers