Propre, efficace algorithme pour l'emballage des entiers en C++

/**
  * Returns a number between kLowerBound and kUpperBound
  * e.g.: Wrap(-1, 0, 4); //Returns 4
  * e.g.: Wrap(5, 0, 4); //Returns 0      
  */
int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
    //Suggest an implementation?
}
  • Quelle est la fonction censé faire? Comment est-elle arrivée à 4 dans le premier et à 0 dans le second cas?
  • C'est un "wrap" la fonction. Tout nombre qui n'est pas entre les deux bornes, puis "emballages" de l'autre côté et commence à décrémenter/incrémentation de fonction sur le côté, c'est sur.
  • Programmation par troupeau. Ce qui marrant.
  • 🙂 Oui. J'ai un crufty solution dans mon code maintenant si je peux continuer à travailler, mais c'est le meilleur copain de vérification de je pense, pour les non-propriétaires de code. 🙂
  • Inspiration Possible dans le stackoverflow.com/questions/478721/...
  • Je suggère fortement à l'encontre de la mise en œuvre de l'emballage dans le logiciel. Beaucoup plus rapide solution serait à l'échelle de vos données à certains de gamme qui est facilement enroulé à l'aide natif point fixe de types de données ou à l'aide d'un masque de bits avec un point fixe de type de données.

InformationsquelleAutor |
  1. 30

    Le signe de a % b n'est définie que si a et b sont à la fois non-négatif.

    int Wrap(int kX, int const kLowerBound, int const kUpperBound)
{
    int range_size = kUpperBound - kLowerBound + 1;

    if (kX < kLowerBound)
        kX += range_size * ((kLowerBound - kX) / range_size + 1);

    return kLowerBound + (kX - kLowerBound) % range_size;
}
    • La première solution qui fonctionne pour les nombres négatifs, sans compter sur un comportement non spécifié ou en boucle.
    • Je l'espère... compte tenu de la façon faussement "simple" la question s'affiche, je ne serais pas surpris d'avoir fait une erreur. Il repose sur kUpperBound >= kLowerBound.
    • Pour le Wrap(-1, 1, 4)), il donne 3. Je pense qu'il devrait retourner 4.
    • Pour une gamme de 1 -> 4, sûrement 0 == 4 et -1 == 3?
    • Ok, vous avez raison. Ma réponse traiter kX, comme une sorte d'indice de faible et de haute tenue.
    • J'aime cette solution meilleur jusqu'à présent. Cela dit, vous pourrait techniquement faire un retour à partir de l'intérieur de la si, ne pourriez-vous pas? Vous êtes amener kX dans la zone à ce moment-là, de retour kX +, contre kX+=, suivi par un autre module, non?
    • Oui, c'est vrai. Et vous pouvez faire que la deuxième moitié d'une manière similaire, sans un module de trop.
    • point mineur: devez-vous changer la signature de la fonction à utiliser "int kX" pas "int const kX", puisque vous êtes évolution kX en interne?
    • Donc, disons que je veux 15 % 10. J'utilise Wrap(15, 0, 10) efficacement les rendements return 0 + (15 - 0) % (10-0+1) ou return 15 % 11, qui donne 4. Cependant, 15 % 10 est 5. Ce commentaire répète ce que des commentateurs a dit, mais ajoute une "dérivation". Je ne pense pas que votre Wrap suit le principe de moindre surprise est.

    InformationsquelleAutor
  2. 17

    Les éléments suivants doivent travailler de manière indépendante de la mise en œuvre de l'opérateur mod:

    int range = kUpperBound - kLowerBound + 1;
kx = ((kx-kLowerBound) % range);
if (kx<0)
  return kUpperBound + 1 + kx;
