c++ bubble - Какой самый быстрый метод поиска для отсортированного массива?



sort in (8)

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

int newSearch(int sortedArray[], int toFind, int len) 
{
    // Returns index of toFind in sortedArray, or -1 if not found
    int low = 0;
    int high = len - 1;
    int mid;

    int l = sortedArray[low];
    int h = sortedArray[high];

    while (l < toFind && h > toFind) {
        mid = low + ((float)(high - low)*(float)(toFind - l))/(1+(float)(h-l));

        int m = sortedArray[mid];

        if (m < toFind) {
            l = sortedArray[low = mid + 1];
        } else if (m > toFind) {
            h = sortedArray[high = mid - 1];
        } else {
            return mid;
        }
    }

    if (l == toFind)
        return low;
    else if (h == toFind)
        return high;
    else
        return -1; // Not found
}

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

Однако я уверен, что есть способы оптимизировать эти функции, чтобы сделать их еще быстрее. У кого-нибудь есть идеи, как мне сделать эту функцию поиска быстрее? Решение в C или C ++ является приемлемым, но мне нужно, чтобы он обрабатывал массив из 100000 элементов.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <assert.h>

static __inline__ unsigned long long rdtsc(void)
{
  unsigned long long int x;
     __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
     return x;
}

int interpolationSearch(int sortedArray[], int toFind, int len) {
    // Returns index of toFind in sortedArray, or -1 if not found
    int64_t low = 0;
    int64_t high = len - 1;
    int64_t mid;

    int l = sortedArray[low];
    int h = sortedArray[high];

    while (l <= toFind && h >= toFind) {
        mid = low + (int64_t)((int64_t)(high - low)*(int64_t)(toFind - l))/((int64_t)(h-l));

        int m = sortedArray[mid];

        if (m < toFind) {
            l = sortedArray[low = mid + 1];
        } else if (m > toFind) {
            h = sortedArray[high = mid - 1];
        } else {
            return mid;
        }
    }

    if (sortedArray[low] == toFind)
        return low;
    else
        return -1; // Not found
}

int interpolationSearch2(int sortedArray[], int toFind, int len) {
    // Returns index of toFind in sortedArray, or -1 if not found
    int low = 0;
    int high = len - 1;
    int mid;

    int l = sortedArray[low];
    int h = sortedArray[high];

    while (l <= toFind && h >= toFind) {
        mid = low + ((float)(high - low)*(float)(toFind - l))/(1+(float)(h-l));
        int m = sortedArray[mid];

        if (m < toFind) {
            l = sortedArray[low = mid + 1];
        } else if (m > toFind) {
            h = sortedArray[high = mid - 1];
        } else {
            return mid;
        }
    }

    if (sortedArray[low] == toFind)
        return low;
    else
        return -1; // Not found
}

int binarySearch(int sortedArray[], int toFind, int len) 
{
    // Returns index of toFind in sortedArray, or -1 if not found
    int low = 0;
    int high = len - 1;
    int mid;

    int l = sortedArray[low];
    int h = sortedArray[high];

    while (l <= toFind && h >= toFind) {
        mid = (low + high)/2;

        int m = sortedArray[mid];

        if (m < toFind) {
            l = sortedArray[low = mid + 1];
        } else if (m > toFind) {
            h = sortedArray[high = mid - 1];
        } else {
            return mid;
        }
    }

    if (sortedArray[low] == toFind)
        return low;
    else
        return -1; // Not found
}

int order(const void *p1, const void *p2) { return *(int*)p1-*(int*)p2; }

int main(void) {
    int i = 0, j = 0, size = 100000, trials = 10000;
    int searched[trials];
    srand(-time(0));
    for (j=0; j<trials; j++) { searched[j] = rand()%size; }

    while (size > 10){
        int arr[size];
        for (i=0; i<size; i++) { arr[i] = rand()%size; }
        qsort(arr,size,sizeof(int),order);

        unsigned long long totalcycles_bs = 0;
        unsigned long long totalcycles_is_64 = 0;
        unsigned long long totalcycles_is_float = 0;
        unsigned long long totalcycles_new = 0;
        int res_bs, res_is_64, res_is_float, res_new;
        for (j=0; j<trials; j++) {
            unsigned long long tmp, cycles = rdtsc();
            res_bs = binarySearch(arr,searched[j],size);
            tmp = rdtsc(); totalcycles_bs += tmp - cycles; cycles = tmp;

            res_is_64 = interpolationSearch(arr,searched[j],size);
            assert(res_is_64 == res_bs || arr[res_is_64] == searched[j]); 
            tmp = rdtsc(); totalcycles_is_64 += tmp - cycles; cycles = tmp;

            res_is_float = interpolationSearch2(arr,searched[j],size);
            assert(res_is_float == res_bs || arr[res_is_float] == searched[j]); 
            tmp = rdtsc(); totalcycles_is_float += tmp - cycles; cycles = tmp;
        }
        printf("----------------- size = %10d\n", size);
        printf("binary search          = %10llu\n", totalcycles_bs);
        printf("interpolation uint64_t = %10llu\n",  totalcycles_is_64);
        printf("interpolation float    = %10llu\n",  totalcycles_is_float);
        printf("new                    = %10llu\n",  totalcycles_new);
        printf("\n");
        size >>= 1;
    }
}

