रूबी

Question

में एक विशेष रेंज से अधिकतम मूल्य प्राप्त करने का सबसे तेज़ तरीका ठीक है, तो कहें कि आपके पास रूबी में वास्तव में बड़ी रेंज है। मैं रेंज में अधिकतम मूल्य प्राप्त करने का एक तरीका खोजना चाहता हूं।

रेंज अनन्य है (तीन बिंदुओं के साथ परिभाषित) जिसका अर्थ है कि इसमें इसके परिणाम में अंतिम वस्तु शामिल नहीं है। यह इंटीजर, स्ट्रिंग, टाइम, या वास्तव में किसी भी ऑब्जेक्ट से बना हो सकता है जो #<=> और #succ का जवाब देता है।

past = Time.local(2010, 1, 1, 0, 0, 0) 
    now = Time.now 
    range = past...now 

    range.include?(now) # => false 

अब मुझे पता है मैं सिर्फ अधिकतम मूल्य प्राप्त करने के कुछ इस तरह कर सकता है:

यहाँ एक विशेष रेंज का एक उदाहरण है (जो रेंज में प्रारंभ/समाप्ति वस्तु के लिए केवल आवश्यकताओं हैं):

range.max # => returns 1 second before "now" using Enumerable#max 

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

जैसा ऊपर बताया गया है ऊपर Range#last का उपयोग नहीं किया जाएगा, क्योंकि यह एक विशेष सीमा है और इसमें इसके परिणामों में अंतिम मूल्य शामिल नहीं है।

max = nil 
    range.each { |value| max = value } 

    # max now contains nil if the range is empty, or the max value 

यह Enumerable#max क्या करता है (जो रेंज विरासत), सिवाय इसके कि यह तथ्य यह है कि प्रत्येक मूल्य से अधिक होने जा रहा है कारनामे के समान है:

सबसे तेजी से दृष्टिकोण मैं के बारे में सोच सकता है यह था पिछला, इसलिए हम पिछले कुछ मानों की तुलना करने के लिए #<=> का उपयोग करके छोड़ सकते हैं (जिस तरह से Range#max करता है) एक छोटा सा समय बचाता है।

अन्य दृष्टिकोण जो मैं सोच रहा था, सामान्य रूबी प्रकारों जैसे इंटीजर, स्ट्रिंग, टाइम, डेट, डेटटाइम के लिए विशेष केस कोड होना था, और उसके बाद उपरोक्त कोड को फ़ॉलबैक के रूप में उपयोग करना था। यह थोड़ा बदसूरत होगा, लेकिन संभवत: अधिक ऑब्जेक्ट प्रकारों का सामना करना पड़ता है क्योंकि मैं बिना किसी पुनरावृत्ति के अधिकतम मूल्य प्राप्त करने के लिए Range#last से घटाव का उपयोग कर सकता हूं।

क्या कोई इस से अधिक कुशल/तेज़ दृष्टिकोण के बारे में सोच सकता है?

Answer 1

सरल समाधान है कि मैं के बारे में सोच सकता है, जो अनन्य पर्वतमाला के साथ ही समावेशी के लिए काम करेंगे:

range.max 

कुछ अन्य संभावित समाधानों:

range.entries.last 
range.entries[-1] 

ये समाधान सभी हे हैं (एन), और बड़ी श्रृंखला के लिए बहुत धीमी होगी। सिद्धांत में समस्या यह है कि रूबी में रेंज मानों को succ विधि का उपयोग शुरुआत से शुरू होने वाले सभी मूल्यों पर क्रमशः किया जाता है। तत्व को पिछले मान को वापस करने के लिए कोई विधि लागू नहीं करनी है (यानी pred)।

सबसे तेजी से विधि अंतिम आइटम (एक हे (1) समाधान) के पूर्ववर्ती को खोजने के लिए होगा:

range.exclude_end? ? range.last.pred : range.last 

यह केवल काम करता है पर्वतमाला तत्व है जो pred लागू होती हैं, के। रूबी के बाद के संस्करण पूर्णांक के लिए pred लागू करें। यदि आप मौजूद नहीं हैं तो आपको विधि को स्वयं जोड़ना होगा (अनिवार्य रूप से आपके द्वारा सुझाए गए विशेष केस कोड के बराबर, लेकिन लागू करने के लिए थोड़ा आसान)।

