it-swarm-eu.dev

Am schnellsten können Sie feststellen, ob eine Ganzzahl zwischen zwei Ganzzahlen (einschließlich) mit bekannten Wertesätzen liegt

Gibt es einen schnelleren Weg als x >= start && x <= end in C oder C++, um zu testen, ob eine Ganzzahl zwischen zwei Ganzzahlen liegt?

[~ # ~] update [~ # ~]: Meine spezielle Plattform ist iOS. Dies ist Teil einer Box-Blur-Funktion, mit der Pixel auf einen Kreis in einem bestimmten Quadrat beschränkt werden.

[~ # ~] update [~ # ~]: Nachdem ich die akzeptierte Antwort ausprobiert habe, habe ich eine Größenordnungsbeschleunigung in einer Codezeile erhalten, als ich das getan habe das Normale x >= start && x <= end Weg.

[~ # ~] update [~ # ~]: 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 zu einer derart dramatischen Beschleunigung führen kann.

374
jjxtra

Es gibt einen alten Trick, dies mit nur einem Vergleich/Zweig zu tun. Ob sich die Geschwindigkeit wirklich verbessert, kann in Frage gestellt werden, und selbst wenn dies der Fall ist, ist es wahrscheinlich zu wenig, um es zu bemerken oder sich darum zu kümmern, aber wenn Sie erst mit zwei Vergleichen beginnen, sind die Chancen für eine enorme Verbesserung ziemlich gering. Der Code sieht so 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 Konvertierung in vorzeichenlos wirklich ein Kinderspiel - nur eine Änderung in der Art und Weise, wie dieselben Bits betrachtet werden.

Beachten Sie, dass Sie in einem typischen Fall upper-lower Außerhalb einer (angenommenen) Schleife vorberechnen können, so dass normalerweise keine signifikante Zeit anfällt. Zusammen mit der Verringerung der Anzahl von Verzweigungsbefehlen verbessert dies (allgemein) auch die Verzweigungsvorhersage. In diesem Fall wird derselbe Zweig genommen, unabhängig davon, ob die Zahl unter dem unteren Ende oder über dem oberen Ende des Bereichs liegt.

In Bezug auf die Funktionsweise ist die Grundidee ziemlich einfach: Eine negative Zahl ist, wenn sie als vorzeichenlose Zahl betrachtet wird, größer als alles, was als positive Zahl begann.

In der Praxis übersetzt diese Methode number und das Intervall zum Ursprungspunkt und prüft, ob number im Intervall [0, D] Liegt, wobei D = upper - lower. Wenn number unter der Untergrenze: negativ, und wenn über der Obergrenze: größer als D.

513
Jerry Coffin

Es ist selten in der Lage, signifikante Optimierungen vorzunehmen, um Code in einem so kleinen Maßstab zu erstellen. Ein großer Leistungsgewinn ergibt sich aus der Beobachtung und Änderung des Codes von einer höheren Ebene. Möglicherweise können Sie den Reichweitentest ganz überflüssig machen oder nur O(n) anstelle von O (n ^ 2). Möglicherweise können Sie die nachbestellen testet so, dass immer eine Seite der Ungleichung impliziert wird.Auch wenn der Algorithmus ideal ist, sind Gewinne wahrscheinlicher, wenn Sie sehen, wie dieser Code den Reichweitentest 10 Millionen Mal durchführt und Sie einen Weg finden, sie zu stapeln und = zu verwenden SSE um viele Tests parallel durchzuführen.

18
Ben Jackson

Dies hängt davon ab, wie oft Sie den Test mit denselben 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. Das Durchführen der Indizierung ist möglicherweise teurer. Wenn Sie jedoch 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 Fälle, in denen start = N zu einem Zeitpunkt, dann fällt die Größe des Arbeitssets auf 128^2 = 16432 Bytes, die in die meisten modernen Caches passen sollten.

Sie müssten immer noch den tatsächlichen Code vergleichen, um festzustellen, ob eine verzweigungslose Nachschlagetabelle ausreichend schneller ist als die offensichtlichen Vergleiche.

17
Andrew Prock

Diese Antwort soll über einen Test berichten, der mit der akzeptierten Antwort durchgeführt wurde. Ich habe einen Nahbereichstest mit einem großen Vektor einer sortierten Zufallszahl durchgeführt, und zu meiner Überraschung ist die grundlegende Methode von (low <= num && num <= high) tatsächlich schneller als die oben akzeptierte Antwort! Der Test wurde mit dem HP Pavilion g6 (AMD A6-3400APU mit 6 GB RAM) durchgeführt. 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, welches 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;
}

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

2
rezeli