Тестируется на Win32 Core2 Quad Q6600, gcc v4.3 msys. Компилирование с g ++ -O3, ничего особенного.

Наблюдение - утверждения, время и издержки цикла составляют около 40%, поэтому любые усиления, перечисленные ниже, следует разделить на 0,6, чтобы получить реальное улучшение в тестируемых алгоритмах.

Простые ответы:

  1. На моей машине замена int64_t на int для «low», «high» и «mid» в interpolationSearch дает ускорение от 20% до 40%. Это самый быстрый и простой способ, который я смог найти. На моем компьютере требуется около 150 циклов (для размера массива 100000). Это примерно то же количество циклов, что и при пропадании кэша. Так что в реальных приложениях уход за вашим кешем, вероятно, будет самым большим фактором.

  2. Замена "/ 2" для binarySearch на ">> 1" увеличивает скорость на 4%.

  3. Использование алгоритма STL binary_search для вектора, содержащего те же данные, что и для "arr", примерно равно скорости, которую выполняет двоичный поиск вручную. Хотя на меньших «размерах» STL гораздо медленнее - около 40%.


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

Для больших статических отсортированных наборов данных вы можете создать дополнительный индекс для частичного размещения голубей в зависимости от объема памяти, который вы готовы использовать. Например, скажем, мы создали двумерный массив диапазонов 256x256, который заполняется начальными и конечными позициями в массиве поиска элементов с соответствующими байтами старшего разряда. Когда мы приходим к поиску, мы используем старшие байты ключа, чтобы найти диапазон / подмножество массива, в котором мы должны искать. Если бы у нас было ~ 20 сравнений в нашем бинарном поиске 100 000 элементов O (log2 (n)), мы теперь сократились до ~ 4 комарисон для 16 элементов, или O (log2 (n / 15)). Стоимость памяти здесь составляет около 512к

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

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


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

Есть три файла для демонстрации.

Сортировка / код поиска регрессии:

#include <sstream>
#include <math.h>
#include <ctime>
#include "limits.h"

void insertionSort(int array[], int length) {
   int key, j;
   for(int i = 1; i < length; i++) {
      key = array[i];
      j = i - 1;
      while (j >= 0 && array[j] > key) {
         array[j + 1] = array[j];
         --j;
      }
      array[j + 1] = key;
   }
}

class RegressionTable {
   public:
      RegressionTable(int arr[], int s, int lower, int upper, double mult, int divs);
      RegressionTable(int arr[], int s);
      void sort(void);
      int find(int key);
      void printTable(void);
      void showSize(void);
   private:
      void createTable(void);
      inline unsigned int resolve(int n);
      int * array;
      int * table;
      int * tableSize;
      int size;
      int lowerBound;
      int upperBound;
      int divisions;
      int divisionSize;
      int newSize;
      double multiplier;
};

RegressionTable::RegressionTable(int arr[], int s) {
   array = arr;
   size = s;
   multiplier = 1.35;
   divisions = sqrt(size);
   upperBound = INT_MIN;
   lowerBound = INT_MAX;
   for (int i = 0; i < size; ++i) {
      if (array[i] > upperBound)
         upperBound = array[i];
      if (array[i] < lowerBound)
         lowerBound = array[i];
   }
   createTable();
}

RegressionTable::RegressionTable(int arr[], int s, int lower, int upper, double mult, int divs) {
   array = arr;
   size = s;
   lowerBound = lower;
   upperBound = upper;
   multiplier = mult;
   divisions = divs;
   createTable();
}

void RegressionTable::showSize(void) {
   int bytes = sizeof(*this);
   bytes = bytes + sizeof(int) * 2 * (divisions + 1);
}

void RegressionTable::createTable(void) {
   divisionSize = size / divisions;
   newSize = multiplier * double(size);
   table = new int[divisions + 1];
   tableSize = new int[divisions + 1];

   for (int i = 0; i < divisions; ++i) {
      table[i] = 0;
      tableSize[i] = 0;
   }

   for (int i = 0; i < size; ++i) {
      ++table[((array[i] - lowerBound) / divisionSize) + 1];
   }

   for (int i = 1; i <= divisions; ++i) {
      table[i] += table[i - 1];
   }
   table[0] = 0;

   for (int i = 0; i < divisions; ++i) {
      tableSize[i] = table[i + 1] - table[i];
   }
}

