Sauberer, effizienter Algorithmus zum Umschließen von Ganzzahlen in 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?
}
Kommentar zu dem Problem
Was die Funktion tun soll? Wie wird es ankommen, bei 4 in der ersten und 0 im zweiten Fall? Kommentarautor: Mark Probst
Es ist ein "wrap" - Funktion. Jede Zahl, die nicht zwischen den beiden Grenzen, dann 'umschließt' auf die andere Seite und beginnt zu Dekrementieren/Inkrementieren, je nach der Seite auf. Kommentarautor: Eddie Parker
Programmierung durch Herde. Was für ein Brüller. Kommentarautor: dmckee
🙂 Yeah. Ich habe eine crufty Lösung in meinem codebase jetzt, damit ich weiter arbeiten können, aber dies ist die beste buddy-Prüfung ich denke, der kann für nicht-proprietären code. 🙂 Kommentarautor: Eddie Parker
Möglich inspiration auf stackoverflow.com/questions/478721/... Kommentarautor: Blorgbeard

InformationsquelleAutor der Frage |

  1. 28

    Zeichen der a % b ist nur definiert, wenn die a und b sind beide nicht-negativ.

    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;
}

    InformationsquelleAutor der Antwort

  2. 15

    Folgende arbeiten sollten, unabhängig von der Umsetzung der mod-operator:

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

    Einen Vorteil gegenüber anderen Lösungen ist, dass es verwendet nur einen einzigen % (d.h. Teilung), wodurch es ziemlich effizient.

    Hinweis (Off-Topic):

    Es ist ein gutes Beispiel, warum es manchmal klug ist, zu definieren Abständen mit der oberen Schranke wird das erste element nicht in dem Bereich (wie für STL-Iteratoren...). In diesem Fall werden sowohl "+1" würde verschwinden.

    InformationsquelleAutor der Antwort

  3. 3

    Schnellste Lösung, die am wenigsten flexibel: nutzen Sie native Datentypen, die die Umhüllung in der hardware.

    Den absolut Schnellste Methode zum Verpacken von ganzen zahlen wäre, um sicherzustellen, dass Ihre Daten so skaliert, int8/int16/int32 oder was auch immer nativen Datentyp. Dann, wenn Sie Ihre Daten zum wickeln des nativen Datentyps erfolgt in der hardware! Sehr schmerzlos und Größenordnungen schneller als jede software-wrapping Umsetzung sind hier zu sehen.

    Als Beispiel Fallstudie:

    Ich habe festgestellt, dass dies sehr nützlich sein, wenn ich brauche eine schnelle Umsetzung von sin/cos, wurde mit Hilfe einer look-up-Tabelle für einen sin - /cos-Implementierung. Im Grunde machen Sie skalieren Sie Ihre Daten so, dass INT16_MAX ist pi und INT16_MIN ist -pi. Dann haben Sie eingestellt, um zu gehen.

    Als eine Randnotiz, skalieren Sie Ihre Daten, fügen Sie einige vorne endliche Berechnung der Kosten, die in der Regel in etwa so aussieht:

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

    Fühlen Sie sich frei, um exchange-int für etwas, was Sie wollen, wie int8_t /int16_t /int32_t.

    Nächste Schnellste Lösung, mehr Flexibilität: Die mod-operation ist langsam statt, wenn möglich versuchen, verwenden Sie bit-Masken!

    Meisten Lösungen, die ich Magermilch sind funktional korrekt ist... aber Sie sind abhängig von der mod-operation.

    Die mod-operation ist sehr langsam, da es im wesentlichen ist dabei eine hardware-division. Die Amateur-Erklärung, warum der mod und division langsam ist gleichzusetzen, die division zu einigen pseudo-code for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; } ( def quotient und divisor ). Wie Sie sehen können, die hardware Abteilung schnell sein kann, wenn es einen niedrigen Wert relativ zu der divisor... aber die Teilung kann auch schrecklich langsam, wenn es viel größer ist als der divisor.

    Wenn Sie skalieren Sie Ihre Daten auf eine Potenz von zwei, dann können Sie eine bit-Maske, die ausgeführt wird in einem Zyklus ( auf 99% aller Plattformen ) und Ihre Geschwindigkeit verbessert wird ungefähr eine Größenordnung ( mindestens 2 oder 3 mal schneller ).

    C-code zu implementieren Verpackung:

    #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;
}

    Fühlen Sie sich frei, um die #define-etwas Laufzeit. Und fühlen Sie sich frei, einstellen der bit-Maske die macht der zwei, die Sie brauchen. Wie 0xFFFFFFFF oder macht der zwei, die Sie entscheiden über die Umsetzung.

    p.s. Ich empfehle dringend die Lektüre über Feste Punkt-Verarbeitung, wenn messing mit der Verpackung/überlauf Bedingungen. Ich schlage vor zu Lesen:

    Fixed-Point-Arithmetik: Eine Einführung von Randy Yates August 23, 2007

    InformationsquelleAutor der Antwort

  4. 2

    Bitte übersehen Sie nicht diese post. 🙂

    Ist das gut?

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

    Dies funktioniert für negative Eingänge, und alle Argumente, die kann auch negativ sein, so lange L kleiner als H.

    Hintergrund... (Beachten Sie, dass H hier ist die variable wiederverwendet, auf original eingestellt H-L+1).

    Hatte ich mich schon mit (N-L)%H+L beim Inkrementieren, aber im Gegensatz zu Lua, die ich verwendet habe, bevor Sie angefangen C zu lernen ein paar Monaten wieder, würde es NICHT funktionieren wenn ich die Eingänge unterhalb der unteren Grenze, geschweige denn negative Eingänge. (Lua aufgebaut ist in C, aber ich weiß nicht, was er tut, und es wahrscheinlich würde nicht schnell sein...)

    Beschloss ich, fügen Sie +(N<L)*H zu machen (N-L+(N<L)*H)%H+L als C zu sein scheint, so festgelegt, dass true=1 und false=0. Es funktioniert gut genug für mich, und scheint eine Antwort auf die ursprüngliche Frage ordentlich. Wenn jemand weiß, wie man es ohne die MOD-operator %, um es blendend schnell, tun Sie es bitte. Ich brauche nicht die Geschwindigkeit sofort, aber einige Zeit werde ich, kein Zweifel.

    EDIT:

    Diese Funktion schlägt fehl, wenn N ist niedriger als L von mehr als H-L+1 aber nicht:

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

    Ich denke, es würde brechen auf der negativen extreme der integer-Bereich in einem system, sollte aber für die meisten praktischen Situationen. Es fügt eine zusätzliche Multiplikation und division, aber immer noch ziemlich kompakt.

    (Das Bearbeiten ist nur für den Abschluss, da kam ich auf eine viel bessere Art und Weise, in der ein neuer Beitrag in diesem thread.)

    Crow.

    InformationsquelleAutor der Antwort

  5. 1

    Eigentlich, da -1 % 4 Wert -1 zurückgegeben wird, auf jedem system habe ich sogar auf die einfache mod-Lösung nicht funktioniert. Ich würde versuchen:

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

    wenn kx ist positiv, du mod, add range, und mod zurück, zum Verhängnis hinzufügen. Wenn kx negativ ist, mod, add range das es positiv ist, dann mod wieder, die nicht tun.

    InformationsquelleAutor der Antwort Brian Postow

  6. 1

    Persönlich habe ich eine Lösung gefunden, um diese Arten von Funktionen-Reiniger, wenn Angebot ist exklusiv und divisor ist beschränkt auf positive Werte.

    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);
}

    Integriert.

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

    Gleichen Familie. Warum nicht?

    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;
}

    Reichten Funktionalität implementiert werden kann, für alle Funktionen mit,

    //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 der Antwort

  7. 0

    Ich würde vorschlagen, diese Lösung:

    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);
}

    If-then-else Logik der ?: Betreiber stellt sicher, dass beide Operanden von % sind nicht negative.

    InformationsquelleAutor der Antwort

  8. 0

    Ich würde ein Einstieg zu den häufigsten Fall lowerBound=0, upperBound=N-1. Und rufen Sie diese Funktion in den Allgemeinen Fall. Keine mod-Berechnung wird durchgeführt, wo ich bereits in Reichweite. Es wird davon ausgegangen oberen>=niedriger, oder 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 der Antwort

  9. 0

    Antwort, dass hat einige Symmetrie und macht es auch offensichtlich, dass, wenn kX in Reichweite ist, wird es wieder unverändert.

    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 der Antwort

  10. 0

    Habe ich angesichts dieses problem auch. Dies ist meine Lösung.

    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;
}

    Ich weiß nicht, ob es gut ist, aber ich dachte ich würde teilen seit ich hierher geleitet, wenn Sie eine Google-Suche auf dieses problem und den hier beschriebenen Lösungen fehlt für meine Bedürfnisse. =)

    InformationsquelleAutor der Antwort

  11. 0

    Meinem anderen post bekam böse, alle, die 'korrigierende' Multiplikation und division aus der hand. Nach einem Blick auf Martin Stettner post, in meinem eigenen Ausgangsbedingungen (N-L)%H+L ich kam mit dieser:

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

    Am äußersten negativen Ende der integer-Bereich, die Sie bricht, wie meine anderen würde man, aber es geht schneller und ist viel leichter zu Lesen und vermeidet die anderen Gemeinheiten, die sich eingeschlichen.

    Crow.

    InformationsquelleAutor der Antwort

  12. -1

    Negativ-kX, die Sie hinzufügen können:

    int temp = kUpperBound - kLowerBound + 1;
while (kX < 0) kX += temp;
return kX%temp + kLowerBound;

    InformationsquelleAutor der Antwort

  13. -1

    Warum nicht mit Extension-Methoden.

    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;
    }
}

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

    InformationsquelleAutor der Antwort

Schreibe einen Kommentar