Wie schnell können Sie lineare Suche?

So weit Sie erhielt mehrere Ratschläge, die meisten, die behaupten, dass die lineare Suche keinen Sinn macht, auf sortierten Daten, wenn binäre Suche wesentlich effizienter arbeiten statt. Dies geschieht oft zu einer der beliebtesten "richtig klingt" Aussagen von Leuten, die keine Pflege zu geben, das problem zu viel zu denken. In der Realität, wenn man bedenkt, das größere Bild, gegeben der richtigen Umstände, lineare Suche kann sehr viel effizienter als die binäre Suche.

Beachten Sie, dass, wenn wir betrachten ein single Suchanfrage für ein sortiertes array binäre Suche ist deutlich effizientere Methode als die lineare Suche. Es gibt keinen Streit darüber. Auch, wenn Sie führen Sie mehrere komplett random Abfragen der gleichen Daten binären Suche noch gewinnt gegenüber der linearen Suche.

Jedoch beginnt das Bild zu ändern, wenn wir betrachten die sequentielle Suche Abfragen und diese Abfragen sind nicht ganz zufällig. Vorstellen, dass Anfragen eintreffen, in der Reihenfolge sortiert, d.h. der jeweils nächste Abfrage ist für einen höheren Wert als die Vorherige Abfrage. I. e. die Abfragen sind auch sortiert. BTW, Sie haben nicht Global und streng sortiert, von Zeit zu Zeit der Abfrage-Sequenz könnte "zurücksetzen", d.h. einen niedrigen Wert abgefragt wird, aber im Durchschnitt ist die konsequente Abfragen sollte dann in aufsteigender Reihenfolge. In anderen Worten, die Abfragen kommen in Serie, jede Serie in aufsteigender Reihenfolge sortiert. In diesem Fall, wenn die Durchschnittliche Länge der Serie ist vergleichbar mit der Länge der Arrays, lineare Suche übertreffen binäre Suche durch eine riesige Marge. Jedoch, um die Vorteile dieser situation, müssen Sie implementieren Ihre Suche im inkrementelle Art und Weise. Es ist einfach: wenn die nächste Abfrage ist größer als die Vorherige, die Sie nicht brauchen, um die Suche zu starten von Anfang an der Reihe. Stattdessen können Sie die Suche von der Stelle, wo die Vorherige Suche gestoppt. Die meisten vereinfachten Umsetzung (nur um den Gedanken zu verdeutlichen) könnte wie folgt Aussehen

static int linear(const int *arr, int n, int key)
{
  static int previous_key = INT_MIN;
  static int previous_i = 0;

  i = key >= previous_key ? previous_i : 0;

  while (i < n) {
    if (arr[i] >= key)
      break;
    ++i;
  }

  previous_key = key;
  previous_i = i;

  return i;
}

(Disclaimer: die oben genannten Umsetzung ist furchtbar hässlich für die offensichtliche Grund, dass das array eintrifft, von außen als parameter, während die Vorherige Suche Zustand ist intern gespeichert. Natürlich, dies ist der falsche Weg, es zu tun in der Praxis. Aber noch einmal, die oben sollen verdeutlichen die Idee und nicht mehr).

Beachten, dass die Komplexität der Verarbeitung jeder Reihe bestellt-Abfragen mit dem obigen Ansatz ist immer O(N) unabhängig von der Länge der Serie. Mithilfe der binären Suche, die Komplexität wäre O(M * log N). So, aus offensichtlichen Gründen, wenn M ist in der Nähe N, d.h. Abfragen kommen in ausreichend langen Serie bestellt, die über die lineare Suche wird deutlich stärker als binäre Suche, während für kleine M die binäre Suche wird gewinnen.

Auch dann, wenn der geordnete Reihe von Abfragen sind nicht sehr lang, die oben genannten änderungen könnte es noch geben Sie eine spürbare Verbesserung auf der Suche nach Leistung, wenn man bedenkt, dass Sie haben lineare Suche.

P. S. Als zusätzliche information über die Struktur des Problems:

Wenn Sie brauchen, um die Suche in einem geordneten array der Länge N und Sie wissen im Voraus, dass die Abfragen kommen in geordnete Reihe von [Ungefähre, Durchschnittliche] Länge M, der optimale Algorithmus wird wie folgt Aussehen

1. Berechnen Sie die stride Wert S = [N/M]. Es könnte auch Sinn machen, um "snap" den Wert S auf die [nächste] Potenz von 2 ist. Denken Sie an Ihre sortierten array als eine Sequenz von Blöcken der Länge S - so genannte S-Blöcke.
2. Nach Empfang einer Abfrage, inkrementelle lineare Suche für den S-block, die möglicherweise enthält der abgefragte Wert, d.h. es ist eine gewöhnliche lineare Suche mit stride S (natürlich, denken Sie daran, start aus dem block, wo die Vorherige Suche Links aus).
3. Nach der Feststellung der S-block, führen Sie die binäre Suche in den S-block für den abgefragten Wert.

