Obtenha o índice do elemento da matriz mais rápido do que O (n)

Dado que tenho uma matriz ENORME e um valor dela. Eu quero obter o índice do valor na matriz. Existe alguma outra maneira, em vez de ligar Array#indexpara pegá-lo? O problema vem da necessidade de manter um array realmente grande e chamar uma Array#indexquantidade enorme de vezes.

Depois de algumas tentativas, descobri que o armazenamento de índices em cache dentro de elementos, armazenando structs com (value, index)campos em vez do valor em si, dá um grande passo no desempenho (20x vezes a vitória).

Ainda assim, eu me pergunto se há uma maneira mais conveniente de encontrar o índice de um elemento sem cache (ou se há uma boa técnica de cache que aumentará o desempenho).

Converta a matriz em um hash. Em seguida, procure a chave.

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

Por que não usar index ou 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')

índice: 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

Outras respostas não levam em consideração a possibilidade de uma entrada listada várias vezes em um array. Isso retornará um hash em que cada chave é um objeto único na matriz e cada valor é uma matriz de índices que corresponde a onde o objeto reside:

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

Isso permite uma busca rápida por entradas duplicadas:

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

Existe um bom motivo para não usar hash? As pesquisas são O(1)vs. O(n)para a matriz.

Se for um array ordenado, você pode usar um algoritmo de busca binária ( O(log n)). Por exemplo, estendendo a classe Array com esta funcionalidade:

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

Pegando uma combinação da resposta de @ sawa e do comentário listado lá, você poderia implementar um índice "rápido" e rindex na classe de array.

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

Se sua matriz tem uma ordem natural, use a pesquisa binária.

Use a pesquisa binária.

A pesquisa binária tem O(log n)tempo de acesso.

Aqui estão as etapas sobre como usar a pesquisa binária,

• Qual é a ordem de sua matriz? Por exemplo, é classificado por nome?
• Use bsearchpara encontrar elementos ou índices

Exemplo de código

# 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

Ainda assim, eu me pergunto se há uma maneira mais conveniente de encontrar o índice de um elemento sem cache (ou se há uma boa técnica de cache que aumentará o desempenho).

Você pode usar a pesquisa binária (se o seu array estiver ordenado e os valores armazenados no array forem comparáveis ​​de alguma forma). Para que isso funcione, você precisa saber dizer à pesquisa binária se ela deve estar olhando "para a esquerda" ou "para a direita" do elemento atual. Mas eu acredito que não há nada de errado em armazenar o indexno momento da inserção e depois usá-lo se você estiver obtendo o elemento do mesmo array.