Trouvez rapidement si une valeur est présente dans un tableau C?c


Answers

Il y a un truc pour l'optimiser (on m'a posé cette question lors d'un entretien d'embauche une fois):

  • Si la dernière entrée du tableau contient la valeur que vous recherchez, renvoyez true
  • Écrivez la valeur que vous recherchez dans la dernière entrée du tableau
  • Itérer le tableau jusqu'à ce que vous rencontriez la valeur que vous recherchez
  • Si vous l'avez rencontré avant la dernière entrée du tableau, renvoyez true
  • Retourner false
bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    uint32_t x = theArray[SIZE-1];
    if (x == compareVal)
        return true;
    theArray[SIZE-1] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    theArray[SIZE-1] = x;
    return i != SIZE-1;
}

Cela donne une branche par itération au lieu de deux branches par itération.

METTRE À JOUR:

Si vous êtes autorisé à allouer le tableau à SIZE+1 , vous pouvez vous débarrasser de la partie "last swapping":

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    theArray[SIZE] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    return i != SIZE;
}

Vous pouvez également vous débarrasser de l'arithmétique supplémentaire incorporée dans theArray[i] , en utilisant ce qui suit à la place:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t *arrayPtr;
    theArray[SIZE] = compareVal;
    for (arrayPtr = theArray; *arrayPtr != compareVal; arrayPtr++);
    return arrayPtr != theArray+SIZE;
}

Si le compilateur ne l'applique pas déjà, alors cette fonction le fera à coup sûr. D'un autre côté, il peut être plus difficile pour l'optimiseur de dérouler la boucle, vous devrez donc le vérifier dans le code d'assemblage généré ...

Question

J'ai une application incorporée avec un ISR à temps critique qui a besoin de parcourir un tableau de taille 256 (de préférence 1024, mais 256 est le minimum) et de vérifier si une valeur correspond au contenu des tableaux. Un bool sera mis à vrai, c'est le cas. MCU est un NXP LPC4357, noyau ARM Cortex M4, le compilateur est GCC. J'ai déjà combiné le niveau d'optimisation 2 (3 est plus lent) et place la fonction en RAM au lieu de flash. J'utilise aussi l'arithmétique du pointeur et une boucle for , qui effectue le down-counting au lieu de up (vérifier si i!=0 est plus rapide que de vérifier si i<256 ). Dans l'ensemble, je me retrouve avec une durée de 12.5us qui doit être réduite drastiquement pour être réalisable. C'est le (pseudo) code que j'utilise maintenant:

uint32_t i;
uint32_t *array_ptr = &theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
    if (compareVal == *array_ptr++)
    {
         validFlag = true;
         break;
     }
}

Quel serait le moyen le plus rapide absolu de faire cela? L'utilisation de l'assemblage en ligne est autorisée. D'autres astuces «moins élégantes» sont également permises.




Conservez la table dans l'ordre trié et utilisez la recherche binaire déroulée de Bentley:

i = 0;
if (key >= a[i+512]) i += 512;
if (key >= a[i+256]) i += 256;
if (key >= a[i+128]) i += 128;
if (key >= a[i+ 64]) i +=  64;
if (key >= a[i+ 32]) i +=  32;
if (key >= a[i+ 16]) i +=  16;
if (key >= a[i+  8]) i +=   8;
if (key >= a[i+  4]) i +=   4;
if (key >= a[i+  2]) i +=   2;
if (key >= a[i+  1]) i +=   1;
return (key == a[i]);

Le point est,

  • Si vous savez quelle est la taille de la table, alors vous savez combien d'itérations il y aura, donc vous pouvez la dérouler complètement.
  • Ensuite, il est inutile de tester le cas == sur chaque itération, car, sauf lors de la dernière itération, la probabilité de ce cas est trop faible pour justifier le test du temps passé. **
  • Finalement, en augmentant la table à une puissance de 2, vous ajoutez au plus une comparaison, et au plus un facteur de deux.

** Si vous n'avez pas l'habitude de penser en termes de probabilités, chaque point de décision a une entropie , qui est la moyenne des informations que vous apprenez en l'exécutant. Pour les tests >= , la probabilité de chaque branche est d'environ 0.5, et -log2 (0.5) est 1, ce qui signifie que si vous prenez une branche, vous apprenez 1 bit, et si vous prenez l'autre branche, vous apprenez un bit, et la moyenne n'est que la somme de ce que vous apprenez sur chaque branche multipliée par la probabilité de cette branche. Donc 1*0.5 + 1*0.5 = 1 , donc l'entropie du test >= est 1. Puisque vous avez 10 bits à apprendre, il faut 10 branches. C'est pourquoi c'est rapide!

