獲取數組元素的索引比O（n）更快

鑑於我有一個巨大的數組，以及它的值。我想獲得數組中的值的索引。有沒有其他的方法，而不是打電話Array#index得到它？這個問題來自保持真正巨大的陣列的需要並且呼叫Array#index巨大的時間。獲取數組元素的索引比O（n）更快

多試幾次後，我發現，緩存中的元素指標通過存儲結構與(value, index)領域，而不是本身的價值給出了性能的一大步（20X次奪冠）。

我還想知道是否有一種更方便的方式來查找沒有緩存的en元素索引（或者有一個好的緩存技術可以提高性能）。

來源

2011-06-05 gmile

112

將數組轉換爲散列。然後尋找鑰匙。

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

來源

2011-06-05 10:41:14 sawa

如果陣列很長，則速度最快 – Kevin 2012-11-19 19:13:50

+16

根據您的使用情況，如果存在重複值，則可能會出現問題。上述方法將返回等價或#rindex（最後一次出現的值）要獲得#index等效結果，意味着返回值的第一個索引的散列需要沿着反轉的方向在創建散列之前的數組，然後從初始數組的總長度中減去返回的索引值 - 1. ＃（array.length - 1） - hash ['b'] – ashoda 2013-05-30 02:49:37

不轉換爲散列準時？我猜想如果它將被多次使用，那麼散列轉換將更加高效。但對於一次性使用，是否沒有不同，然後遍歷數組？ – ahnbizcad 2016-09-16 19:45:53

有沒有好的理由不使用哈希？查找數組爲O(1)與O(n)。

來源

2011-06-05 10:41:07

重點是 - 我打電話'＃keys'哈希，它返回我使用數組。不過，我可能會考慮我的架構以及... – gmile 2011-06-05 12:29:28

如果它是一個分類陣列可以使用二進制搜索算法（O(log n)）。例如，使用此功能擴展Array類：

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

來源

2011-06-05 10:52:28 isakkarlsson

你認爲這很容易閱讀？答案背後的邏輯是以簡單的方式傳遞信息，並且可以清晰地表達你的觀點。 – YoniGeek 2014-06-14 12:21:08

它實際上並不難讀。第一部分，如果下界大於上界（遞歸已存檔），則返回。第二部分通過比較中點m和該點到e的值來檢查我們是否需要左側或右側。如果我們沒有我們想要的答案，我們就會緩解。 – ioquatix 2014-07-20 08:17:43

我認爲這對人們自我低估而不是編輯更好。 – 2017-06-06 21:07:13

199

爲什麼不使用索引或rindex？

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

來源

2012-07-24 08:05:14 Roger

+12

由於數組的大小，這正是OP表示他們不想要的東西。 Array＃索引是O（n），並且多次執行會影響性能。哈希查找是O（1）。 – Tim 2013-05-01 03:46:47

@tim，以及我在回答時記不清這是**相同的問題，也許OP稍後修改了這個問題，這將使這個答案失效。 – Roger 2013-05-01 07:41:32

那不是說它已經在特定的時間編輯過了嗎？ – Tim 2013-05-01 21:08:41

以@澤的回答的組合和那裏列出的評論，你可以實現陣列上的「快速」指數和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

來源

2015-02-09 03:13:07 ianstarz

其他答案沒有考慮到一個條目在列表中多次列出的可能性。這將返回一個散列結果，其中每個鍵是數組中唯一的對象和每個值是索引數組對應於對象的居住地：

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] }

來源

2015-07-12 03:30:13 hololeap

如果您的數組有自然順序使用二進制搜索。

使用二進制搜索。

二進制搜索有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

來源

2016-12-26 00:23:14 akuhn

獲取數組元素的索引比O（n）更快

回答

相關問題