ओ (एन)

Question

से अधिक सरणी तत्व की अनुक्रमणिका प्राप्त करें, मेरे पास एक विशाल सरणी है, और इससे एक मूल्य है। मैं सरणी में मान का सूचकांक प्राप्त करना चाहता हूं। क्या कोई अन्य तरीका है, इसके बजाय इसे पाने के लिए Array#index पर कॉल करें? समस्या वास्तव में विशाल सरणी रखने और Array#index पर भारी मात्रा में कॉल करने की आवश्यकता से आती है।

की कोशिश करता की एक जोड़ी के बाद मैंने पाया कि कैशिंग मूल्य खुद के बजाय (value, index) क्षेत्रों के साथ structs भंडारण के द्वारा तत्वों के अंदर अनुक्रमित प्रदर्शन में एक बड़ा कदम (20x बार जीता) देता है।

फिर भी मुझे आश्चर्य है कि कैशिंग के बिना एन तत्व के सूचकांक को खोजने का एक और सुविधाजनक तरीका है (या एक अच्छी कैशिंग तकनीक है जो प्रदर्शन को बढ़ावा देगी)।

Answer 1

सरणी को हैश में कनवर्ट करें। फिर कुंजी की तलाश करें।

array = ['a', 'b', 'c'] 
hash = Hash[array.map.with_index.to_a] # => {"a"=>0, "b"=>1, "c"=>2} 
hash['b'] # => 1 

Answer 2

क्या हैश का उपयोग न करने का कोई अच्छा कारण है? सरणी के लिए लुकअप O(1) बनाम O(n) हैं।

Answer 3

यदि यह एक आप एक द्विआधारी खोज एल्गोरिथ्म (O(log n)) इस्तेमाल कर सकते हैं अनुसार क्रमबद्ध सरणी है। उदाहरण के लिए, इस कार्यक्षमता के साथ ऐरे-क्लास का विस्तार:

class Array 
    def b_search(e, l = 0, u = length - 1) 
    return if lower_index > upper_index 

    midpoint_index = (lower_index + upper_index)/2 
    return midpoint_index if self[midpoint_index] == value 

    if value < self[midpoint_index] 
     b_search(value, lower_index, upper_index - 1) 
    else 
     b_search(value, lower_index + 1, upper_index) 
    end 
    end 
end 

Answer 4

इंडेक्स या रिन्डेक्स का उपयोग क्यों नहीं करें?

array = %w(a b c d e) 
# get FIRST index of element searched 
puts array.index('a') 
# get LAST index of element searched 
puts array.rindex('a') 

सूचकांक: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-index

rindex: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-rindex

Answer 5

@ सावा के जवाब का एक संयोजन और टिप्पणी वहाँ सूचीबद्ध आप सरणी पर एक "जल्दी" सूचकांक और rindex को लागू कर सकता है ले रहा है कक्षा।

class Array 
    def quick_index el 
    hash = Hash[self.map.with_index.to_a] 
    hash[el] 
    end 

    def quick_rindex el 
    hash = Hash[self.reverse.map.with_index.to_a] 
    array.length - 1 - hash[el] 
    end 
end 

Answer 6

अन्य उत्तरों एक सरणी में कई बार सूचीबद्ध प्रविष्टि की संभावना को ध्यान में रखते हैं। यह एक हैश वापस आ जाएगी जहां प्रत्येक कुंजी सरणी में एक अनूठा वस्तु है और प्रत्येक मूल्य सूचकांक की एक सरणी है कि जहां किसी चीज़ रहती है से मेल खाती है है:

a = [1, 2, 3, 1, 2, 3, 4] 
=> [1, 2, 3, 1, 2, 3, 4] 

indices = a.each_with_index.inject(Hash.new { Array.new }) do |hash, (obj, i)| 
    hash[obj] += [i] 
    hash 
end 
=> { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5], 4 => [6] } 

यह डुप्लिकेट प्रविष्टियों के लिए एक त्वरित खोज के लिए अनुमति देता है:

indices.select { |k, v| v.size > 1 } 
=> { 1 => [0, 3], 2 => [1, 4], 3 => [2, 5] } 

Answer 7

यदि आपके सरणी में प्राकृतिक आदेश बाइनरी खोज का उपयोग करता है।

बाइनरी खोज का उपयोग करें।

बाइनरी खोज में O(log n) पहुंच का समय है।

यहाँ कैसे द्विआधारी खोज का उपयोग करने पर कदम उठाए जाते हैं,

• आप सरणी के आदेश क्या है? उदाहरण के लिए, क्या यह नाम से क्रमबद्ध है?
• उपयोग bsearch तत्वों को खोजने या सूचकांक

कोड उदाहरण

# assume array is sorted by name! 

array.bsearch { |each| "Jamie" <=> each.name } # returns element 
(0..array.size).bsearch { |n| "Jamie" <=> array[n].name } # returns index