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

Question

Я хочу оптимизировать этот линейный поиск:

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

Массив отсортирован, и предполагается, что функция возвращает индекс первого элемента, который больше или равен ключу. Их массив не большой (менее 200 элементов) и будет подготовлен один раз для большого количества поисков. Элементы массива после n-го могут при необходимости инициализироваться чем-то подходящим, если это ускоряет поиск.

Нет, бинарный поиск не разрешен, только линейный поиск.

Редактировать : Все мои знания по этой теме теперь обобщены в этом сообщении в блоге .

Answer 1

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

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

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

Answer 2

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

Обратите внимание, что если мы рассмотрим одиночный поисковый запрос для отсортированного массива, бинарный поиск будет значительно более эффективным методом, чем линейный поиск. Там нет спора об этом. Кроме того, когда вы выполняете несколько полностью случайных запросов к одним и тем же данным, бинарный поиск по-прежнему побеждает линейный поиск.

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

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 приближается к N алгоритму «автоматически "favors linear search. Последнее имеет смысл, потому что в такой среде линейный поиск значительно эффективнее, чем бинарный.

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

Answer 3

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

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

Answer 4

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

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

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

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 (). Полный код со всеми тестами здесь . Вот время выполнения 32M поиска:

[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

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

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

Answer 5

Если решение для конкретной цели является приемлемым, то вы можете довольно легко использовать 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).

Answer 6

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

Answer 7

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

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

Answer 8

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

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;

Answer 9

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

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

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

Answer 10

Если вы на платформе 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;
}