Méthode la plus rapide pour déterminer si un entier se situe entre deux entiers (inclus) avec des ensembles de valeurs connus

Existe-t-il un moyen plus rapide qu'en x >= start && x <= endC ou C ++ pour tester si un entier est entre deux entiers?

MISE À JOUR : Ma plateforme spécifique est iOS. Cela fait partie d'une fonction de flou de boîte qui restreint les pixels à un cercle dans un carré donné.

MISE À JOUR : Après avoir essayé la réponse acceptée , j'ai obtenu un ordre de grandeur d'accélération sur la seule ligne de code en le faisant normalement x >= start && x <= end.

MISE À JOUR : Voici le code après et avant avec l'assembleur de XCode:

NOUVELLE FAÇON

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

ANCIENNE VOIE

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

Assez incroyable de voir comment la réduction ou l'élimination des branchements peut fournir une accélération aussi spectaculaire.

Il y a une vieille astuce pour le faire avec une seule comparaison / branche. Que cela améliore vraiment la vitesse peut être contesté, et même si c'est le cas, c'est probablement trop peu pour le remarquer ou s'en soucier, mais lorsque vous commencez seulement avec deux comparaisons, les chances d'une énorme amélioration sont assez lointaines. Le code ressemble à:

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

Avec un ordinateur typique et moderne (c'est-à-dire tout ce qui utilise un complément à deux), la conversion en non signé est vraiment un nop - juste un changement dans la façon dont les mêmes bits sont affichés.

Notez que dans un cas typique, vous pouvez pré-calculer en upper-lowerdehors d'une boucle (présumée), de sorte que cela ne contribue normalement pas à un temps significatif. En plus de réduire le nombre d'instructions de branchement, cela améliore (généralement) la prédiction de branchement. Dans ce cas, la même branche est prise, que le nombre soit inférieur à l'extrémité inférieure ou supérieur à l'extrémité supérieure de la plage.

Quant à la façon dont cela fonctionne, l'idée de base est assez simple: un nombre négatif, lorsqu'il est considéré comme un nombre non signé, sera plus grand que tout ce qui a commencé comme un nombre positif.

En pratique, cette méthode traduit numberet l'intervalle au point d'origine et vérifie si numberest dans l'intervalle [0, D], où D = upper - lower. Si en numberdessous de la borne inférieure: négatif et si au-dessus de la borne supérieure: supérieur àD .

Il est rare de pouvoir effectuer des optimisations importantes pour coder à une si petite échelle. Les gains de performances importants proviennent de l'observation et de la modification du code à partir d'un niveau supérieur. Vous pourrez peut-être éliminer complètement la nécessité du test de portée, ou n'en faire que O (n) au lieu de O (n ^ 2). Vous pourrez peut-être réorganiser les tests de sorte qu'un côté de l'inégalité soit toujours impliqué. Même si l'algorithme est idéal, les gains sont plus susceptibles de se produire lorsque vous voyez comment ce code effectue le test de plage 10 millions de fois et que vous trouvez un moyen de les regrouper et d'utiliser SSE pour effectuer de nombreux tests en parallèle.

Cela dépend du nombre de fois que vous souhaitez effectuer le test sur les mêmes données.

Si vous effectuez le test une seule fois, il n'y a probablement pas de moyen significatif d'accélérer l'algorithme.

Si vous faites cela pour un ensemble très limité de valeurs, vous pouvez créer une table de recherche. L'exécution de l'indexation peut être plus coûteuse, mais si vous pouvez tenir la table entière dans le cache, vous pouvez supprimer toutes les branches du code, ce qui devrait accélérer les choses.

Pour vos données, la table de recherche serait 128 ^ 3 = 2 097 152. Si vous pouvez contrôler l'une des trois variables afin de prendre en compte toutes les instances où start = Nà un moment donné, la taille de l'ensemble de travail descend en 128^2 = 16432octets, ce qui devrait convenir à la plupart des caches modernes.

Vous devrez toujours comparer le code réel pour voir si une table de recherche sans branche est suffisamment rapide que les comparaisons évidentes.

Cette réponse consiste à rendre compte d'un test effectué avec la réponse acceptée. J'ai effectué un test de plage fermée sur un grand vecteur d'entier aléatoire trié et à ma grande surprise, la méthode de base de (faible <= num && num <= élevé) est en fait plus rapide que la réponse acceptée ci-dessus! Le test a été effectué sur HP Pavilion g6 (AMD A6-3400APU avec 6 Go de RAM. Voici le code de base utilisé pour les tests:

int num = rand();  // num to compare in consecutive ranges.
chrono::time_point<chrono::system_clock> start, end;
auto start = chrono::system_clock::now();

int inBetween1{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (randVec[i - 1] <= num && num <= randVec[i])
        ++inBetween1;
}
auto end = chrono::system_clock::now();
chrono::duration<double> elapsed_s1 = end - start;

par rapport à ce qui est la réponse acceptée ci-dessus:

int inBetween2{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (static_cast<unsigned>(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1]))
        ++inBetween2;
}

Faites attention que randVec est un vecteur trié. Pour n'importe quelle taille de MaxNum, la première méthode bat la seconde sur ma machine!

Pour toute vérification de plage variable:

if (x >= minx && x <= maxx) ...

Il est plus rapide d'utiliser le fonctionnement en bits:

if ( ((x - minx) | (maxx - x)) >= 0) ...

Cela réduira deux branches en une seule.

Si vous vous souciez du type sûr:

if ((int32_t)(((uint32_t)x - (uint32_t)minx) | ((uint32_t)maxx - (uint32_t)x)) > = 0) ...

Vous pouvez combiner plusieurs contrôles de plage de variables ensemble:

if (( (x - minx) | (maxx - x) | (y - miny) | (maxy - y) ) >= 0) ...

Cela réduira 4 branches en 1.

Il est 3,4 fois plus rapide que l'ancien en gcc:

N'est-il pas possible d'effectuer simplement une opération au niveau du bit sur l'entier?

Comme il doit être compris entre 0 et 128, si le 8ème bit est défini (2 ^ 7), il est de 128 ou plus. Le cas de bord sera cependant pénible, car vous voulez une comparaison inclusive.