कुछ त्वरित बेंच मार्किंग, पता चलता है कि यह पिछले विधि बड़ी पर्वतमाला (इस मामले range = 1...1000000 में) के लिए परिमाण के कई क्रमों से सबसे तेजी से है, क्योंकि यह हे है (1):

          user  system  total  real 
r.entries.last      11.760000 0.880000 12.640000 (12.963178) 
r.entries[-1]      11.650000 0.800000 12.450000 (12.627440) 
last = nil; r.each { |v| last = v } 20.750000 0.020000 20.770000 (20.910416) 
r.max        17.590000 0.010000 17.600000 (17.633006) 
r.exclude_end? ? r.last.pred : r.last 0.000000 0.000000 0.000000 ( 0.000062) 

Benchmark code is here।

टिप्पणियों में यह range.last - (range.exclude_end? ? 1 : 0) का उपयोग करने का सुझाव दिया गया है। यह बिना किसी अतिरिक्त तरीके के तिथियों के लिए काम करता है, लेकिन गैर-संख्यात्मक श्रेणियों के लिए कभी काम नहीं करेगा। String#- मौजूद नहीं है और पूर्णांक तर्कों के साथ कोई समझ नहीं आता है। String#pred, हालांकि, can be implented।

Answer 2

मैं गति के बारे में यकीन नहीं है (और प्रारंभिक परीक्षण अविश्वसनीय रूप से तेजी से नहीं है), लेकिन निम्नलिखित आपको क्या चाहिए कर सकते हैं:

past = Time.local(2010, 1, 1, 0, 0, 0) 
now = Time.now 
range = past...now 

range.to_a[-1] 

बहुत बुनियादी परीक्षण (मेरे सिर में बढ़ रहा है) से पता चला आपके द्वारा प्रदान की गई विधि में लगभग 5-6 लगने में लगभग 4 सेकंड लग गए। उम्मीद है की यह मदद करेगा।

संपादित करें 1: दूसरा समाधान हटा दिया गया क्योंकि यह पूरी तरह से गलत था।

Answer 3

मुझे नहीं लगता कि यह प्राप्त करने का कोई तरीका है जिसमें सीमा का आकलन शामिल नहीं है, कम से कम जब तक कि पहले से ही उल्लेख नहीं किया गया है, आपके पास सीमा के निर्माण के तरीके के बारे में अन्य जानकारी है और इसलिए बिना वांछित मूल्य का अनुमान लगा सकते हैं गणन। सभी सुझावों में से, मैं #max के साथ जाऊंगा, क्योंकि यह सबसे अधिक अभिव्यक्तिपूर्ण प्रतीत होता है।

require 'benchmark' 
N = 20 
Benchmark.bm(30) do |r| 
    past, now = Time.local(2010, 2, 1, 0, 0, 0), Time.now 
    @range = past...now 
    r.report("range.max") do 
    N.times { last_in_range = @range.max } 
    end 
    r.report("explicit enumeration") do 
    N.times { @range.each { |value| last_in_range = value } } 
    end 
    r.report("range.entries.last") do 
    N.times { last_in_range = @range.entries.last } 
    end 
    r.report("range.to_a[-1]") do 
    N.times { last_in_range = @range.to_a[-1] } 
    end 
end 
           user  system  total  real 
range.max      49.406000 1.515000 50.921000 (50.985000) 
explicit enumeration   52.250000 1.719000 53.969000 (54.156000) 
range.entries.last    53.422000 4.844000 58.266000 (58.390000) 
range.to_a[-1]     49.187000 5.234000 54.421000 (54.500000) 

मुझे लगता है कि 3 और 4 विकल्प काफी सिस्टम का समय बढ़ा दिया है पर ध्यान दें। मुझे उम्मीद है कि यह एक सरणी के स्पष्ट निर्माण से संबंधित है, जो उनसे बचने के लिए एक अच्छा कारण प्रतीत होता है, भले ही वे स्पष्ट रूप से अधिक समय में अधिक महंगा न हों।