Moyen le plus rapide de déterminer si un entier est compris entre deux entiers (inclus) avec des ensembles de valeurs connus

Existe-t-il un moyen plus rapide que x >= start && x <= end en C ou C ++ pour tester si un entier est compris entre deux nombres entiers?

MISE À JOUR : Ma plate-forme 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 accéléré sur la première ligne de code en le faisant de la manière normale x >= start && x <= end way.

UPDATE : Voici le code avant et après 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 

OLD WAY

 #define POINT_IN_RANGE_AND_INCREMENT(p, range) (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 étonnant de voir comment la réduction ou l’élimination des twigments peut apporter une telle rapidité.

Il y a un vieux truc pour faire cela avec une seule comparaison / twig. On peut se demander si cela va vraiment améliorer la vitesse, et même si c’est le cas, il est probablement trop difficile de le remarquer ou de s’en soucier, mais si vous ne commencez que par deux comparaisons, les chances d’une énorme amélioration sont minimes. 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 classique et moderne (c’est-à-dire tout ce qui peut utiliser deux compléments), la conversion en non signé est vraiment un échec - un simple changement dans la manière dont les mêmes bits sont visualisés.

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

En ce qui concerne son fonctionnement, l'idée de base est assez simple: un nombre négatif, 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 le number et l'intervalle au point d'origine et vérifie si le number est number dans l'intervalle [0, D] , où D = upper - lower . Si number inférieur à la borne inférieure: négatif et si supérieur à la limite supérieure: supérieur à D

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 pour accélérer l’algorithme.

Si vous le faites pour un ensemble de valeurs très fini, vous pouvez créer une table de consultation. L’exécution de l’indexation peut être plus coûteuse, mais si vous pouvez placer la table entière en cache, vous pouvez supprimer toutes les twigs 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 à la fois, la taille de l’ensemble de travail tombe à 128^2 = 16432 octets, ce qui convient parfaitement à la plupart des caches modernes.

Vous devrez toujours évaluer le code réel pour voir si une table de consultation sans agence est suffisamment plus rapide que les comparaisons évidentes.

Il est rare de pouvoir faire des optimisations significatives pour coder à une si petite échelle. Les gains de performance importants proviennent de l’observation et de la modification du code à partir d’un niveau supérieur. Vous pouvez peut-être éliminer complètement le besoin du test de distance, ou ne pas 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 implicite. Même si l’algorithme est idéal, les gains sont plus probables lorsque vous voyez comment ce code teste la scope 10 millions de fois et vous trouvez un moyen de les regrouper et d’utiliser SSE pour faire de nombreux tests en parallèle.

Cette réponse consiste à signaler un test effectué avec la réponse acceptée. J’ai effectué un test d’intervalle fermé sur un grand vecteur d’entier aléatoire sortingé et à ma grande surprise, la méthode de base de (bas <= num && num <= haut) 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 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 elapsed_s1 = end - start; 

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

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

Attention, randVec est un vecteur sortingé. Pour toute taille de MaxNum, la première méthode bat la seconde sur ma machine!

N’est-il pas possible d’effectuer une opération au niveau du nombre entier?

Comme il doit être compris entre 0 et 128, si le 8ème bit est défini (2 ^ 7), il est égal ou supérieur à 128. Le cas d’arête sera pénible, car vous voulez une comparaison inclusive.