Подтвердить что ты не робот

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

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

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-го могут при необходимости быть инициализированы чем-то соответствующим, если это ускоряет поиск.

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

Изменить. Все мои знания об этой теме теперь суммируются в этом сообщении в блоге.

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

Ответ 2

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

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

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

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, оптимальный алгоритм будет выглядеть следующим образом

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

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

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

Ответ 3

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

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

Ответ 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 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.

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

[email protected]:
    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 [email protected]
[email protected]:
    phaddd  xmm3, xmm3
    inc rdx
    phaddd  xmm3, xmm3
    pextrw  eax, xmm3, 0

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

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

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

Ответ 6

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

Ответ 7

Если вы находитесь на платформе 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 вы также можете использовать Duff 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;
}

Ответ 8

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

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

Ответ 9

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

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

Примечание. Отредактировано следующее. Отметьте комментарии ниже о его измерениях линейного и двоичного поиска для достаточно малой N.

Ответ 10

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

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;

Ответ 11

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

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

Ответ 12

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

Ответ 13

Вы могли бы избежать 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;
  }
}

Ответ 14

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

// loop backward

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

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

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

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

Ответ 15

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

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

Ответ 16

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

Ответ 17

В одном из комментариев вы сказали, что длина массива равна 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.

Ответ 18

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

Ответ 19

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

CPU : Memory speed | Example CPU | Type of optimisation
========================================================================
    Equal          |    8086     | (1) Loop unrolling
------------------------------------------------------------------------
  CPU > RAM        |  Pentium    | (2) None
  • Избегание условной ветки, требуемой для цикла, хотя данные будут давать небольшое улучшение производительности.
  • Как только процессор начнет работать быстрее, чем оперативная память, не имеет значения, насколько эффективен цикл (если он не очень плохой цикл), он будет остановлен из-за того, что придется ждать ввода данных из ОЗУ. SIMD на самом деле не помогает, поскольку преимущество параллельного тестирования все еще перевешивается из-за необходимости ждать появления большего количества данных. SIMD действительно приходит в себя, когда вы ограничены в ЦП.

Ответ 20

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

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