int RegressionTable::find(int key) {
   double temp = multiplier;
   multiplier = 1;

   int minIndex = table[(key - lowerBound) / divisionSize];
   int maxIndex = minIndex + tableSize[key / divisionSize];
   int guess = resolve(key);
   double t;
   while (array[guess] != key) {
      // uncomment this line if you want to see where it is searching.
      //cout << "Regression Guessing " << guess << ", not there." << endl;
      if (array[guess] < key) {
         minIndex = guess + 1;
      }
      if (array[guess] > key) {
         maxIndex = guess - 1;
      }
      if (array[minIndex] > key || array[maxIndex] < key) {
         return -1;
      }
      t = ((double)key - array[minIndex]) / ((double)array[maxIndex] - array[minIndex]);
      guess = minIndex + t * (maxIndex - minIndex);
   }

   multiplier = temp;

   return guess;
}

inline unsigned int RegressionTable::resolve(int n) {
   float temp;
   int subDomain = (n - lowerBound) / divisionSize;
   temp = n % divisionSize;
   temp /= divisionSize;
   temp *= tableSize[subDomain];
   temp += table[subDomain];
   temp *= multiplier;
   return (unsigned int)temp;
}

void RegressionTable::sort(void) {
   int * out = new int[int(size * multiplier)];
   bool * used = new bool[int(size * multiplier)];
   int higher, lower;
   bool placed;

   for (int i = 0; i < size; ++i) {

      /* Figure out where to put the darn thing */
      higher = resolve(array[i]);
      lower = higher - 1;

      if (higher > newSize) {
         higher = size;
         lower = size - 1;
      } else if (lower < 0) {
         higher = 0;
         lower = 0;
      }
      placed = false;
      while (!placed) {
         if (higher < size && !used[higher]) {
            out[higher] = array[i];
            used[higher] = true;
            placed = true;
         } else if (lower >= 0 && !used[lower]) {
            out[lower] = array[i];
            used[lower] = true;
            placed = true;
         }
         --lower;
         ++higher;
      }
   }
   int index = 0;
   for (int i = 0; i < size * multiplier; ++i) {
      if (used[i]) {
         array[index] = out[i];
         ++index;
      }
   }

   insertionSort(array, size);
}

И тогда есть обычные функции поиска:

#include <iostream>
using namespace std;

int binarySearch(int array[], int start, int end, int key) {
   // Determine the search point.
   int searchPos = (start + end) / 2;
   // If we crossed over our bounds or met in the middle, then it is not here.
   if (start >= end)
      return -1;
   // Search the bottom half of the array if the query is smaller.
   if (array[searchPos] > key)
      return binarySearch (array, start, searchPos - 1, key);
   // Search the top half of the array if the query is larger.
   if (array[searchPos] < key)
      return binarySearch (array, searchPos + 1, end, key);
   // If we found it then we are done.
   if (array[searchPos] == key)
      return searchPos;
}

int binarySearch(int array[], int size, int key) {
   return binarySearch(array, 0, size - 1, key);
}

int interpolationSearch(int array[], int size, int key) {
   int guess = 0;
   double t;
   int minIndex = 0;
   int maxIndex = size - 1;
   while (array[guess] != key) {

      t = ((double)key - array[minIndex]) / ((double)array[maxIndex] - array[minIndex]);
      guess = minIndex + t * (maxIndex - minIndex);

      if (array[guess] < key) {
         minIndex = guess + 1;
      }
      if (array[guess] > key) {
         maxIndex = guess - 1;
      }
      if (array[minIndex] > key || array[maxIndex] < key) {
         return -1;
      }
   }

   return guess;
}

А потом я написал простую основную статью, чтобы проверить различные виды.

    #include <iostream>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    #include "regression.h"
    #include "search.h"
    using namespace std;

    void randomizeArray(int array[], int size) {
       for (int i = 0; i < size; ++i) {
          array[i] = rand() % size;
       }
    }

    int main(int argc, char * argv[]) {

       int size = 100000;
       string arg;
       if (argc > 1) {
          arg = argv[1];
          size = atoi(arg.c_str());
       }
       srand(time(NULL));
       int * array;
       cout << "Creating Array Of Size " << size << "...\n";
       array = new int[size];

       randomizeArray(array, size);
       cout << "Sorting Array...\n";
       RegressionTable t(array, size, 0, size*2.5, 1.5, size);
       //RegressionTable t(array, size);
       t.sort();
       int trials = 10000000;
       int start;

       cout << "Binary Search...\n";
       start = clock();
       for (int i = 0; i < trials; ++i) {
          binarySearch(array, size, i % size);
       }
       cout << clock() - start << endl;

       cout << "Interpolation Search...\n";
       start = clock();
       for (int i = 0; i < trials; ++i) {
          interpolationSearch(array, size, i % size);
       }
       cout << clock() - start << endl;

       cout << "Regression Search...\n";
       start = clock();
       for (int i = 0; i < trials; ++i) {
          t.find(i % size);
       }
       cout << clock() - start << endl;

       return 0;
}

