एक गैर परिवर्तनीय तुलनित्र "काम" द्वारा छंटनी करता है?

यदि मैं एक गैर-संक्रमणीय ComparatorCollections.sort पर आपूर्ति करता हूं तो क्या होगा? क्या मैं अनंत लूप में चला सकता हूं?एक गैर परिवर्तनीय तुलनित्र "काम" द्वारा छंटनी करता है?

मैंने लिखा एक छोटा सा परीक्षण एक आउटपुट का उत्पादन किया, लेकिन मैं यह सुनिश्चित करना चाहता हूं कि यह हमेशा मामला होगा।

समस्या यह है कि कुछ मामलों में, मेरा तुलनित्र चक्र उत्पन्न कर सकता है, और इस मामले में मैं बस यह सुनिश्चित करना चाहता हूं कि यह अनंत लूप में नहीं चलेगा। मुझे वास्तविक परिणाम की परवाह नहीं है।

स्रोत

2011-10-31 duduamar

शायद कुछ प्रासंगिक कोड पोस्ट करें? – pap

यह एक सामान्य प्रश्न है, जो एक विशिष्ट कोड से प्रासंगिक नहीं है - प्रश्न यह है कि यदि मैं एक तुलनित्र प्रदान करता हूं जो संग्रह को प्रदान करता है जो संग्रह .sort – duduamar

गैर-संक्रमणीय 'तुलनाकर्ता' का उपयोग करने का व्यवहार परिभाषित नहीं किया गया है, एक गैर-संक्रमणीय 'तुलनात्मक' के रूप में ** ** ठीक से लागू नहीं किया गया है **। प्रैक्टिस में, मैं * सुंदर * सुनिश्चित करता हूं कि 'संग्रह .sort()' एक * अनंत * लूप में नहीं चलाएगा, भले ही 'तुलनाकर्ता' टूटा हुआ हो। लेकिन विनिर्देशों में कुछ भी * इस व्यवहार की आवश्यकता नहीं है। –

Java docs कहता है कि आपको यह सुनिश्चित करना होगा कि आपका तुलनित्र संक्रमणीय है। यदि आप एक तुलनित्र की आपूर्ति करते हैं जो अनुरोधित नहीं किया गया है, तो सभी दांव बंद हैं। यह किसी दिए गए कार्यान्वयन के लिए काम कर सकता है लेकिन दूसरे में क्रैश हो सकता है (std::sort सी ++ में करता है)।

संक्षेप में, आपको कुछ या अन्य उदाहरणों के लिए भी काम करने पर भरोसा नहीं करना चाहिए।

स्रोत

2011-10-31 08:24:51 Pablo

हाँ ... यह समझ में आता है। मुझे उस पर भरोसा नहीं करना चाहिए, धन्यवाद। – duduamar

हाय पाब्लो।मुझे एक टिप्पणी को हाइजैक करने के लिए खेद है, लेकिन मैंने यहां एक प्रश्न पूछा है: https://stackoverflow.com/questions/45599509/why-does-stdsort-segfault-with-non-transitive-comparators आप स्पष्ट रूप से उस मुद्दे का सामना करना पड़ा है जिसका मैं आज सामना कर रहा हूं, जहां सी ++ std :: सॉर्ट एक गैर-संक्रमणीय तुलनित्र के साथ दुर्घटनाग्रस्त हो जाता है। मैं सोच रहा था कि क्या आपको पता था क्यों? फिर, 6 साल की एक टिप्पणी को हाइजैक करने के लिए खेद है, लेकिन इस विषय पर बहुत कम डेटा मौजूद है। –

Collections.sort()mergesort पर आधारित है।

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

हालांकि, परिणाम सूची के आदेश पर कोई गारंटी नहीं है।

स्रोत

2011-10-31 08:29:43 amit

यह एक अच्छी टिप्पणी है, लेकिन कार्यान्वयन बिना किसी सूचना के बदला जा सकता है ... – duduamar

हाँ। यह जावा 7 में बदल गया। – vz0

इस मामले में Collections.sort का व्यवहार कार्यान्वयन निर्भर है। जावा 6 एसई कार्यान्वयन विलय और सम्मिलन के संयोजन का उपयोग करता है जो गैर-संक्रमणीय तुलनित्रों के साथ निर्धारक दोनों हैं, लेकिन जावा 7 में टिमसोर्ट एल्गोरिदम का उपयोग किया जाता है और अन्य कार्यान्वयन क्विक्सोर्ट या कुछ और का उपयोग कर सकते हैं, इसलिए आप यह सुनिश्चित नहीं कर सकते कि यह सभी कार्यान्वयन के साथ काम करते हैं।

स्रोत

2011-10-31 08:30:08 x4u

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

स्रोत

2011-10-31 08:30:12 Max

चूंकि जावा 7 संग्रह .sort TimSort का उपयोग करता है। जावा> = 7 में सॉर्टिंग के लिए एक गैर-संक्रमणीय तुलनित्र का उपयोग निम्नलिखित अपवाद को फेंक देगा:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

स्रोत

2014-12-04 13:50:50 Martin

एक गैर परिवर्तनीय तुलनित्र "काम" द्वारा छंटनी करता है?

उत्तर

संबंधित मुद्दे