रूबी स्थिर में तरह है?

Question

रुबी स्थिर में sort है? यही है, sort के लिए टाई में मौजूद तत्वों के लिए, मूल आदेश से संरक्षित उनके बीच सापेक्ष आदेश है? उदाहरण के लिए, दिए गए:

a = [ 
    {id: :a, int: 3}, 
    {id: :b, int: 1}, 
    {id: :c, int: 2}, 
    {id: :d, int: 0}, 
    {id: :e, int: 1}, 
    {id: :f, int: 0}, 
    {id: :g, int: 1}, 
    {id: :h, int: 2}, 
] 

यह गारंटी है कि हम हमेशा

a.sort_by{|h| h[:int]} 

निम्नलिखित

[ 
    {id: :d, int: 0}, 
    {id: :f, int: 0}, 
    {id: :b, int: 1}, 
    {id: :e, int: 1}, 
    {id: :g, int: 1}, 
    {id: :c, int: 2}, 
    {id: :h, int: 2}, 
    {id: :a, int: 3}, 
] 

:id मूल्य के साथ तत्वों के बीच सापेक्ष आदेश के लिए किसी भी बदलाव के बिना के लिए मिलता है :d, :f, और :b, :e, :g, और :c, :h के बीच में? यदि ऐसा है, तो दस्तावेज़ीकरण में इसका वर्णन किया गया है?

यह प्रश्न this question के साथ कनेक्शन हो सकता है या नहीं हो सकता है।

Answer 1

दोनों MRI के sort और sort_byunstable हैं। कुछ समय पहले उन्हें स्थिर बनाने के लिए request था, लेकिन इसे अस्वीकार कर दिया गया था; इसका कारण यह है कि रूबी in-place quicksort algorithm का उपयोग करता है, जो स्थिरता की आवश्यकता नहीं होने पर बेहतर प्रदर्शन करता है। ध्यान दें कि आप अभी भी अस्थिर लोगों से स्थिर तरीकों को लागू कर सकते हैं:

module Enumerable 
    def stable_sort 
    sort_by.with_index { |x, idx| [x, idx] } 
    end 

    def stable_sort_by 
    sort_by.with_index { |x, idx| [yield(x), idx] } 
    end 
end 

Answer 2

व्यक्तिगत रूप से मैं इस पर भरोसा नहीं करता। कैसे मुक्केबाज़ी कुछ इस तरह कर रही है:

a.sort {|a, b| s1 = a[:int] <=> b[:int]; s1 != 0 ? s1 : a[:id] <=> b[:id] } 

Answer 3

नहीं, माणिक के अंतर्निहित तरह नहीं स्थिर है।

यदि आप स्थिर प्रकार चाहते हैं, तो यह काम करना चाहिए। यदि आप इसे अक्सर इस्तेमाल करने जा रहे हैं तो शायद आप इसके लिए एक विधि बनाना चाहते हैं।

a.each_with_index.sort_by {|h, idx| [h[:int], idx] }.map(&:first) 

मूल रूप से यह प्रत्येक मद के मूल सरणी सूचकांक का ट्रैक रखता है, और जब h[:int] ही है एक टाई ब्रेकर के रूप में यह उपयोग करता है।

अधिक जानकारी, उत्सुक के लिए:

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

आपका उदाहरण कुछ हद तक योगदान हुआ है क्योंकि :id कुंजी मूल सरणी में आरोही क्रमबद्ध हैं। मान लें कि मूल सरणी :id से उतरकर क्रमबद्ध थी;

[ 
{:id=>:f, :int=>0}, 
{:id=>:d, :int=>0}, 
{:id=>:g, :int=>1}, 
{:id=>:e, :int=>1}, 
{:id=>:b, :int=>1}, 
{:id=>:h, :int=>2}, 
{:id=>:c, :int=>2}, 
{:id=>:a, :int=>3} 
] 

मूल इंडेक्स का उपयोग करके यह भी संभाल लेंगे: आप परिणाम में :id के उतरते जब टाई को तोड़ने की है, इसलिए की तरह बनना चाहता हूँ चाहते हैं।

अद्यतन:

Matz के अपने सुझाव (this page देखें) के समान है, और इसके बाद के संस्करण की तुलना में थोड़ा और अधिक कुशल हो सकता है:,

n = 0 
ary.sort_by {|x| n+= 1; [x, n]} 

Answer 4

रूबी के कुछ कार्यान्वयन के लिए, प्रकार स्थिर लेकिन आपको इस पर निर्भर नहीं होना चाहिए। रुबी के प्रकार की स्थिरता कार्यान्वयन परिभाषित है।

क्या प्रलेखन कहते हैं

The documentation का कहना है कि आप तरह स्थिर किया जा रहा है पर निर्भर नहीं करना चाहिए:

परिणाम स्थिर होने की गारंटी नहीं है। जब दो तत्वों की तुलना 0 लौटाती है, तो तत्वों का क्रम अप्रत्याशित होता है।

