멀티 스레드 처리를 위해 pthread를 사용하여 C 언어로 작성된 이진 검색 프로그램

우리는 이진 검색 방법이 가장 적합하고 효과적인 정렬 알고리즘이라는 것을 알고 있습니다. 이 알고리즘은 정렬된 시퀀스에서 작동합니다. 알고리즘은 간단합니다. 중간에서 요소를 찾은 다음 목록을 두 부분으로 나누고 왼쪽 하위 목록 또는 오른쪽 하위 목록으로 이동합니다.

우리는 알고리즘을 알고 있습니다. 이제 다중 스레드 환경에서 이진 검색 기술을 사용하는 방법을 살펴보겠습니다. 스레드 수는 시스템에 존재하는 코어 수에 따라 달라집니다. 아이디어를 얻기 위해 코드를 살펴보겠습니다.

예

#include <iostream>
#define MAX 16
#define MAX_THREAD 4
using namespace std;
//place arr, key and other variables as global to access from different thread
int arr[] = { 1, 6, 8, 11, 13, 14, 15, 19, 21, 23, 26, 28, 31, 65, 108, 220 };
int key = 31;
bool found = false;
int part = 0;
void* binary_search(void* arg) {
   // There are four threads, each will take 1/4th part of the list
   int thread_part = part++;
   int mid;
   int start = thread_part * (MAX / 4); //set start and end using the thread part
   int end = (thread_part + 1) * (MAX / 4);
   // search for the key until low < high
   // or key is found in any portion of array
   while (start < end && !found) { //if some other thread has got the element, it will stop
      mid = (end - start) / 2 + start;
      if (arr[mid] == key) {
         found = true;
         break;
      }
      else if (arr[mid] > key)
         end = mid - 1;
      else
         start = mid + 1;
   }
}
main() {
   pthread_t threads[MAX_THREAD];
   for (int i = 0; i < MAX_THREAD; i++)
      pthread_create(&threads[i], NULL, binary_search, (void*)NULL);
   for (int i = 0; i < MAX_THREAD; i++)
      pthread_join(threads[i], NULL); //wait, to join with the main thread
   if (found)
      cout << key << " found in array" << endl;
   else
      cout << key << " not found in array" << endl;
}

출력

31 found in array

위 내용은 멀티 스레드 처리를 위해 pthread를 사용하여 C 언어로 작성된 이진 검색 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!