Trouvez rapidement si une valeur est présente dans un tableau 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 d'itérer à travers un tableau de taille 256 (de préférence 1024, mais 256 est le minimum) et 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 (en vérifiant si i!=0 est plus rapide qu'en vérifiant 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.




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

1) vous pouvez supprimer le «je» 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 cela ne donnera cependant pas d'amélioration significative, une telle optimisation pourrait probablement être réalisée par le compilateur lui-même.

2) Comme cela a déjà été mentionné par d'autres réponses, presque toutes les CPU modernes sont basées sur RISC, par exemple ARM. Même les processeurs Intel X86 modernes utilisent des cœurs RISC à l'intérieur, autant que je sache (compilation à partir de X86 à la volée). Major optimization for RISC is pipeline optimization (and for Intel and other CPU as well), minimizing code jumps. One type of such optimization (probably a major one), is "cycle rollback" one. It's incredibly stupid, and efficient, even Intel compiler can do that AFAIK. It looks like:

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:

This way the optimization is that the pipeline is not broken for the worst case (if compareVal is absent in the array), so it is as fast as possible (of course not counting algorithm optimizations such as hash tables, sorted arrays and so on, mentioned in other answers, which may give better results depending on array size. Cycles Rollback approach can be applied there as well by the way. I'm writing here about that I think I didn't see in others)

The second part of this optimization is that that array item is taken by direct address (calculated at compiling stage, make sure you use a static array), and do not need additional ADD op to calculate pointer from array's base address. This optimization may not have significant effect, since AFAIK ARM architecture has special features to speed up arrays addressing. But anyway it's always better to know that you did all the best just in C code directly, right?

Cycle Rollback may look awkward due to waste of ROM (yep, you did right placing it to fast part of RAM, if your board supports this feature), but actually it's a fair pay for speed, being based on RISC concept. This is just a general point of calculation optimization - you sacrifice space for sake of speed, and vice versa, depending on your requirements.

If you think that rollback for array of 1024 elements is too large sacrifice for your case, you can consider 'partial rollback', for example dividing the array into 2 parts of 512 items each, or 4x256, and so on.

3) modern CPU often support SIMD ops, for example ARM NEON instruction set - it allows to execute the same ops in parallel. Frankly speaking I do not remember if it is suitable for comparison ops, but I feel it may be, you should check that. Googling shows that there may be some tricks as well, to get max speed, see https://.com/a/5734019/1028256

I hope it can give you some new ideas.




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!




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é.




I'm a great fan of hashing. The problem of course is to find an efficient algorithm that is both fast and uses a minimum amount of memory (especially on an embedded processor).

If you know beforehand the values that may occur you can create a program that runs through a multitude of algorithms to find the best one - or, rather, the best parameters for your data.

I created such a program that you can read about in this post and achieved some very fast results. 16000 entries translates roughly to 2^14 or an average of 14 comparisons to find the value using a binary search. I explicitly aimed for very fast lookups - on average finding the value in <=1.5 lookups - which resulted in greater RAM requirements. I believe that with a more conservative average value (say <=3) a lot of memory could be saved. By comparison the average case for a binary search on your 256 or 1024 entries would result in an average number of comparisons of 8 and 10, respectively.

My average lookup required around 60 cycles (on a laptop with an intel i5) with a generic algorithm (utilizing one division by a variable) and 40-45 cycles with a specialized (probably utilizing a multiplication). This should translate into sub-microsecond lookup times on your MCU, depending of course on the clock frequency it executes at.

It can be real-life-tweaked further if the entry array keeps track of how many times an entry was accessed. If the entry array is sorted from most to least accessed before the indeces are computed then it'll find the most commonly occuring values with a single comparison.




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




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.