D'un autre côté, que se passe-t-il si votre premier test est if (key == a[i+512) ? La probabilité d'être vrai est de 1/1024, alors que la probabilité de faux est de 1023/1024. Donc, si c'est vrai, vous apprendrez tous les 10 bits! Mais si c'est faux, vous apprendrez -log2 (1023/1024) = 0,00141 bits, pratiquement rien! Donc la quantité moyenne que vous apprenez de ce test est 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112 bits. Environ un centième de peu. Ce test ne porte pas son poids!




Utilisez un ensemble de hachage. Cela donnera O (1) temps de recherche.

Le code suivant suppose que vous pouvez réserver la valeur 0 comme valeur «vide», c'est-à-dire ne pas apparaître dans les données réelles. La solution peut être étendue pour une situation où ce n'est pas le cas.

#define HASH(x) (((x >> 16) ^ x) & 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
    int i = HASH(value);
    while (my_hash[i] != 0 && my_hash[i] != value) i = (i + 1) % HASH_LEN;
    return i;
}

void store(uint32_t value)
{
    int i = lookup(value);
    if (my_hash[i] == 0)
       my_hash[i] = value;
}

bool contains(uint32_t value)
{
    return (my_hash[lookup(value)] == value);
}

Dans cet exemple d'implémentation, le temps de recherche sera généralement très faible, mais dans le pire des cas, il peut aller jusqu'au nombre d'entrées stockées. Pour une application en temps réel, vous pouvez également envisager une implémentation utilisant des arbres binaires, ce qui aura un temps de recherche plus prévisible.




En supposant que votre processeur fonctionne à 204 MHz, ce qui semble être le maximum pour le LPC4357, et en supposant également que votre résultat de synchronisation reflète le cas moyen (la moitié du tableau traversé), nous obtenons:

  • Fréquence du processeur: 204 MHz
  • Période de cycle: 4,9 ns
  • Durée en cycles: 12,5 μs / 4,9 ns = 2551 cycles
  • Cycles par itération: 2551/128 = 19.9

Ainsi, votre boucle de recherche passe environ 20 cycles par itération. Cela ne semble pas terrible, mais je suppose que pour accélérer le processus, il faut regarder l'assemblée.

Je recommande de laisser tomber l'index et d'utiliser une comparaison de pointeurs à la place, et de faire tous les pointeurs const .

bool arrayContains(const uint32_t *array, size_t length)
{
  const uint32_t * const end = array + length;
  while(array != end)
  {
    if(*array++ == 0x1234ABCD)
      return true;
  }
  return false;
}

Cela vaut au moins la peine d'être testé.




La vectorisation peut être utilisée ici, comme c'est souvent le cas dans les implémentations de memchr. Vous utilisez l'algorithme suivant:

  1. Créez un masque de votre requête en répétant, égal en longueur au nombre de bits de votre système d'exploitation (64 bits, 32 bits, etc.). Sur un système 64 bits, vous répétez deux fois la requête 32 bits.

  2. Traitez la liste comme une liste de plusieurs éléments de données à la fois, en convertissant simplement la liste en liste de types de données plus importants et en extrayant des valeurs. Pour chaque tronçon, XOR avec le masque, puis XOR avec 0b0111 ... 1, puis ajouter 1, puis & avec un masque de 0b1000 ... 0 répétition. Si le résultat est 0, il n'y a certainement pas de correspondance. Sinon, il peut y avoir une correspondance (habituellement avec une probabilité très élevée), alors recherchez normalement le bloc.

Exemple de mise en œuvre: https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src




Je suis désolé si ma réponse a été déjà répondu - que je suis un lecteur paresseux. Sentez-vous libre de downvote alors))

1) vous pouvez supprimer contre « i » du tout - il suffit de comparer les pointeurs, à savoir

for (ptr = &the_array[0]; ptr < the_array+1024; ptr++)
{
    if (compareVal == *ptr)
    {
       break;
    }
}
... compare ptr and the_array+1024 here - you do not need validFlag at all.

tout ce qui ne donnera aucune amélioration significative cependant, une telle optimisation pourrait probablement être atteint par le compilateur lui-même.

2) Comme il a déjà été mentionné par d'autres réponses, presque toutes les CPU modernes sont basées RISC, par exemple ARM. Même modernes processeurs Intel X86 utiliser des noyaux RISC à l'intérieur, pour autant que je sais (compilation à partir X86 à la volée). Optimisation majeure pour l'optimisation des RISC est pipeline (et pour Intel et d'autres CPU ainsi), le code réduisant au minimum les sauts. Un type d'une telle optimisation (probablement un moment important), est « rollback de cycle » un. Il est incroyablement stupide et efficace, même compilateur Intel peut faire autant que je sache. Ça ressemble à:

