Cプログラミング
 Computer >> コンピューター >  >> プログラミング >> Cプログラミング

Cプログラムでpthreadを使用したバイナリ検索?


二分探索アプローチは、最も適切で効果的な並べ替えアルゴリズムの1つであることを私たちは知っています。これは、ソートされたシーケンスで機能します。アルゴリズムは単純で、中央から要素を見つけ、リストを2つの部分で分割し、左側のサブリストまたは右側のサブリストのいずれかに移動します。

私たちはそのアルゴリズムを知っています。次に、マルチスレッド環境でバイナリ検索手法を使用する方法を説明します。スレッドの数は、システムに存在するコアの数によって異なります。アイデアを得るためのコードを見てみましょう。

#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

  1. C ++プログラムでの二分探索?

    二分探索は、半区間探索、対数探索、または二分探索とも呼ばれ、ソートされた配列内のターゲット値の位置を見つける検索アルゴリズムです。二分探索は、ターゲット値を配列の中央の要素と比較します。それらが等しくない場合、ターゲットが存在できない半分が削除され、残りの半分で検索が続行され、再び中央の要素がターゲット値と比較され、ターゲット値が見つかるまでこれが繰り返されます。残りの半分が空の状態で検索が終了した場合、ターゲットは配列に含まれていません。アイデアは単純ですが、バイナリ検索を正しく実装するには、特に配列の値が範囲内の整数のすべてではない場合、終了条件と中間点の計算に関する微妙な点に注意する必要

  2. C#での二分探索

    バイナリ検索はソートされた配列で機能します。値は配列の中央の要素と比較されます。同等性が見つからない場合は、値が存在しない半分の部分が削除されます。同様に、残りの半分の部分が検索されます。 これが配列のmid要素です。 62を見つける必要があるとしましょう。そうすると、左側の部分が削除され、右側の部分が検索されます- これらは二分探索の複雑さです- 最悪の場合のパフォーマンス O(log n) ベストケースのパフォーマンス O(1) 平均パフォーマンス O(log n) 最悪の場合のスペースの複雑さ O(1) 例 二分