Как быстро вы можете сделать линейный поиск?

Поскольку вы можете поместить известные значения после последней допустимой записи, добавьте дополнительный элемент n+1 = max, чтобы убедиться, что цикл не выходит за конец массива без проверки i ‹ n.

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

Вы также можете попробовать развернуть цикл с тем же сигнальным значением:

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

Во-первых, любое быстрое решение должно использовать векторизацию для одновременного сравнения множества элементов.

Однако все опубликованные до сих пор векторизованные реализации страдают одной общей проблемой: у них есть ответвления. В результате приходится вводить поблочную обработку массива (для уменьшения накладных расходов на ветвление), что приводит к низкой производительности для небольших массивов. Для больших массивов линейный поиск хуже, чем хорошо оптимизированный бинарный поиск, поэтому нет смысла его оптимизировать.

Однако линейный поиск можно реализовать вообще без ветвлений. Идея очень проста: индекс, который вам нужен, — это именно то количество элементов в массиве, которое меньше, чем ключ, который вы ищете. Таким образом, вы можете сравнить каждый элемент массива со значением ключа и суммировать все флаги:

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

Самое интересное в этом решении то, что оно вернет один и тот же ответ, даже если вы перемешаете массив =) Хотя это решение кажется довольно медленным, его можно элегантно векторизовать. Реализация, представленная ниже, требует, чтобы массив был выровнен по 16 байтам. Кроме того, массив должен быть дополнен элементами INT_MAX, поскольку он использует 16 элементов одновременно.

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

Окончательное сокращение одного регистра SSE2 можно реализовать с помощью SSE2 только в случае необходимости, это не должно сильно влиять на общую производительность.

Я протестировал его с компилятором Visual C++ 2013 x64 на Intel Core2 Duo E4700 (довольно старый, да). Массив размером 197 генерируется из элементов, предоставленных функцией rand(). Полный код со всеми тестами находится здесь. Вот время для выполнения 32 миллионов поисков:

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

Исходный код OP обрабатывает 10,6 миллионов массивов в секунду (2,1 миллиарда элементов в секунду). Предлагаемый код обрабатывает 29,5 млн массивов в секунду (5,8 млрд элементов в секунду). Кроме того, предложенный код хорошо работает для небольших массивов: даже для массивов из 15 элементов он почти в три раза быстрее исходного кода OP.

Вот сгенерированная сборка:

$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

Напоследок хотелось бы отметить, что хорошо оптимизированный бинарный поиск можно сделать быстрее, переключившись на описанный векторизованный линейный поиск, как только интервал станет мал.

ОБНОВЛЕНИЕ. Дополнительную информацию можно найти на странице моя запись в блоге по этому поводу.

Если целевое решение является приемлемым, вы можете легко использовать SIMD (SSE, AltiVec или что-то еще, что у вас есть), чтобы получить ~ 4-кратное ускорение, тестируя 4 элемента за раз, а не только 1.

Из интереса я собрал простую реализацию SIMD следующим образом:

int linear_search_ref(const int32_t *A, int32_t key, int n)
{
    int result = -1;
    int i;

    for (i = 0; i < n; ++i)
    {
        if (A[i] >= key)
        {
            result = i;
            break;
        }
    }
    return result;
}

int linear_search(const int32_t *A, int32_t key, int n)
{
#define VEC_INT_ELEMS 4
#define BLOCK_SIZE (VEC_INT_ELEMS * 32)
    const __m128i vkey = _mm_set1_epi32(key);
    int vresult = -1;
    int result = -1;
    int i, j;

    for (i = 0; i <= n - BLOCK_SIZE; i += BLOCK_SIZE)
    {
        __m128i vmask0 = _mm_set1_epi32(-1);
        __m128i vmask1 = _mm_set1_epi32(-1);
        int mask0, mask1;

        for (j = 0; j < BLOCK_SIZE; j += VEC_INT_ELEMS * 2)
        {
            __m128i vA0 = _mm_load_si128(&A[i + j]);
            __m128i vA1 = _mm_load_si128(&A[i + j + VEC_INT_ELEMS]);
            __m128i vcmp0 = _mm_cmpgt_epi32(vkey, vA0);
            __m128i vcmp1 = _mm_cmpgt_epi32(vkey, vA1);
            vmask0 = _mm_and_si128(vmask0, vcmp0);
            vmask1 = _mm_and_si128(vmask1, vcmp1);
        }
        mask0 = _mm_movemask_epi8(vmask0);
        mask1 = _mm_movemask_epi8(vmask1);
        if ((mask0 & mask1) != 0xffff)
        {
            vresult = i;
            break;
        }
    }
    if (vresult > -1)
    {
        result = vresult + linear_search_ref(&A[vresult], key, BLOCK_SIZE);
    }
    else if (i < n)
    {
        result = i + linear_search_ref(&A[i], key, n - i);
    }
    return result;
#undef BLOCK_SIZE
#undef VEC_INT_ELEMS
}

