C++: что такое линейный поиск с барьером

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

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

Сравним два варианта линейного поиска в одной программе с измерением времени выполнения функций через std::chrono. Листинг закомментирован. В начале и в конце функции find_2 у нас имеются дополнительные действия, но они производятся один раз, а не на каждой итерации цикла.

#include <iostream>
#include <cstdlib>
#include <chrono>
using namespace std;
using namespace std::chrono;

size_t find_1(int const* arr, size_t size, int value) {
 for (size_t i = 0; i < size; ++i) { //Первое условие в цикле
  if (arr[i] == value) { //Второе условие для проверки значения
   return i;
  }
 }
 return numeric_limits <size_t>::max();
}

size_t find_2(int* arr, size_t size, int value) {
 if (size != 0) {
  int last = arr[size - 1]; //Сохраним прежний элемент массива
  arr[size - 1] = value; //Гарантируем, что value есть в массиве
  //Есть гарантия того, что элемент есть в массиве, значит индекс можно не проверять
  size_t i = 0;
  for (i = 0; arr[i] != value; ++i) { //Одно условие в цикле
  }
  arr[size - 1] = last; //Восстанавливаем последний элемент
  if (i != (size - 1) || value == last) { //Не уткнулись в барьер или последний элемент был искомым
   return i;
  }
 }
 return numeric_limits<size_t>::max();
}

int main() {
 const size_t n = 250000; //Размерность, если переполнение стека, уменьшить
 int arr[n];
 for (size_t i = 0; i < n; i++) arr[i] = rand() % n;
 int search = arr[n-1]; //Проверяем худший случай, когда искомый элемент - последний

 auto start = high_resolution_clock::now();
 size_t index1 = find_1(arr, n, search);
 auto stop = high_resolution_clock::now();
 auto duration = duration_cast<microseconds>(stop - start);
 if (index1 == numeric_limits <size_t>::max()) {
  cout << "Search 1: not found" << endl;
 }
 else {
  cout << "Search 1: " << index1 << endl;
 }
 cout << "Time is " << duration.count() << " ms" << endl;

 start = high_resolution_clock::now();
 size_t index2 = find_2(arr, n, search);
 stop = high_resolution_clock::now();
 duration = duration_cast<microseconds>(stop - start);
 if (index2 == numeric_limits <size_t>::max()) {
  cout << "Search 2: not found" << endl;
 }
 else {
  cout << "Search 2: " << index2 << endl;
 }
 cout << "Time is " << duration.count() << " ms" << endl;

 return 0;
}

Результаты работы программы:

Search 1: 110760
Time is 159 ms
Search 2: 110760
Time is 146 ms

12.06.2021, 12:18 [4270 просмотров]