Попробуйте и скажите мне, будет ли это быстрее для вас. Это очень сложно, так что это действительно легко сломать, если вы не знаете, что делаете. Будьте осторожны при его изменении.

Я скомпилировал основной с g ++ на Ubuntu.


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


Реализация бинарного поиска, который использовался для сравнений, может быть улучшена. Основная идея заключается в том, чтобы изначально «нормализовать» диапазон, чтобы цель всегда была> минимальной и <максимальной после первого шага. Это увеличивает размер дельты завершения. Это также имеет эффект специальных целей кожуха, которые меньше, чем первый элемент отсортированного массива или больше, чем последний элемент отсортированного массива. Ожидайте примерно 15% улучшения времени поиска. Вот как может выглядеть код в C ++.

int binarySearch(int * &array, int target, int min, int max)
{ // binarySearch
  // normalize min and max so that we know the target is > min and < max
  if (target <= array[min]) // if min not normalized
  { // target <= array[min]
      if (target == array[min]) return min;
      return -1;
  } // end target <= array[min]
  // min is now normalized

  if (target >= array[max]) // if max not normalized
  { // target >= array[max]
      if (target == array[max]) return max;
      return -1;
  } // end target >= array[max]
    // max is now normalized

  while (min + 1 < max)
  { // delta >=2
    int tempi = min + ((max - min) >> 1); // point to index approximately in the middle between min and max
    int atempi = array[tempi]; // just in case the compiler does not optimize this
    if (atempi > target)max = tempi; // if the target is smaller, we can decrease max and it is still normalized        
    else if (atempi < target)min = tempi; // the target is bigger, so we can increase min and it is still normalized        
        else return tempi; // if we found the target, return with the index
        // Note that it is important that this test for equality is last because it rarely occurs.
  } // end delta >=2
  return -1; // nothing in between normalized min and max
} // end binarySearch

Если у вас есть некоторый контроль над расположением данных в памяти, вы можете посмотреть на массивы Judy.

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

На этой основе работают n-арные деревья, а затем массивы Джуди добавляют несколько менее важных оптимизаций.

Итог: даже «Оперативное запоминающее устройство» (ОЗУ) быстрее при последовательном доступе, чем произвольно. Алгоритм поиска должен использовать этот факт в своих интересах.


Один из способов избежать ошибок прогнозирования ветвлений - построить таблицу поиска и проиндексировать ее с использованием данных. Стефан де Бройн обсуждал это в своем ответе.

Но в этом случае мы знаем, что значения находятся в диапазоне [0, 255], и мы заботимся только о значениях> = 128. Это означает, что мы можем легко извлечь один бит, который скажет нам, хотим ли мы значения или нет: сдвигом данные вправо 7 бит, мы остаемся с 0 бит или 1 бит, и мы хотим только добавить значение, когда у нас есть 1 бит. Назовем этот бит «бит решения».

Используя значение 0/1 бит решения как индекс в массиве, мы можем сделать код, который будет одинаково быстрым, будут ли данные отсортированы или не отсортированы. Наш код всегда будет добавлять значение, но когда бит решения равен 0, мы добавим значение где-то, на что нас не волнует. Вот код:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

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

Но в моем тестировании явная таблица поиска была немного быстрее, чем это, вероятно, потому, что индексирование в таблицу поиска было немного быстрее, чем смещение битов. Это показывает, как мой код настраивается и использует таблицу поиска (невообразимо называется lut«LookUp Table» в коде). Вот код C ++:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

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

EDIT: Одна вещь, которую я забыл положить.

Методика индексирования в массив вместо использования ifоператора может использоваться для определения того, какой указатель использовать. Я видел библиотеку, которая реализовала двоичные деревья, и вместо двух указателей указателей ( pLeftи / pRightили других) имела массив указателей длины-2 и использовал метод «принятия решения», чтобы решить, какой из них следует. Например, вместо:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

эта библиотека будет делать что-то вроде:

i = (x < node->value);
node = node->link[i];

Вот ссылка на этот код: Red Black Trees , Eternally Confuzzled





c++ c algorithm sorting optimization