Vous n'êtes pas si difficile sans votre voiture. La plus rapide liste de recherche

StackOverflow https://stackoverflow.com/questions/1570547

  •  21-09-2019
  •  | 
  •  

Question

J'ai une collection de structures. Chaque structure dispose de 2 touches. Si je fais une recherche en utilisant la clé # 1, j'obtenir la clé # 2 en retour et vice-versa.

Il est facile d'écrire du code sur le bureau lorsque vous avez la puissance du .NET Framework derrière vous. Je suis en train d'écrire le code dans le .NET Micro Framework, qui est un sous-ensemble très limité de cadre. Par exemple, dans la mesure où les collections, je n'ai que des tableaux et des objets ArrayList à ma disposition.

Ainsi, par exemple est ici la liste des structures: 

Key #1        Key #2 
6             A
7             F
8             Z
9             B

Alors, quand je fais une recherche 8, je devrais obtenir Z. Lorsque je fais une recherche Z, je devrais 8.

Je cherche à faire le plus rapide et moins processeur recherche intensive en utilisant soit des tableaux ou ArrayList. Le dispositif que je suis contre le codage est un processeur ARM bas de gamme, donc je dois optimiser tôt.

Était-ce utile?

La solution

Si l'ensemble est fixé, regardez dans fonctions de hachage parfaites .

Autres conseils

Quel est le motif que vous ne pouvez pas écrire votre propre hashmap?

Cela dépend du nombre d'entrées et de votre modèle d'accès.

Étant donné que votre modèle d'accès est un accès aléatoire si vous ne vous pourriez avoir pas trop d'éléments ont 2 tableaux de paires et utilisez ensuite 

Array.BinarySearch()

Eh bien ... si vous voulez que le le plus rapide et ne sont pas trop préoccupés par la mémoire, il suffit d'utiliser deux tables de hachage. Un va dans un sens, on va à l'autre. Je ne sais pas s'il y a un moyen plus efficace de la mémoire ...

Ou utiliser une seule table de hachage, mais ont les entrées pour les deux sens là-dedans.

est-il pas aussi simple que:

  • trouver la clé du tableau vous interrogez
  • retourner la clé à la même indice dans le tableau opposé

Je garderais aussi simple que possible et juste parcourir le tableau que vous recherchez. Vous aurez probablement voir un avantage de mettre en œuvre certaines routines de hachage si votre liste est (figure Déplume de l'air) sur 1k + éléments, à la complexité accrue de vos propres routines de hachage ralentir les choses un peu.

Plusieurs solutions:

  1. Gardez 2 listes en synchronisation, faites une recherche linéaire. Fonctionne bien à moins que vos collections sont très grandes, ou vous cherchez à plusieurs reprises.
  2. Deux tables de hachage. La rédaction de votre propre est assez facile - il est juste un tableau fixe de godets (chaque godet peut être un ArrayList). Carte un élément à un seau en faisant object.GetHashCode() % numBuckets.
  3. Deux tableaux de la taille de la plage de valeurs. Si vos chiffres sont dans une plage fixe, allouer un tableau de la taille de la gamme, avec des éléments étant des éléments de l'autre groupe. Super rapide et facile, mais utilise beaucoup de mémoire.

Si c'est un ensemble fixe, envisagez d'utiliser switch. Voir réponse à une question similaire ici.

J'ai eu ce problème il y a quelques années lors de la programmation C, que nous devons trouver un code à barres (numérique) rapidement environ 10 mille lignes (en ce moment, en utilisant un fichier comme la base de données - comme il était un dispositif à main)

J'ai créé ma propre recherche qu'au lieu d'itérer un par un commencerait toujours au milieu ...

recherche de 4050 à 10000 pile d'élément

  

commencer à 5000 (10 000/2)
  maintenant, est le nombre plus ou moins élevé ... inférieur

     

commencer à 2500 (5000/2)
  maintenant, est le nombre plus ou moins élevé ... plus

     

start sur 3750 (2500 + 2500/2)
  maintenant, est le nombre plus ou moins élevé ... plus

     

start sur 4375 (3750 + 1250/2)
  maintenant, est le nombre plus ou moins élevé ... inférieur

     

commencer sur 4063 (4375 - 625/2)
  maintenant, est le nombre plus ou moins élevé ... inférieur

     

commencer sur 3907 (4063 - 312/2)
  maintenant, est le nombre plus ou moins élevé ... plus

     

start sur 3907 (3907 + 156/2)
  maintenant, est le nombre plus ou moins élevé ... plus

     

start sur 3946 (3907 + 78/2)
  maintenant, est le nombre plus ou moins élevé ... plus

...

jusqu'à ce que vous obtenez la valeur ... vous devez rechercher environ 14 fois au lieu 4050 itérations

sur les lettres ... ils représentent tous un nombre numérique et ...

it helps

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top