На процессоре Core i7 с тактовой частотой 2,67 ГГц, используя OpenSUSE x86-64 и gcc 4.3.2, я получаю 7x - 8x улучшения в довольно широкой "зоне наилучшего восприятия", где n = 100 000, а ключ находится в средней точке массива (т. е. результат = н/2). Производительность падает примерно до 3.5x, когда n становится большим, и поэтому размер массива превышает размер кэша (предположительно, в этом случае становится ограниченной пропускная способность памяти). Производительность также падает, когда n мало, из-за неэффективности реализации SIMD (конечно, она была оптимизирована для больших n).

Вы получили много предложений по улучшению, но вам нужно измерить каждую оптимизацию, чтобы определить, какая из них лучше всего подходит для вашего оборудования и компилятора.

В качестве примера, в первой версии этого ответа я предположил, что на 100-200 элементов массива немного более высокие накладные расходы бинарного поиска должны легко быть оплачены гораздо меньшим количеством зондов в массиве. Однако в комментариях ниже Марк Пробст сообщает, что он видит линейный поиск вперед примерно до 500 записей на своем оборудовании. Это усиливает необходимость измерения при поиске наилучшей производительности.

Примечание: отредактировано после комментариев Марка ниже о его измерениях линейного и бинарного поиска для достаточно малых значений N.

Можно параллельно.

Если список небольшой, возможно, не стоит разделять поиск, но если нужно обработать много поисков, то вы можете определенно запустить их параллельно. Это не уменьшит задержку операций, но улучшит пропускную способность.

Если вы используете платформу Intel:

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

но это находит только точные совпадения, а не совпадения больше или равные.

В C вы также можете использовать устройство Дафф:

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

Если бы у вас был квантовый компьютер, вы могли бы использовать алгоритм Гровера для поиска ваших данных в O (N^1/2) раз и используя O(log N) дискового пространства. В противном случае ваш вопрос довольно глуп. Бинарный поиск или один из его вариантов (например, троичный поиск) — действительно лучший выбор. Выполнять микрооптимизацию линейного поиска глупо, когда вы можете выбрать более совершенный алгоритм.

Я знаю, что эта тема старая, но я не мог удержаться от сообщения. Моя оптимизация для дозорного линейного поиска:

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

Большим улучшением дозорного поиска является то, что его итерация использует только одну условную ветвь (ключ) вместо двух (индекс и ключ).

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

развернуть с фиксированными индексами массива.

int linear( const int *array, int n, int key ) {
  int i = 0;
  if ( array[n-1] >= key ) {
     do {
       if ( array[0] >= key ) return i+0;
       if ( array[1] >= key ) return i+1;
       if ( array[2] >= key ) return i+2;
       if ( array[3] >= key ) return i+3;
       array += 4;
       i += 4;
     } while ( true );
  }
  return -1;
}

Этот ответ немного более неясен, чем мой другой, поэтому я публикую его отдельно. Он основан на том факте, что C гарантирует логический результат false=0 и true=1. X86 может создавать логические значения без ветвления, поэтому он может быть быстрее, но я его не тестировал. Подобные микрооптимизации всегда будут сильно зависеть от вашего процессора и компилятора.

Как и прежде, вызывающая сторона отвечает за размещение контрольного значения в конце массива, чтобы гарантировать завершение цикла.

Чтобы определить оптимальную величину развертывания цикла, нужно поэкспериментировать. Вы хотите найти точку убывающей (или отрицательной) отдачи. Я собираюсь взять SWAG и попробовать 8 на этот раз.

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

Редактировать. Как указывает Марк, эта функция вводит зависимость в каждой строке от предыдущей строки, что ограничивает способность конвейера процессора выполнять операции параллельно. Итак, давайте попробуем небольшую модификацию функции, чтобы удалить зависимость. Теперь функция действительно требует 8 дозорных элементов в конце.

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

