In C-Sprache geschriebenes binäres Suchprogramm, das pthread für die Multithread-Verarbeitung verwendet

Wir wissen, dass die binäre Suchmethode der am besten geeignete und effektivste Sortieralgorithmus ist. Dieser Algorithmus funktioniert mit sortierten Sequenzen. Der Algorithmus ist einfach: Er findet einfach das Element in der Mitte, teilt dann die Liste in zwei Teile und bewegt sich zur linken oder rechten Unterliste.

Wir kennen seinen Algorithmus. Jetzt werden wir sehen, wie man die binäre Suchtechnik in einer Multithread-Umgebung verwendet. Die Anzahl der Threads hängt von der Anzahl der im System vorhandenen Kerne ab. Werfen wir einen Blick auf den Code, um eine Vorstellung davon zu bekommen.

Beispiel

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

Ausgabe

31 found in array

Das obige ist der detaillierte Inhalt vonIn C-Sprache geschriebenes binäres Suchprogramm, das pthread für die Multithread-Verarbeitung verwendet. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!