Obtenez l'index de l'élément du tableau plus rapidement que O (n)

Étant donné que j'ai un tableau ÉNORME, et une valeur de celui-ci. Je veux obtenir l'index de la valeur dans le tableau. Y a-t-il un autre moyen, plutôt que d'appeler Array#indexpour 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 la mise en cache des index à l'intérieur des éléments en stockant des structures avec des (value, index)champs au lieu de la valeur elle-même donne un énorme pas en avant dans les performances (20x fois gagnant).

Je me demande toujours s'il existe 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éliorera les performances).

Convertissez le tableau en hachage. Cherchez ensuite la clé.

array = ['a', 'b', 'c']
hash = Hash[array.map.with_index.to_a]    # => {"a"=>0, "b"=>1, "c"=>2}
hash['b'] # => 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')

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

D'autres réponses ne prennent pas en compte la possibilité d'une entrée répertoriée plusieurs fois dans un tableau. Cela retournera un hachage où chaque clé est un objet unique dans le tableau et chaque valeur est un tableau d'indices qui correspond à l'endroit où se trouve 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 entrées en double:

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

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

S'il s'agit d'un tableau trié , vous pouvez utiliser un algorithme de recherche binaire ( O(log n)). Par exemple, étendre 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

En combinant la réponse de @ sawa et le commentaire qui y est listé, vous pouvez implémenter un index "rapide" et un rindex sur la classe du tableau.

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 votre tableau a un ordre naturel, utilisez la recherche binaire.

Utilisez la recherche binaire.

La recherche binaire a O(log n)un temps d'accès.

Voici les étapes à suivre pour utiliser la recherche binaire,

• Quelle est la commande de votre tableau? Par exemple, est-il trié par nom?
• Utilisez bsearchpour rechercher des éléments ou des indices

Exemple de code

# 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

Je me demande toujours s'il existe 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éliorera les performances).

Vous pouvez utiliser la recherche binaire (si votre tableau est ordonné et que les valeurs que vous stockez dans le tableau sont comparables d'une certaine manière). Pour que cela fonctionne, vous devez être capable de dire à la recherche binaire si elle doit regarder "à gauche" ou "à droite" de l'élément courant. Mais je pense qu'il n'y a rien de mal à stocker le indexau moment de l'insertion, puis à l'utiliser si vous obtenez l'élément du même tableau.