Вы можете избежать n проверок, подобных тому, как это делает развертывание цикла.

static int linear(const int *array, int arraySize, int key)
{
  //assuming the actual size of the array is always 1 less than arraySize
  array[arraySize] = key; 

  int i = 0;
  for (; ; ++i)
  {
     if (array[i] == key) return i;
  }
}

петля назад, это может быть переведено ...

// loop backward

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

... к этому ("может быть" быстрее):

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

Кроме того, только бинарный поиск может ускорить поиск.

это может вызвать векторные инструкции (предложенные Gman):

for (int i = 0; i < N; i += 4) {
    bool found = false;   
    found |= (array[i+0] >= key);
    ...
    found |= ( array[i+3] >= key);
    // slight variation would be to use max intrinsic
    if (found) return i;
}
...
// quick search among four elements

это также делает меньше инструкций ветвления. вы помогаете, гарантируя, что входной массив выровнен по границе 16 байтов

еще одна вещь, которая может помочь векторизации (выполнение вертикального максимального сравнения):

for (int i = 0; i < N; i += 8) {
    bool found = false;   
    found |= max(array[i+0], array[i+4]) >= key;
    ...
    found |= max(array[i+3], array[i+7] >= key;
    if (found) return i;
}
// have to search eight elements

Вы можете искать более крупный элемент, чем int за раз - в частности, платформа, это может быть намного быстрее или медленнее в зависимости от того, как он обрабатывает чтение больших данных. Например, в 64-разрядной системе чтение массива по 2 элемента за раз и проверка элементов hi/low по отдельности может выполняться быстрее из-за меньшего количества операций ввода-вывода. Тем не менее, это сортировка O (n), несмотря ни на что.

В одном из комментариев вы сказали, что длина массива равна 64.

Что ж, если вы должны сделать это линейно, вы можете сделать следующее:

int i = -1;
do {
  if (arr[0] >= key){i = 0; break;}
  if (arr[1] >= key){i = 1; break;}
  ...
  if (arr[62] >= key){i = 62; break;}
  if (arr[63] >= key){i = 63; break;}
} while(0);

Однако я серьезно сомневаюсь, что это быстрее, чем этот бинарный поиск: *

int i = 0;
if (key >= arr[i+32]) i += 32;
if (key >= arr[i+16]) i += 16;
if (key >= arr[i+ 8]) i +=  8;
if (key >= arr[i+ 4]) i +=  4;
if (key >= arr[i+ 2]) i +=  2;
if (key >= arr[i+ 1]) i +=  1;

*Спасибо Джону Бентли за это.

Добавлено: поскольку вы сказали, что эта таблица подготовлена ​​один раз для большого количества поисков, и вы хотите быстро, вы можете выделить где-то немного места и сгенерировать машинный код с жестко зашитыми в него значениями. Это может быть линейный или бинарный поиск. В случае бинарного кода машинный код будет выглядеть так, как это сгенерирует компилятор:

if (key < value32){
  if (key < value16){
    ...
  }
  else {
    ...
  }
}
else {
  if (key < value48){
    ...
  }
  else {
    ...
  }
}

Затем вы просто копируете это в то место, где вы можете его вызвать.

ИЛИ вы можете распечатать приведенный выше код, скомпилировать и скомпоновать его на лету в dll и загрузить dll.

На самом деле ответ на этот вопрос на 100% зависит от платформы, для которой вы пишете код. Например:

CPU : Memory speed | Example CPU | Type of optimisation
========================================================================
    Equal          |    8086     | (1) Loop unrolling
------------------------------------------------------------------------
  CPU > RAM        |  Pentium    | (2) None

1. Избегание условного перехода, необходимого для зацикливания данных, даст небольшое улучшение производительности.
2. Как только ЦП начинает работать быстрее, чем ОЗУ, не имеет значения, насколько эффективным становится цикл (если только это не действительно плохой цикл), он будет останавливаться из-за необходимости ждать, пока данные будут загружены из ОЗУ. SIMD на самом деле не помогает, поскольку преимущество параллельного тестирования все еще перевешивается необходимостью ждать поступления дополнительных данных. SIMD действительно вступает в свои права, когда вы ограничены процессором.

Ну, вы могли бы использовать указатели...

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