ruby - elementos - Obtener índice del elemento de matriz más rápido que O(n)

crear lista en ruby

Question

Dado que tengo una gran variedad, y un valor de ella. Quiero obtener el índice del valor en el conjunto. ¿Hay alguna otra manera, en lugar de llamar a Array#index para obtenerlo? El problema proviene de la necesidad de mantener una matriz realmente enorme y de llamar a Array#index enormes cantidades de veces.

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

Todavía me pregunto si hay una manera más conveniente de encontrar el índice de elemento sin almacenamiento en caché (o hay una buena técnica de almacenamiento en caché que aumentará el rendimiento).

Answer 1

¿Hay alguna buena razón para no usar un hash? Las búsquedas son O(1) frente a O(n) para la matriz.

Answer 2

¿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

Answer 3

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

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

Answer 4

Otras respuestas no tienen en cuenta la posibilidad de una entrada enumerada 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 a 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] }

Answer 5

Si se trata de una matriz ordenada , puede usar un algoritmo de búsqueda Binario ( O(log n) ). Por ejemplo, extendiendo 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

Answer 6

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

Utilice la búsqueda binaria.

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

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

• ¿Cuál es el orden de tu array? Por ejemplo, ¿está ordenado por nombre?
• Use bsearch para encontrar 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

Answer 7

Tomando una combinación de la respuesta de @sawa y el comentario allí enumerado, puede implementar un índice "rápido" y 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