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

Si votre tableau a un ordre naturel, utilisez la recherche binaire.

Utilisez la recherche binaire.

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

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

• Quel est l'ordre de votre tableau ? Par exemple, est-il trié par nom ?
• Utilisez bsearch pour trouver 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

Answer 2

En combinant la réponse de @sawa et le commentaire qui y figure, vous pourriez implémenter un index "rapide" et un rindex sur la classe 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

Answer 3

Je me demande quand 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).

Vous pouvez utiliser la recherche binaire (si votre tableau est ordonné). et les valeurs que vous stockez dans le tableau sont comparables d'une certaine manière). Pour que cela fonctionne, vous devez être en mesure d'indiquer à la recherche binaire si elle doit chercher "à gauche" ou "à droite" de l'élément actuel. Mais je pense qu'il n'y a rien de mal à stocker la valeur index au moment de l'insertion et l'utiliser ensuite si vous récupérez l'élément dans le même tableau.