else
  return kLowerBound + kx;

    Un avantage sur les autres solutions, c'est qu'elle utilise un seul % (c'est à dire de la division), ce qui le rend assez efficace.

    Remarque (Hors Sujet):

    C'est un bon exemple, pourquoi il est parfois judicieux de définir des intervalles avec la limite supérieure étant d'être le premier élément de pas dans la gamme (comme la STL itérateurs...). Dans ce cas, les deux "+1" disparaîtrait.

    • Très agréable et excellent point sur l' +1s.
    InformationsquelleAutor
  3. 4

    Solution la plus rapide, la moins flexible: tirer parti des indigènes de types qui font de l'emballage dans le matériel.

    La absolue méthode la plus rapide pour l'emballage des entiers serait de faire en sorte de vos données est mise à l'échelle de int8/int16/int32 ou quel type de données natif. Puis, quand vous avez besoin de vos données pour envelopper le type de données natif sera fait en hardware! Très indolore et ordres de grandeur plus rapide que n'importe quel logiciel d'emballage de la mise en œuvre vu ici.

    Comme un exemple d'étude de cas:

    J'ai trouvé cela très utile quand j'ai besoin d'une mise en œuvre rapide de sin/cos mis en œuvre à l'aide d'une look-up-table pour un sin/cos mise en œuvre. Fondamentalement, vous faire évoluer vos données telles que INT16_MAX est pi et INT16_MIN est -pi. Alors vous êtes prêt à aller.

    Comme une note de côté, de mise à l'échelle de vos données d'ajouter un peu de place avant finis calcul des coûts qui ressemble généralement à ceci:

    int fixedPoint = (int)( floatingPoint * SCALING_FACTOR + 0.5 )

    N'hésitez pas à échanger int pour quelque chose d'autre que vous voulez comme int8_t /int16_t /int32_t.

    Prochaine solution la plus rapide, plus souple: Le mod opération est lent au lieu de cela, si possible, essayez d'utiliser des masques de bits!

    La plupart des solutions que j'ai écrémé sont fonctionnellement correct... mais ils sont dépendants du mod opération.

    Le mod opération est très lent, car il s'agit essentiellement de faire un matériel de la division. Les dilettantes explication de pourquoi mod et la division sont lent, c'est d'assimiler la division de fonctionnement de certains pseudo-code for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; } ( def de quotient et diviseur ). Comme vous pouvez le voir, le matériel division peut être rapide si c'est un faible nombre par rapport au diviseur... mais la division peut également être horriblement lent si il est beaucoup plus grand que le diviseur.

    Si vous pouvez mettre à l'échelle vos données à une puissance de deux, alors vous pouvez utiliser un masque de bits qui s'exécutent dans un cycle ( 99% de toutes les plates-formes ) et votre amélioration de la vitesse sera d'environ un ordre de grandeur ( au moins 2 ou 3 fois plus rapide ).

    Code C pour mettre en œuvre emballage:

    #define BIT_MASK (0xFFFF)
int wrappedAddition(int a, int b) {
    return ( a + b ) & BIT_MASK;
}
int wrappedSubtraction(int a, int b) {
    return ( a - b ) & BIT_MASK;
}

    N'hésitez pas à faire le #define quelque chose qui est de l'exécution. Et n'hésitez pas à ajuster le masque de bits pour être quelle que soit la puissance de deux que vous avez besoin. Comme 0xFFFFFFFF ou une puissance de deux, vous décidez sur la mise en œuvre.

    p.s. Je vous suggère fortement la lecture sur point fixe de traitement lorsque déconner avec l'emballage et les conditions de dépassement. Je suggère la lecture de:

    Point fixe de l'Arithmétique: Une Introduction par Randy Yates 23 août 2007

    InformationsquelleAutor
  4. 2

    S'il vous plaît ne pas négliger ce post. 🙂

    Est-ce bon?

    int Wrap(N,L,H){
  H=H-L+1; return (N-L+(N<L)*H)%H+L;
}

    Cela fonctionne pour les entrées, et tous les arguments peuvent être négatifs, tant que L est moins de H.

    De fond... (à Noter que H ici est la réutilisés variable, définie à l'origine H-L+1).

    J'avais été en utilisant (N-L)%H+L lors de l'incrémentation, mais, contrairement à Lua, que j'ai utilisé avant de commencer à apprendre le C il y a quelques mois, cela ne fonctionnera PAS si j'ai utilisé des intrants en dessous de la limite inférieure, jamais l'esprit négatif des entrées. (Lua est construit en C, mais je ne sais pas ce qu'il fait, et il n'y aurait probablement pas être rapide...)

    J'ai décidé d'ajouter +(N<L)*H de faire (N-L+(N<L)*H)%H+L, comme C semble être défini de telle manière que le vrai=1 et faux=0. Il fonctionne assez bien pour moi, et semble répondre à la question d'origine d'une manière ordonnée. Si quelqu'un sait comment le faire sans l'opérateur MOD % à le faire de manière aveuglante, rapide, veuillez le faire. Je n'ai pas besoin de vitesse pour l'instant, mais quelques temps, j'ai, sans aucun doute.

    EDIT:

    Que la fonction échoue si N est inférieur L par plus de H-L+1 mais ce n'est pas le cas:

    int Wrap(N,L,H){
  H-=L; return (N-L+(N<L)*((L-N)/H+1)*++H)%H+L;
}

    Je pense qu'il serait pause à l'négatives extrêmes de l'intervalle entier dans n'importe quel système, mais devrait fonctionner pour la plupart des situations pratiques. Cela ajoute une multiplication et une division, mais est encore assez compact.

    (Cette édition est juste la fin, parce que je suis venu avec une bien meilleure façon, dans un nouveau post dans ce fil.)

    Crow.

    InformationsquelleAutor
  5. 1

    En fait, depuis que -1 % 4 retourne -1 sur chaque système, j'ai même été sur la, le simple mod solution ne fonctionne pas. Je voudrais essayer:

    int range = kUpperBound  - kLowerBound +1;
kx = ((kx - kLowerBound) % range) + range;
return (kx % range) + kLowerBound;

    si kx est positif, vous mod, ajouter de la gamme, et le mod retour, annulation de l'ajouter. Si kx est négatif, vous mod, ajouter de la gamme, qui le rend positif, alors le mod de nouveau, ce qui ne veut pas faire n'importe quoi.

    • C'est mieux que mon "while":)
    • Les meilleurs à ce jour, je pense.
    • Essayez lb = 3, ac = 8, kx = 5. Clairement kx est dans la gamme devrait donc donne 5 mais... ligne 2: kx = (5 % 6) + 6 == 11, ensuite, à la ligne 3: (kx % 6) + 3 = 5 + 3 == 8 != 5.
    • Juste parce qu'il n'est que sur chaque système, vous le savez, ne signifie pas qu'il est juste.
    • devez lire kx=((kx-kLowerBound)%de la gamme)+range dans la deuxième ligne.
    InformationsquelleAutor Brian Postow
  6. 1

    Personnellement, j'ai trouvé des solutions à ces types de fonctions pour être plus propre si la gamme est exclusive et diviseur est limitée à des valeurs positives.

    int ifloordiv(int x, int y)
{
    if (x > 0)
        return x / y;
    if (x < 0)
        return (x + 1) / y - 1;
    return 0
}

int iwrap(int x, int y)
{   return x - y * ifloordiv(x, y);
}

    Intégré.

    int iwrap(int x, int y)
{
    if (x > 0)
        return x % y;
    if (x < 0)
        return (x + 1) % y + y - 1;
    return 0;
}

    Même famille. Pourquoi pas?

    int ireflect(int x, int y)
{
    int z = iwrap(x, y*2);
    if (z < y)
        return z;
    return y*2-1 - z;
}

int ibandy(int x, int y)
{
    if (y != 1)
        return ireflect(abs(x + x / (y - 1)), y);
    return 0;
}

    Allaient fonctionnalités peuvent être mises en œuvre pour toutes les fonctions,

    //output is in the range [min, max).
int func2(int x, int min, int max)
{
    //increment max for inclusive behavior.
    assert(min < max);
    return func(x - min, max - min) + min;
}
    InformationsquelleAutor
  7. 0

    Je voudrais suggérer cette solution:

    int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
    int d = kUpperBound - kLowerBound + 1;
    return kLowerBound + (kX >= 0 ? kX % d : -kX % d ? d - (-kX % d) : 0);
}

    La si-alors-sinon la logique de la ?: opérateur permet de s'assurer que les deux opérandes de % sont non négatifs.

    InformationsquelleAutor
  8. 0

    Je voudrais lui donner un point d'entrée pour le cas le plus courant limite inférieure=0, upperBound=N-1. Et d'appeler cette fonction dans le cas général. Aucun mod le calcul est effectué que lorsque je l'est déjà dans la gamme. Il suppose supérieur>=faible, ou n>0.

    int wrapN(int i,int n)
{
  if (i<0) return (n-1)-(-1-i)%n; //-1-i is >=0
  if (i>=n) return i%n;
  return i; //In range, no mod
}

int wrapLU(int i,int lower,int upper)
{
  return lower+wrapN(i-lower,1+upper-lower);
}
    InformationsquelleAutor
  9. 0

    Une réponse qui a une certaine symétrie et rend également évident que lorsque le kX est à portée, il est retourné non modifiée.

    int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
    int range_size = kUpperBound - kLowerBound + 1;

    if (kX < kLowerBound)
        return kX + range_size * ((kLowerBound - kX) / range_size + 1);

    if (kX > kUpperBound)
        return kX - range_size * ((kX - kUpperBound) / range_size + 1);

    return kX;
}
    InformationsquelleAutor
  10. 0

    J'ai été confronté à ce problème ainsi. C'est ma solution.

    template <> int mod(const int &x, const int &y) {
    return x % y;
}
template <class T> T mod(const T &x, const T &y) {
    return ::fmod((T)x, (T)y);
}
template <class T> T wrap(const T &x, const T &max, const T &min = 0) {
    if(max < min)
        return x;
    if(x > max)
        return min + mod(x - min, max - min + 1);
    if(x < min)
        return max - mod(min - x, max - min + 1);
    return x;
}

    Je ne sais pas si c'est bon, mais j'ai pensé que je pourrais partager avec vous depuis que j'ai réalisé ici lorsque vous faites une recherche Google sur ce problème et trouvé la solution ci-dessus ce qui manque à mes besoins. =)

    InformationsquelleAutor
  11. 0

    Mon autre post suis méchant, tout ce que "correctives" multiplication et la division sont sortis de la main. Après avoir regardé Martin Stettner post, et à mes conditions de départ de (N-L)%H+L, je suis venu avec cette:

    int Wrap(N,L,H){
  H=H-L+1; N=(N-L)%H+L; if(N<L)N+=H; return N;
}

    À l'extrême négatif à la fin de l'intervalle entier il se casse comme mon autre, mais il sera plus rapide, et il est beaucoup plus facile à lire, et évite les autres ignominies qui se faufile à elle.

    Crow.

    InformationsquelleAutor
  12. -1

    Pour le négatif, kX, vous pouvez ajouter:

    int temp = kUpperBound - kLowerBound + 1;
while (kX < 0) kX += temp;
return kX%temp + kLowerBound;
    • Fonctionne mais pas élégant. Essayez "{temp2 = -kX/temp; kX += temp2+1;}"
    • devrait être: "si (kX < 0) {...};"
    • Cela ne fonctionne pas avec un zéro à la limite inférieure. E. g. lb = 3, ac = 8, kX = 5. Clairement 5 est déjà dans la gamme, mais temp = 6 et 5 % 6 + 3 = 8 != 5.
    InformationsquelleAutor
  13. -2

    Pourquoi pas à l'aide de méthodes d'Extension.

    public static class IntExtensions
{
    public static int Wrap(this int kX, int kLowerBound, int kUpperBound)
    {
        int range_size = kUpperBound - kLowerBound + 1;

        if (kX < kLowerBound)
            kX += range_size * ((kLowerBound - kX) / range_size + 1);

        return kLowerBound + (kX - kLowerBound) % range_size;
    }
}

    Utilisation: currentInt = (++currentInt).Wrap(0, 2);

    • Parce que la question est sur le C++, pas du C#?
    InformationsquelleAutor