Oben ist die optimale inkrementelle Suche-Algorithmus möglich, in einem Sinn, der es erreicht die theoretische Grenze für die asymptotische Effizienz wiederholte Suche. Beachten Sie, dass wenn der Wert von M ist viel kleiner dann N der Algorithmus "automatisch" verschiebt sich in Richtung binäre Suche, während, wenn M nahe kommt N den Algorithmus "automatisch" begünstigt lineare suchen. Letzteres macht Sinn, da in solcher Umgebung die lineare Suche ist wesentlich effizienter als die binäre Suche.

All dies ist nur zur Veranschaulichung der Tatsache, dass die Decke Aussagen wie "lineare Suche auf einem sortierten array ist immer sinnlos" zeigen, nichts anderes als Mangel an wissen auf Seiten derer, die solche Aussagen machen.

Zunächst keine schnelle Lösung verwenden müssen, Vektorisierung zu vergleichen, die viele Elemente auf einmal.

Jedoch alle die vektorisierte Implementierungen geschrieben, so weit leiden unter einem gemeinsamen problem: Sie haben Niederlassungen. Als Ergebnis, werden Sie haben, um einzuführen blockwise Verarbeitung von array (overhead reduziert der Verzweigung), die führt zu low-performance für kleine arrays. Für große arrays-linear-Suche ist schlimmer, als eine gut optimierte binäre Suche, so gibt es keinen Punkt in der Optimierung von it.

Jedoch lineare Suche realisiert werden können, ohne Zweige. Die Idee ist sehr einfach: der index, den Sie wollen, ist genau die Anzahl der array-Elemente, die kleiner sind als der Schlüssel, den Sie suchen. Damit Sie vergleichen können jedes element des Arrays mit dem key-Wert und die Summe aller flags:

static int linear_stgatilov_scalar (const int *arr, int n, int key) {
    int cnt = 0;
    for (int i = 0; i < n; i++)
        cnt += (arr[i] < key);
    return cnt;
}

Einen Spaß an dieser Lösung ist, dass würde es wieder die gleiche Antwort, auch wenn Sie die shuffle-array =) Obwohl diese Lösung scheint zu sein, eher langsam, kann es sein, vektorisiert aus. Die Umsetzung, sofern unten erfordert array auf 16 byte ausgerichtet. Auch, das array muss aufgefüllt werden mit INT_MAX Elemente, weil es verbraucht 16 Elemente auf einmal.

static int linear_stgatilov_vec (const int *arr, int n, int key) {
    assert(size_t(arr) % 16 == 0);
    __m128i vkey = _mm_set1_epi32(key);
    __m128i cnt = _mm_setzero_si128();
    for (int i = 0; i < n; i += 16) {
        __m128i mask0 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+0]), vkey);
        __m128i mask1 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+4]), vkey);
        __m128i mask2 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+8]), vkey);
        __m128i mask3 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+12]), vkey);
        __m128i sum = _mm_add_epi32(_mm_add_epi32(mask0, mask1), _mm_add_epi32(mask2, mask3));
        cnt = _mm_sub_epi32(cnt, sum);
    }
    cnt = _mm_hadd_epi32(cnt, cnt);
    cnt = _mm_hadd_epi32(cnt, cnt);
// int ans = _mm_extract_epi32(cnt, 0);    //SSE4.1
    int ans = _mm_extract_epi16(cnt, 0);    //correct only for n < 32K
    return ans;
}

Die endgültige Reduktion einer einzelnen SSE2-register implementiert werden können, mit SSE2 nur wenn nötig, es sollte nicht wirklich Einfluss auf die Gesamtleistung.

Habe ich es getestet mit Visual C++ 2013 x64-compiler auf Intel Core2 Duo E4700 (ziemlich alt, ja). Der array der Größe 197 generiert wird, mit Elementen versehen, die von rand(). Den vollständigen code, mit all den Tests ist hier. Hier ist die Zeit zum ausführen 32M Suche:

[OP]
Time = 3.155 (-896368640) //the original OP's code
[Paul R]
Time = 2.933 (-896368640)
[stgatilov]
Time = 1.139 (-896368640) //the code suggested

