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

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

26 голосов
/ 30 апреля 2010

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

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

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

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

Ответы [ 20 ]

1 голос
/ 13 мая 2011

Вы можете избежать 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;
  }
}
1 голос
/ 30 апреля 2010

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

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;
}
0 голосов
/ 30 апреля 2010

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

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;
}
0 голосов
/ 30 апреля 2010

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

// loop backward

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

... к этому («могло бы быть» быстрее): 

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

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

0 голосов
/ 11 марта 2012 
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;
}
0 голосов
/ 30 апреля 2010

это может привести к векторным инструкциям (предложено 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
0 голосов
/ 01 мая 2010

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

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

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

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

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

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

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

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

0 голосов
/ 30 апреля 2010

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

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

Страница:
...