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

Dado que tengo una matriz ENORME, y un valor de ella. Quiero obtener el índice del valor en el conjunto. ¿Hay alguna otra forma, en lugar de llamar al Array#index para obtenerlo? El problema proviene de la necesidad de mantener enormes cantidades y llamar al Array#index muchísimas veces.Obtener índice del elemento de matriz más rápido que O (n)

Después de un par de intentos me encontré con que el almacenamiento en caché índices dentro de los elementos de almacenamiento de estructuras con (value, index) campos en vez del valor en sí da un paso enorme en el rendimiento (20x veces ganan).

Todavía me pregunto si hay una forma 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).

Fuente

2011-06-05 gmile

112

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

Fuente

2011-06-05 10:41:14 sawa

más rápido si la matriz es muy larga – Kevin

+16

Dependiendo de su caso de uso, esto podría ser problemático si hay valores duplicados. El método descrito anteriormente devolverá el equivalente o #rindex (última aparición de valor) Para obtener resultados equivalentes a #index, lo que significa que el hash devolverá el primer índice del valor que necesitaría para hacer algo en la línea de inversión la matriz antes de crear el hash y luego restar el valor del índice devuelto de la longitud total de la matriz inicial: 1. # (array.length - 1) - hash ['b'] – ashoda

¿No es la conversión en hash? ¿A tiempo? Supongo que si va a usarse más de una vez, la conversión hash será más eficiente. pero para un solo uso, ¿no es diferente luego de iterar a través de la matriz? – ahnbizcad

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

Fuente

2011-06-05 10:41:07

El punto es - Voy a llamar '# keys' de hachís, que devuelve una matriz que estoy utilizando. Aún así, podría pensar en mi arquitectura también ... – gmile

Si es un ordenados matriz se puede utilizar 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

Fuente

2011-06-05 10:52:28 isakkarlsson

U ¿Esto es simple de leer? La lógica detrás de una respuesta es entregar el mensaje de una manera fácil y usted puede expresar claramente su punto de vista. – YoniGeek

Realmente no es tan difícil de leer. Primera parte, regresa si el límite inferior es más grande que el límite superior (la recursión se ha archivado). La segunda parte verifica si necesitamos el lado izquierdo o el lado derecho comparando el punto medio m con el valor en ese punto a e. si no tenemos la respuesta que queremos, recurrimos. – ioquatix

Creo que es mejor para el ego de las personas votar menos que editar. –

199

¿Por qué no utilizar 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

Fuente

2012-07-24 08:05:14 Roger

+12

Esto es exactamente lo que OP dijo que NO QUERÍA, debido al gran tamaño de su matriz. El índice de matriz # es O (n) y hacer eso varias veces eliminará el rendimiento. La búsqueda Hash es O (1). – Tim

@tim, bueno, no recuerdo en el momento de mi respuesta que ESTA era la ** misma ** pregunta, quizás el OP revisó la pregunta más tarde, lo que invalidaría esta respuesta. – Roger

¿No diría que se había editado en un momento específico, entonces? – Tim

Tomar una combinación de respuesta de @ Sawa y el comentario que aparece allí se podía aplicar un índice de "rápida" y rindex en la matriz clase.

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

Fuente

2015-02-09 03:13:07 ianstarz

Otras respuestas no tienen en cuenta la posibilidad de una entrada enumerada varias veces en una matriz. Esto devolverá un hash, donde cada tecla es un objeto único de la matriz y cada valor es una serie 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] }

Fuente

2015-07-12 03:30:13 hololeap

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.

Éstos son los pasos a seguir para utilizar la búsqueda binaria,

¿Cuál es el orden de usted matriz? Por ejemplo, ¿está ordenado por nombre?
bsearch Uso de encontrar elementos o índices

ejemplo 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

Fuente

2016-12-26 00:23:14 akuhn

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

Respuesta

Cuestiones relacionadas