Obtenga el índice del elemento de la matriz más rápido que O (n)

Dado que tengo una ENORME matriz y un valor de ella. Quiero obtener el índice del valor en la matriz. ¿Hay alguna otra forma, en lugar de llamar Array#indexpara conseguirlo? El problema proviene de la necesidad de mantener una matriz realmente enorme y llamar una Array#indexgran cantidad de veces.

Después de un par de intentos, descubrí que el almacenamiento en caché de los índices dentro de los elementos almacenando estructuras con (value, index)campos en lugar del valor en sí da un gran paso en el rendimiento (20 veces más ganado).

Aún así, me pregunto si hay una forma más conveniente de encontrar el índice de un elemento sin almacenamiento en caché (o existe una buena técnica de almacenamiento en caché que aumentará el rendimiento).

Convierta la matriz en un hash. Luego busque la llave.

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

¿Por qué no usar index o 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

Otras respuestas no tienen en cuenta la posibilidad de que una entrada aparezca varias veces en una matriz. Esto devolverá un hash donde cada clave es un objeto único en la matriz y cada valor es una matriz de índices que corresponde al lugar donde vive el objeto:

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

Esto permite una búsqueda rápida de entradas duplicadas:

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

¿Existe una buena razón para no usar un hash? Las búsquedas son O(1)vs. O(n)para la matriz.

Si es una matriz ordenada , puede usar un algoritmo de búsqueda binaria ( O(log n)). Por ejemplo, ampliando la clase Array con esta funcionalidad:

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

Tomando una combinación de la respuesta de @ sawa y el comentario que aparece allí, podría implementar un índice "rápido" y un rindex en la clase de matriz.

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

Si su matriz tiene un orden natural, utilice la búsqueda binaria.

Utilice la búsqueda binaria.

La búsqueda binaria tiene O(log n)tiempo de acceso.

Estos son los pasos sobre cómo utilizar la búsqueda binaria,

• ¿Cuál es el orden de su matriz? Por ejemplo, ¿está ordenado por nombre?
• Úselo bsearchpara buscar elementos o índices

Ejemplo 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

Aún así, me pregunto si hay una forma más conveniente de encontrar el índice de un elemento sin almacenamiento en caché (o existe una buena técnica de almacenamiento en caché que aumentará el rendimiento).

Puede usar la búsqueda binaria (si su matriz está ordenada y los valores que almacena en la matriz son comparables de alguna manera). Para que eso funcione, necesita poder decirle a la búsqueda binaria si debe mirar "a la izquierda" o "a la derecha" del elemento actual. Pero creo que no hay nada de malo en almacenar el indexen el momento de la inserción y luego usarlo si obtiene el elemento de la misma matriz.