Was ist die effizienteste Methode, x zusammenhängende Werte von y in einem Array zu finden?

Question

Wenn ich meine App über Callgrind laufen ließ, stellte sich heraus, dass diese Zeile alles andere um den Faktor 10.000 übertraf. Ich werde es wahrscheinlich neu gestalten, aber es hat mich neugierig gemacht; Gibt es einen besseren Weg, es zu tun?

Hier ist, was ich im Moment tun:

int i = 1; 
while 
(
    (
     (*(buffer++) == 0xffffffff && ++i) || 
     (i = 1) 
    ) 
    && 
    i < desiredLength + 1 
    && 
    buffer < bufferEnd 
); 

Es ist für den Offset des ersten Batzen desiredLength 0xffffffff Werte in einem 32-Bit unsigned int Array suchen.

Es ist deutlich schneller als alle Implementierungen, die ich mit einer inneren Schleife kommen könnte. Aber es ist immer noch zu verdammt langsam.

Answer 1

Sie getaggt C++, damit ich nehme an, Sie STL-Algorithmen zur Verfügung haben:

std::search_n(buffer, bufferEnd, desiredLength, 0xffffffff); 

Answer 2

Versuchen Sie memcmp von C-Standardbibliothek zu verwenden. Moderne Compiler sollten sehr optimierte Implementierungen von memxxx Funktionen haben, die die meisten modernen CPUs beschleunigen.

Answer 3

Wenn ich das umsetzen will ich es memchr und memcmp mit tun:

bool found = false; 
std::vector<unsigned char> tmp(desiredLength*sizeof(uint32_t), 0xFF); 
while(true) { 
    void* p = memchr(bufferStart, 0xFF, 
     (bufferEnd-bufferStart-desiredLength) * sizeof(uint32_t)); 
    if(!p) break; 
    if(!memcmp(p, &tmp[0], desiredLength * sizeof(uint32_t))) { 
     found = true; 
     break; 
    } 
} 

Sie können auch std::search_n verwenden das kann besser als Ihr eigener Code optimiert werden

Answer 4

Nur ein Gedanke, aber Sie sind über das int-Array i ne auf einmal richtig? Denken Sie darüber nach, wenn Sie *(buffer) != 0xffffffff und buffer[desiredLength-1] != 0xffffffff dann können Sie sicher sein, dass es keinen Sinn zwischendurch zu überprüfen, so können Sie einfach buffer auf desiredLength anstatt nur durch 1, die Ihre Geschwindigkeit deutlich verbessern können, wenn desiredLength ist viel größer als eins. Natürlich erschwert es Ihre Funktion, weil:

1. Wenn beide *(buffer) und buffer[desiredLength-1] gleich 0xffffffff dann können Sie nicht, dass es zwischen ihnen zusammenhängenden annehmen, so werden Sie immer noch, dass überprüfen müssen.
2. Wenn *(buffer) nicht gleich 0xffffffff aber buffer[desiredLength-1] tut gleich 0xffffffff dann musst du an den Anfang der 0xffffffff Sequenz verfolgen.
3. Sie haben Sie den Pufferüberlauf nicht zu gewährleisten, wenn Sie überprüfen buffer[desiredLength-1]

etwas komplexer, aber es kann Dinge zu beschleunigen. Hoffnung, die Sinn macht.

Answer 5

Ich würde auch für den search_n Vorschlag gehen, weil ich ziemlich sicher bin, dass es das richtig macht. Es ist eigentlich ziemlich einfach und kann im Prinzip um einen Faktor von sented_length beschleunigt werden. es sei denn, die Zielwerte sind im Array wirklich dicht.

Hier ist die Idee: Wenn Sie K aufeinander folgenden Instanzen eines Wert haben, beginnend an Position I, dann muss es der Fall sein, dass Position I + K - 1 diesen Wert enthält. Also überprüfst du das zuerst; Wenn dies nicht der Fall ist, ist die früheste Position, die die K aufeinanderfolgenden Werte enthalten könnte, I + K, so dass Sie den Algorithmus dort neu starten können.

Wenn auf der anderen Seite der Wert bei I + K - 1 finden, dann scannen Sie zurück, bis Sie entweder I erreichen (in diesem Fall, dass Sie es gelungen), oder Sie erreichen eine Position J - 1, die nicht den Zielwert enthält. In letzterem Fall wissen Sie, dass Zielwerte von J bis I + K - 1 vorhanden sind. Überprüfen Sie jetzt J + K - 1. Wenn das funktioniert, müssen Sie nur rückwärts nach I + K scannen. Wenn es nicht funktioniert, starten Sie den Algorithmus unter J + K neu.

Die meiste Zeit werden Sie nur jede K'th Position im Vektor betrachten. Für große K, das ist ein großer Gewinn.

Answer 6

Denn wenn std::search_n ist nicht verfügbar:

int i = 1; 
while 
(
    (
     i == 1 
     && 
     buffer < bufferEnd 
     && 
     (
      (
       *buffer == desired 
       && 
       *(buffer + desiredLength - 1) == desired 
       && 
       (i = 3) 
      ) 
      || 
      (buffer += desiredLength && (i = 1)) 
     ) 
    ) 
    || 
    (
     i == 2 
     && 
     (
      (
       buffer > arr 
       && 
       (*(--buffer) == desired) 
      ) 
      || 
      (i = 3) 
     ) 
    ) 
    || 
    (
     i >= 3 
     && 
     buffer < bufferEnd 
     && 
     (
      (
       *(buffer++) == desired 
       && 
       (i++ || true) 
      ) 
      || 
      (i = 1) 
     ) 
     && 
     (
      i < 3 
      || 
      i - 3 < desiredLength + 1 
     ) 
    ) 
); 
buffer -= i - 4; 

if (buffer > bufferEnd - (i-3)) 
    buffer = bufferEnd; 

Returns identische Ergebnisse nur geringfügig langsamer als std:search_n:

buffer = std::search_n(buffer, bufferEnd-1, desiredLength, desired); 
if (buffer == bufferEnd-1) 
    buffer = bufferEnd;