ध्यान दें कि यह नहीं कहता कि यह प्रकार स्थिर है या नहीं। यह सिर्फ इतना कहता है कि यह स्थिर होने की गारंटी नहीं है। रुबी के किसी दिए गए कार्यान्वयन में स्थिर प्रकार हो सकता है और अभी भी दस्तावेज़ीकरण के अनुरूप हो सकता है। इसमें एक अस्थिर प्रकार भी हो सकता है, या किसी भी समय सॉर्ट स्थिर हो सकता है या नहीं।

क्या रूबी वास्तव में

यह परीक्षण कोड प्रिंट करता true अगर रूबी के प्रकार स्थिर, या false है अगर यह नहीं है:

Foo = Struct.new(:value, :original_order) do 
    def <=>(foo) 
    value <=> foo.value 
    end 
end 

size = 1000 
unsorted = size.times.map do |original_order| 
    value = rand(size/10) 
    Foo.new(value, original_order) 
end 
sorted = unsorted.sort 
stably_sorted = unsorted.sort_by do |foo| 
    [foo.value, foo.original_order] 
end 
p [RUBY_PLATFORM, RUBY_VERSION, RUBY_PATCHLEVEL, sorted == stably_sorted] 

यहाँ माणिक मैं पर स्थापित किया है सभी के लिए परिणाम हैं मेरी लिनक्स बॉक्स:

["java", "1.8.7", 357, false] 
["java", "1.9.3", 551, false] 
["x86_64-linux", "1.8.7", 374, false] 
["x86_64-linux", "1.8.7", 374, false] 
["x86_64-linux", "1.8.7", 376, false] 
["x86_64-linux", "1.9.3", 392, false] 
["x86_64-linux", "1.9.3", 484, false] 
["x86_64-linux", "1.9.3", 551, false] 
["x86_64-linux", "2.0.0", 643, false] 
["x86_64-linux", "2.0.0", 648, false] 
["x86_64-linux", "2.1.0", 0, false] 
["x86_64-linux", "2.1.10", 492, false] 
["x86_64-linux", "2.1.1", 76, false] 
["x86_64-linux", "2.1.2", 95, false] 
["x86_64-linux", "2.1.3", 242, false] 
["x86_64-linux", "2.1.4", 265, false] 
["x86_64-linux", "2.1.5", 273, false] 
["x86_64-linux", "2.1.6", 336, false] 
["x86_64-linux", "2.1.7", 400, false] 
["x86_64-linux", "2.1.8", 440, false] 
["x86_64-linux", "2.1.9", 490, false] 
["x86_64-linux", "2.2.0", 0, true] 
["x86_64-linux", "2.2.1", 85, true] 
["x86_64-linux", "2.2.2", 95, true] 
["x86_64-linux", "2.2.3", 173, true] 
["x86_64-linux", "2.2.4", 230, true] 
["x86_64-linux", "2.2.5", 319, true] 
["x86_64-linux", "2.2.6", 396, true] 
["x86_64-linux", "2.3.0", 0, true] 
["x86_64-linux", "2.3.1", 112, true] 
["x86_64-linux", "2.3.2", 217, true] 
["x86_64-linux", "2.3.3", 222, true] 
["x86_64-linux", "2.4.0", 0, true] 
["x86_64-linux", "2.4.0", -1, true] 
["x86_64-linux", "2.4.0", -1, true] 
["x86_64-linux", "2.4.0", -1, true] 
["x86_64-linux", "2.4.0", -1, true] 
["x86_64-linux", "2.4.1", 111, true] 

हम देख सकते हैं कि JRuby अस्थिर है, और 2.2 से पहले एमआरआई, लिनक्स पर, अस्थिर है। एमआरआई> = 2.2.0 स्थिर है (फिर से, लिनक्स पर)।

हालांकि प्लेटफॉर्म मायने रखता है। हालांकि उपरोक्त परिणाम से पता चलता है कि तरह लिनक्स पर एमआरआई 2.4.1 में स्थिर है, एक ही संस्करण विंडोज पर अस्थिर है:

["x64-mingw32", "2.4.1", 111, false] 

क्यों एमआरआई लिनक्स पर तरह स्थिर है, लेकिन विंडोज पर नहीं है?

रूबी कार्यान्वयन के एक संस्करण के भीतर भी, सॉर्ट एल्गोरिदम बदल सकता है। एमआरआई कम से कम तीन अलग-अलग प्रकार का उपयोग कर सकता है। util.c में #ifdefs की श्रृंखला का उपयोग करके संकलन समय पर क्रमबद्ध दिनचर्या का चयन किया जाता है। ऐसा लगता है कि एमआरआई में कम से कम दो अलग-अलग पुस्तकालयों से प्रकार का उपयोग करने की क्षमता है। इसका अपना कार्यान्वयन भी है।

इसके बारे में आपको क्या करना चाहिए?

चूंकि सॉफ़्टवेयर स्थिर हो सकता है लेकिन स्थिर होने की गारंटी नहीं दी जा सकती है, तो कोड लिखना न करें जो रुबी के प्रकार स्थिर होने पर निर्भर करता है। एक अलग संस्करण, कार्यान्वयन, या मंच पर इस्तेमाल होने पर वह कोड तोड़ सकता है।