Frage Der schnellste Weg, um festzustellen, ob eine ganze Zahl zwischen zwei ganzen Zahlen (einschließlich) mit bekannten Mengen von Werten liegt


Gibt es einen schnelleren Weg als? x >= start && x <= end in C oder C ++ zu testen, ob eine ganze Zahl zwischen zwei ganzen Zahlen ist?

AKTUALISIEREN: Meine spezifische Plattform ist iOS. Dies ist Teil einer Box-Unschärfe-Funktion, die Pixel auf einen Kreis in einem bestimmten Quadrat beschränkt.

AKTUALISIEREN: Nach dem Versuch, die akzeptierte Antwort, Ich habe eine Größenordnung der Beschleunigung auf der einen Zeile des Codes gegenüber dem normalen tun x >= start && x <= end Weg.

AKTUALISIEREN: Hier ist der after und before Code mit Assembler von XCode:

NEUER WEG

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

ALTER WEG

#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

Ziemlich erstaunlich, wie das Reduzieren oder Eliminieren von Verzweigungen solch eine dramatische Beschleunigung bereitstellen kann.


362
2018-06-13 19:34


Ursprung


Antworten:


Es gibt einen alten Trick, dies mit nur einem Vergleich / Zweig zu tun. Ob es die Geschwindigkeit wirklich verbessern wird, ist vielleicht fraglich, und selbst wenn dies der Fall ist, ist es wahrscheinlich zu wenig, um es zu bemerken oder zu beachten, aber wenn man nur mit zwei Vergleichen beginnt, sind die Chancen einer großen Verbesserung ziemlich gering. Der Code sieht folgendermaßen aus:

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

Bei einem typischen, modernen Computer (d. H. Alles, das Zweierkomplement verwendet), ist die Umwandlung zu vorzeichenlos wirklich ein NOP - nur eine Änderung in der Art, wie die gleichen Bits betrachtet werden.

Beachten Sie, dass Sie in einem typischen Fall vorberechnen können upper-lower außerhalb einer (vermuteten) Schleife, so dass normalerweise keine signifikante Zeit beiträgt. Zusammen mit dem Reduzieren der Anzahl von Verzweigungsbefehlen verbessert dies (allgemein) auch die Verzweigungsvorhersage. In diesem Fall wird die gleiche Verzweigung genommen, unabhängig davon, ob die Anzahl unter dem unteren Ende oder über dem oberen Ende des Bereichs liegt.

Was das angeht, ist die Grundidee ziemlich einfach: Eine negative Zahl wird, wenn sie als vorzeichenlose Zahl betrachtet wird, größer sein als alles, was als positive Zahl begann.

In der Praxis wird diese Methode übersetzt number und das Intervall bis zum Ausgangspunkt und prüft ob number ist in dem Intervall [0, D], woher D = upper - lower. Ob number unterhalb der unteren Grenze: Negativund wenn über der oberen Grenze: größer als D.


499
2018-06-13 19:32



Es hängt davon ab, wie oft Sie den Test über die gleichen Daten durchführen möchten.

Wenn Sie den Test ein einziges Mal durchführen, gibt es wahrscheinlich keine sinnvolle Möglichkeit, den Algorithmus zu beschleunigen.

Wenn Sie dies für eine sehr begrenzte Menge von Werten tun, können Sie eine Nachschlagetabelle erstellen. Die Indizierung ist möglicherweise teurer, aber wenn Sie die gesamte Tabelle in den Cache einpassen können, können Sie alle Verzweigungen aus dem Code entfernen, was die Dinge beschleunigen sollte.

Für Ihre Daten wäre die Nachschlagetabelle 128 ^ 3 = 2.097.152. Wenn Sie eine der drei Variablen steuern können, berücksichtigen Sie alle Instanzen start = N auf einmal fällt die Größe des Arbeitssatzes auf 128^2 = 16432 Bytes, die in den meisten modernen Caches gut passen sollten.

Sie müssten immer noch den tatsächlichen Code vergleichen, um zu sehen, ob eine branchless Lookup-Tabelle ausreichend schneller ist als die offensichtlichen Vergleiche.


17
2018-06-13 19:34



Es ist selten, dass wir in der Lage sind, signifikante Optimierungen vorzunehmen, um in einem so kleinen Maßstab zu codieren. Große Leistungssteigerungen ergeben sich aus der Beobachtung und Änderung des Codes von einer höheren Ebene. Sie können möglicherweise die Notwendigkeit für den Reichweitentest ganz eliminieren, oder nur O (n) von ihnen anstelle von O (n ^ 2). Sie können die Tests möglicherweise so umordnen, dass immer eine Seite der Ungleichung impliziert wird. Selbst wenn der Algorithmus ideal ist, werden Verstärkungen wahrscheinlicher, wenn Sie sehen, wie dieser Code den Bereich 10 Millionen Mal testet, und Sie finden eine Möglichkeit, sie stapelweise zu verwenden und SSE zu verwenden, um viele Tests parallel durchzuführen.


16
2018-06-14 03:36



Diese Antwort soll über einen Test berichten, der mit der angenommenen Antwort durchgeführt wurde. Ich habe einen Closed-Range-Test an einem großen Vektor der sortierten zufälligen Ganzzahl durchgeführt und zu meiner Überraschung ist die grundlegende Methode von (low <= num && num <= high) tatsächlich schneller als die oben angenommene Antwort! Getestet wurde mit dem HP Pavilion g6 (AMD A6-3400APU mit 6 GB RAM). Hier ist der Kerncode, der zum Testen verwendet wurde:

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;

verglichen mit dem folgenden, was die akzeptierte Antwort oben ist:

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

Achten Sie darauf, dass randVec ein sortierter Vektor ist. Für jede Größe von MaxNum schlägt die erste Methode die zweite auf meiner Maschine!


2



Ist es nicht möglich, eine bitweise Operation für die Ganzzahl auszuführen?

Da es zwischen 0 und 128 liegen muss, wenn das achte Bit gesetzt ist (2 ^ 7), ist es 128 oder mehr. Der Randfall wird jedoch ein Schmerz sein, da Sie einen umfassenden Vergleich wünschen.


-3