Den OP ' s original-code Prozesse 10.6 Millionen-array pro Sekunde (2,1 Milliarden Elemente pro Sekunde). Die vorgeschlagene code-Prozesse 29.5 Millionen von arrays pro Sekunde (5,8 Milliarden Elemente pro Sekunde).
Auch der vorgeschlagene code funktioniert gut für kleinere arrays: auch für arrays von 15 Elementen, ist es immer noch fast drei mal schneller als die OP ' s original-code.

Hier ist die generierte assembly:

$LL56@main:
    movdqa  xmm2, xmm4
    movdqa  xmm0, xmm4
    movdqa  xmm1, xmm4
    lea rcx, QWORD PTR [rcx+64]
    pcmpgtd xmm0, XMMWORD PTR [rcx-80]
    pcmpgtd xmm2, XMMWORD PTR [rcx-96]
    pcmpgtd xmm1, XMMWORD PTR [rcx-48]
    paddd   xmm2, xmm0
    movdqa  xmm0, xmm4
    pcmpgtd xmm0, XMMWORD PTR [rcx-64]
    paddd   xmm1, xmm0
    paddd   xmm2, xmm1
    psubd   xmm3, xmm2
    dec r8
    jne SHORT $LL56@main
$LN54@main:
    phaddd  xmm3, xmm3
    inc rdx
    phaddd  xmm3, xmm3
    pextrw  eax, xmm3, 0

Schließlich möchte ich zu beachten, dass eine gut optimierte binäre Suche kann schneller gemacht werden, durch die Umstellung auf die beschrieben vektorisiert lineare Suche, sobald das Intervall wird kleiner.

UPDATE: Weitere Informationen finden Sie in mein blog-post auf die Sache.

Haben Sie erhalten viele Anregungen für Verbesserungen, aber Sie brauchen, um zu Messen, jede Optimierung zu sehen, welche ist am besten gegeben, Ihre hardware-und compiler -.

Als ein Beispiel, in der ersten version dieser Antwort, ich vermutete, dass von 100-200 array-Elemente, die etwas höhere Aufwand der binären Suche sollte einfach bezahlt werden von weitaus weniger Sonden in dem array. Jedoch, unten in den Kommentaren, Mark Probst berichtet, dass er sieht, lineare Suche vor bis zu 500 Einträge auf seiner hardware. Dies verstärkt die Notwendigkeit, zu Messen bei der Suche nach der besten Leistung.

Hinweis: Bearbeitet folgende Daneben auch die Kommentare unten auf seine Messungen von linearen versus binäre Suche für relativ kleine N.

Wenn Sie auf einer Intel-Plattform:

int linear (const int *array, int n, int key)
{
  __asm
  {
    mov edi,array
    mov ecx,n
    mov eax,key
    repne scasd
    mov eax,-1
    jne end
    mov eax,n
    sub eax,ecx
    dec eax
end:
  }
}

aber das findet nur genaue übereinstimmungen, nicht größer als oder gleich entspricht.

In C können Sie auch Duff ' s Device:

int linear (const int *array, int n, int key)
{
  const int
    *end = &array [n];

  int
    result = 0;

  switch (n % 8)
  {
    do {
  case 0:
    if (*(array++) >= key) break;
    ++result;
  case 7:
    if (*(array++) >= key) break;
    ++result;
  case 6:
    if (*(array++) >= key) break;
    ++result;
  case 5:
    if (*(array++) >= key) break;
    ++result;
  case 4:
    if (*(array++) >= key) break;
    ++result;
  case 3:
    if (*(array++) >= key) break;
    ++result;
  case 2:
    if (*(array++) >= key) break;
    ++result;
  case 1:
    if (*(array++) >= key) break;
    ++result;
    } while(array < end);
  }

  return result;
}

Ich weiß, dass dieses Thema alt ist, aber ich konnte nicht halten mich von der Buchung. Meine Optimierung für eine sentinel-linear-Suche:

int sentinel_linear_search(int key, int *arr, int n)
{
    int last_value, i;

    /* considering that n is the real size of the array */
    if (--n < 1)
        return -1;

    last_value = arr[n];

    /* set array last member as the key */
    arr[n] = key;

    i = 0;
    while (arr[i] != key)
        ++i;

    /* recover the real array last member */
    arr[n] = last_value;

    return (arr[i] == key) ? i : -1;
}

Den sentinel-Suche große Verbesserung ist, dass seine iteration verwendet nur eine bedingte Verzweigung (key) anstelle von zwei (index und Schlüssel).

    while (arr[i] != key)
        ++i;

Diese Antwort ist ein wenig dunkler als meine anderen, so bin ich Entsendung es separat. Es beruht auf der Tatsache, dass C garantiert eine Boolesche Ergebnis false=0 und true=1. X86 produzieren können booleans ohne Verzweigung, so könnte es schneller sein, aber ich habe es noch nicht getestet. Mikro-Optimierungen wie diese werden immer stark abhängig von Prozessor und compiler.

