Obtenir l'index d'un élément de tableau plus rapidement que O(n)

Question

Étant donné que j'ai un GRAND tableau, et une valeur de celui-ci. Je veux obtenir l'index de la valeur dans le tableau. Existe-t-il un autre moyen, plutôt que d'appeler Array#index pour l'obtenir ? Le problème vient de la nécessité de conserver un tableau vraiment énorme et d'appeler Array#index énormément de fois.

Après quelques essais, j'ai trouvé que mise en cache les index à l'intérieur des éléments en stockant les structs avec (value, index) au lieu de la valeur elle-même donne un énorme gain de performance (20x le gain).

Je me demande tout de même s'il n'y a pas un moyen plus pratique de trouver l'index d'un élément sans mise en cache (ou s'il existe une bonne technique de mise en cache qui améliore les performances).

Answer 1

Pourquoi ne pas utiliser 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')

l'index : 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 2

Convertir le tableau en hachage. Puis cherchez la clé.

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

Answer 3

Les autres réponses ne prennent pas en compte la possibilité qu'une entrée soit listée plusieurs fois dans un tableau. Cette réponse renverra un hachage où chaque clé est un objet unique dans le tableau et chaque valeur est un tableau d'indices qui correspond à l'emplacement de l'objet :

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

Cela permet une recherche rapide des doublons :

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

Answer 4

Y a-t-il une bonne raison de ne pas utiliser un hachage ? Les recherches sont O(1) vs. O(n) pour le tableau.

Answer 5

Si c'est un trié vous pouvez utiliser un algorithme de recherche binaire ( O(log n) ). Par exemple, l'extension de la classe Array avec cette fonctionnalité :

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