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

1. Скажите своему боссу, что вы можете сделать это на 50% быстрее, но это займет 6 месяцев и немного денег.
2. Подождите шесть месяцев.
3. Покупайте новое оборудование.

Что ж, это имеет такой же смысл, как линейный поиск по отсортированному массиву!

(А если серьезно, можете ли вы нам кое-что объяснить, почему нет бинарного поиска?)

Этот ответ немного более неясен, чем мой другой, поэтому я публикую его отдельно. Он основан на том факте, что 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; 
} 

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

Вы можете делать это параллельно.

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

Если решение, ориентированное на конкретную цель, приемлемо, вы можете легко использовать 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 = 100000 с ключом, находящимся в средней точке массива (т.е. результат = n / 2). Производительность падает примерно до 3,5x , когда n становится большим, и поэтому массив превышает размер кеша (в этом случае, вероятно, становится ограниченным пропускная способность памяти). Производительность также падает, когда n мало, из-за неэффективности реализации SIMD (конечно, она была оптимизирована для больших n).

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

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

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

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

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

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

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

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

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

// loop backward

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

... в это ("могло бы быть" быстрее):

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

Кроме этого, только двоичный поиск может ускорить поиск

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

В качестве примера в первой версии этого ответа я предположил, что при использовании 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:
  }
}

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

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

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

Поскольку вы можете поместить известные значения после последней допустимой записи, добавьте дополнительный элемент 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;
}

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

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

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

Обратите внимание, что сложность обработки каждой серии упорядоченных запросов с использованием описанного выше подхода всегда составляет O (N) , независимо от длины серии. Используя двоичный поиск, сложность будет O (M * log N) . Таким образом, по очевидным причинам, когда M близко к N , то есть запросы поступают в виде достаточно длинных упорядоченных серий, вышеупомянутый линейный поиск будет значительно превосходить двоичный поиск, в то время как для небольшого M двоичный поиск победит.

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

P.S. В качестве дополнительной информации о структуре проблемы:

Когда вам нужно выполнить поиск в упорядоченном массиве длиной N и вы заранее знаете, что запросы будут поступать в упорядоченная серия [приблизительная, средняя] длины M , оптимальный алгоритм будет выглядеть следующим образом

1. Вычислить значение шага S = [N / M] .Также имеет смысл «привязать» значение S к [ближайшей] степени 2. Думайте о своем отсортированном массиве как о последовательности блоков длиной S - так называемых S-блоки .
2. После получения запроса выполните инкрементный линейный поиск S-блока, который потенциально содержит запрашиваемое значение, то есть это обычный линейный поиск с шагом S (конечно, не забудьте начать с блока, на котором закончился предыдущий поиск).
3. После обнаружения S-блока выполните двоичный поиск в S-блоке запрошенного значения.

Вышеупомянутый алгоритм является наиболее оптимальным из возможных, в том смысле, что он достигает теоретического предела асимптотической эффективности повторяющегося поиска. Обратите внимание, что если значение M намного меньше, чем N , алгоритм «автоматически» переходит в сторону бинарного поиска , а когда M M приближается к N алгоритм "автоматически" поддерживает линейный поиск. Последнее имеет смысл, потому что в такой среде линейный поиск значительно эффективнее двоичного поиска.