Als vor der Aufrufer ist dafür verantwortlich, dass eine sentinel-Wert am Ende des Arrays, um sicherzustellen, dass die Schleife beendet.

Bestimmung der optimalen Menge der loop-unrolling ein wenig Experimentieren. Suchen Sie den Punkt Abnehmender (oder negative) gibt. Ich werde nehmen eine BEUTE und versuchen 8 diese Zeit.

static int
linear (const int *arr, int n, int key)
{
        assert(arr[n] >= key);
        int i = 0;
        while (arr[i] < key) {
                i += (arr[i] < key);
                i += (arr[i] < key);
                i += (arr[i] < key);
                i += (arr[i] < key);
                i += (arr[i] < key);
                i += (arr[i] < key);
                i += (arr[i] < key);
                i += (arr[i] < key);
       }
       return i;
}

Edit: Als die Punkte Markieren, die diese Funktion stellt eine Abhängigkeit in jeder Zeile auf der vorhergehenden Zeile, die Grenzen der Fähigkeit der Prozessor-pipeline zum ausführen von Operationen parallel. So versuchen wir eine kleine änderung an der Funktion zum entfernen der Abhängigkeit. Nun die Funktion erfordert in der Tat 8 sentinel-Elemente am Ende.

static int 
linear (const int *arr, int n, int key) 
{ 
        assert(arr[n] >= key);
        assert(arr[n+7] >= key);
        int i = 0; 
        while (arr[i] < key) {
                int j = i;
                i += (arr[j] < key); 
                i += (arr[j+1] < key); 
                i += (arr[j+2] < key); 
                i += (arr[j+3] < key); 
                i += (arr[j+4] < key); 
                i += (arr[j+5] < key); 
                i += (arr[j+6] < key); 
                i += (arr[j+7] < key); 
       } 
       return i; 
} 

Schleife nach hinten, könnte dies übersetzt werden...

//loop backward

for (int i = arraySize - 1; i >=0; --i)

...auf diese( "könnte" schneller ):

    mov cx, arraySize - 1
detectionHere:
    ...
    loop detectionHere   

Andere als die, nur binary search kann die Suche schneller

Suchen Sie für eine größere element als int in einer Zeit, die Plattform - spezifisch sind, kann dies viel schneller oder langsamer, je nachdem, wie es mit der größeren Daten Lesen. Zum Beispiel, auf einem 64-bit-system, das Lesen in das array 2 Elemente zu einer Zeit und überprüfen die hi/low Elemente einzeln konnte schneller laufen, da weniger I/O. Dennoch ist dies eine O(n) verschiedene Art, egal was.

uint32 LinearFindSse4( uint8* data, size_t data_len, uint8* finddata, size_t finddatalen )
{
    /**
     * the following is based on...
     * #define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL)
     * we split it into 2 sections
     * first section is:
     * (v) - 0x01010101UL)
     *
     * second section is:
     * ~(v) & 0x80808080UL)
     */
    __m128i ones = _mm_set1_epi8( 0x01 );
    __m128i eights = _mm_set1_epi8( 0x80 );
    __m128i find_field = _mm_set1_epi8( finddata[0] );

    uint32 found_at = 0;
    for (int i = 0; i < data_len; i+=16)
    {
#define CHECKTHIS( n ) if (!memcmp(&data[i+n], &finddata[0], sizeof(finddata))) { found_at = i + n; break; }

        __m128i chunk = _mm_stream_load_si128( (__m128i *)&data[i] );
        __m128i xor_result = _mm_xor_si128( chunk, find_field );
        __m128i first_sec = _mm_sub_epi64( xor_result, ones );
        __m128i second_sec = _mm_andnot_si128( xor_result, eights );

        if(!_mm_testz_si128(first_sec, second_sec))
        {
            CHECKTHIS(0);
            CHECKTHIS(1);
            CHECKTHIS(2);
            CHECKTHIS(3);
            CHECKTHIS(4);
            CHECKTHIS(5);
            CHECKTHIS(6);
            CHECKTHIS(7);
            CHECKTHIS(8);
            CHECKTHIS(9);
            CHECKTHIS(10);
            CHECKTHIS(11);
            CHECKTHIS(12);
            CHECKTHIS(13);
            CHECKTHIS(14);
            CHECKTHIS(15);
        }
    }
    return found_at;
}

Gut, könnte man Zeiger verwenden...

static int linear(const int *array, int arraySize, int key) {
    int i;

    for(i = 0; i < arraySize; ++i) {
        if(*array >= key) {
            return i;
        }

        ++array;
    }

    return arraySize;
}