रूबी गणनीय रिवर्स का पता लगाने के

संभालने मैं निम्नलिखित सरणी है:रूबी गणनीय रिवर्स का पता लगाने के

views = [ 
    { :user_id => 1, :viewed_at => '2012-06-29 17:03:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:04:28 -0400' }, 
    { :user_id => 2, :viewed_at => '2012-06-29 17:05:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:06:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:07:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:08:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:09:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:16:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:26:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:36:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:47:28 -0400' }, 
    { :user_id => 2, :viewed_at => '2012-06-29 17:57:28 -0400' }, 
    { :user_id => 3, :viewed_at => '2012-06-29 17:67:28 -0400' }, 
    { :user_id => 1, :viewed_at => '2012-06-29 17:77:28 -0400' } 
]

सरणी संभालने viewed_at

द्वारा आदेश दिया जाता है तो मैं विचारों में पिछली बार देखे जाने हैश पुनः प्राप्त करना चाहते हैं के लिए सरणी एक विशेष user_id, मैं निम्नलिखित कर सकता था:

views.reverse.detect { |view| view[:user_id] == 1 }

जहां पता पहले आइटम को एक गणना में वापस कर देगा जहां ब्लॉक सही साबित होता है।

मेरा प्रश्न है: मुझे लगता है कि रिवर्स विधि के लिए लागत है, तो मैं सरणी को उलट किए बिना रिवर्स में कैसे पता लगा सकता हूं? या रिवर्स विधि O(n) नहीं है?

स्रोत

2012-06-29 Patrick Klingemann

तुम सच में 'क्या है 17? –

जब आप विधियों को व्यवस्थित करते हैं, तो आप हमेशा गणनाकर्ताओं को चेन करना चाहते हैं। गणनाकर्ता श्रृंखला केवल ऑब्जेक्ट को फिर से सक्रिय करती है और ओ (एन) है। सबसे आम उदाहरण है "हैलो" .each_char.map {| x | x.succ} ' – texasbruce

@texasbruce: यह रूबी 2.0 के साथ पूरी तरह से सच होगा, जहां सभी प्रकार के आलसी संचालन संभव होंगे (अब बहुत सारे ऑपरेशन रिटर्न सरणी, गणनाकर्ता नहीं) – tokland

विधि Array#reverse समय और स्थान में ओ (एन) है। चूंकि आपको पूरी उलटा सरणी की आवश्यकता नहीं है, तो आप Array#reverse_each का उपयोग कर सकते हैं, जो अंतरिक्ष में ओ (1) होगा। अभ्यास में, यह वास्तव में बड़े सरणी के लिए केवल प्रासंगिक है।

views.reverse_each.detect { |view| view[:user_id] == 1 } 
#=> {:user_id=>1, :viewed_at=>"2012-06-29 17:77:28 -0400"}

स्रोत

2012-06-29 21:25:45 tokland

यह बहुत दिलचस्प है। मैंने रुबी 1.9.3 में प्रत्येक विधि को रिवर्स देखा। गणनात्मक दस्तावेज, लेकिन इसका नाम यह दर्शाता है कि यह प्रत्येक वस्तु के माध्यम से एक गणना में पुनरावृत्त करता है। मैं आपके उदाहरण से देखता हूं कि यह संभवतः नहीं (संभावित रूप से यह कर सकता है)। क्या आप इस संदर्भ में एक स्थान के बीच अंतर को समझाते हैं। आपके विचारशील उत्तर के लिए धन्यवाद! –

"इसका नाम इंगित करता है कि यह प्रत्येक वस्तु के माध्यम से एक गणना में पुनरावृत्त करता है"। रूबी में प्रत्येक 'विधियां हमेशा आलसी होती हैं, अगर वे पूछे जाने पर पूरी गणना को पुन: सक्रिय करते हैं, लेकिन जब यह पता लगाएगा कि' पता 'अधिक मूल्यों के लिए पूछता है तो यह रुक जाएगा। "क्या आप इस संदर्भ में एक स्थान के बीच अंतर को समझाएंगे"। रिवर्स_चैच का उपयोग करना: समय) मिलान करने वाले को खोजने के लिए आपको संभावित इनपुट को पार करने की आवश्यकता है, इसलिए यह सबसे खराब स्थिति, स्थान में रैखिक ओ (एन) है) आपको केवल मौजूदा तत्व को चेक करने की आवश्यकता है, यह ओ (1) है। पायथन में उदाहरण: http://wiki.python.org/moin/TimeComplexity – tokland

आपको बहुत बहुत धन्यवाद! –

यह अंतिम वस्तु से सूचकांक प्राप्त करेगा जिसके लिए ब्लॉक सत्य है (या शून्य अगर कोई मेल नहीं खाता है)। एक समय के रूप 77`:

views.rindex{|view| view[:user_id] == 1}

बेंचमार्किंग @toklands reverse_each के बाद (मेरे लिए आश्चर्य की बात है) बहुत तेजी से:

require 'benchmark' 
ar = Array.new(100){rand(100)} 
target = rand(100) 

Benchmark.bm(15) do |x| 
    x.report('reverse_each'){1000.times{ar.reverse_each.detect(target)}} 
    x.report('rindex'){1000.times{ar.rindex(target)}} 
end 


#      user  system  total  real 
#reverse_each  0.000000 0.000000 0.000000 ( 0.002981) 
#rindex   0.020000 0.000000 0.020000 ( 0.012078)

स्रोत

2012-06-29 21:36:13 steenslag

वास्तव में आश्चर्य की बात है, अवधारणात्मक रूप से यह एक ही ऑपरेशन है, समय बहुत समान होना चाहिए। – tokland

रूबी गणनीय रिवर्स का पता लगाने के

उत्तर

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