if (compareVal == the_array[0]) { validFlag = true; goto end_of_compare; }
if (compareVal == the_array[1]) { validFlag = true; goto end_of_compare; }
...and so on...
end_of_compare:

De cette façon, l'optimisation est que le pipeline est pas cassé pour le pire des cas (si compareVal est absent dans le tableau), il est donc aussi vite que possible (bien sûr sans compter l'optimisation des algorithmes tels que des tables de hachage, tableaux triés et ainsi de suite, mentionné dans d'autres réponses, ce qui peut donner de meilleurs résultats en fonction de la taille du tableau. les cycles Rollback approche peut être appliquée là aussi par la manière. J'écris ici à ce sujet, je pense que je ne l'ai pas vu dans d'autres)

La deuxième partie de cette optimisation est que cet élément de tableau est prise par adresse directe (calculée à l'étape compilation, assurez-vous d'utiliser un tableau statique), et ne pas besoin op supplémentaire ADD pour calculer le pointeur de l'adresse de base de tableau. Cette optimisation ne peut pas avoir un effet significatif, étant donné que l'architecture ARM a des caractéristiques AFAIK spéciales pour accélérer les réseaux d'adressage. Mais de toute façon, il est toujours préférable de savoir que vous avez fait le meilleur juste en code C directement, non?

Cycle Rollback peut sembler maladroite à cause de déchets de ROM (eh oui, vous avez bien fait de le placer à jeûner une partie de RAM, si votre carte prend en charge cette fonction), mais en réalité il est un salaire équitable pour la vitesse, étant basée sur le concept RISC. Ceci est juste un point général de l'optimisation de calcul - vous l'espace sacrifice pour l'amour de la vitesse, et vice versa, en fonction de vos besoins.

Si vous pensez que rollback pour un tableau de 1024 éléments est trop grand sacrifice pour votre cas, vous pouvez envisager « rollback partiel », par exemple en divisant le tableau en 2 parties de 512 pièces chacune, 4x256, et ainsi de suite.

3) CPU modernes prennent en charge souvent ops SIMD, par exemple ARM jeu d'instructions NEON - il permet d'exécuter les mêmes opérations en parallèle. Pour parler franchement , je ne me souviens pas si elle est appropriée pour les opérations de comparaison, mais je pense qu'il peut être, vous devriez vérifier. Googler montre qu'il peut y avoir quelques trucs aussi bien, pour obtenir la vitesse maximale, voir https://.com/a/5734019/1028256

J'espère que cela peut vous donner quelques idées nouvelles.




Je suis un grand fan de hash. Le problème est bien sûr de trouver un algorithme efficace qui est à la fois rapide et utilise une quantité minimale de mémoire (en particulier sur un processeur embarqué).

Si vous savez d'avance les valeurs qui peuvent se produire, vous pouvez créer un programme qui passe par une multitude d'algorithmes pour trouver le meilleur - ou plutôt les meilleurs paramètres pour vos données.

J'ai créé un tel programme que vous pouvez lire dans ce post et obtenu des résultats très rapides. 16000 entrées signifie à peu près 2 ^ 14 soit une moyenne de 14 comparaisons pour trouver la valeur en utilisant une recherche binaire. Je visais explicitement très rapide lookups - sur la recherche de la valeur moyenne en <= 1,5 lookups - ce qui a entraîné des besoins plus importants de RAM. Je crois que , avec une valeur moyenne plus conservatrice (disons <= 3) beaucoup de mémoire pourrait être sauvé. Par comparaison , le cas moyen d'une recherche binaire sur votre 256 ou 1024 entrées entraînerait un nombre moyen de comparaisons entre 8 et 10, respectivement.

Ma recherche moyenne requise environ 60 cycles (sur un ordinateur portable avec un i5 intel) avec un algorithme générique (utilisant une division par une variable) et cycles avec une 40-45 spécialisée (utilisant probablement une multiplication). Cela devrait se traduire en sous-microseconde temps de consultation sur votre MCU, en fonction bien sûr de la fréquence d'horloge qu'il exécute à.

Il peut être peaufiné-vie réelle plus si le tableau d'entrée garde la trace de combien de fois une entrée a été consulté. Si le tableau d'entrée est triée du plus au moins avant que les indeces accessibles sont calculés puis il va trouver les valeurs le plus souvent avec se produisant une seule comparaison.