2

配列の各要素を調べて、その特定の要素が 1 つの INT より大きく、別の INT より小さいかどうかを判断する関数を実装しようとしています。例えば：

Return true if Arr[5] is >i && < u

これは基本的なアルゴリズムとして機能しますが、「分割統治」方法論を使用してより効率的なコードを作成したいのですが、再帰を使用してそれをカウントするのに問題があり、すべての例がありますsee は、2 点ではなく 1 点の比較のみを扱います。誰でも状況に光を当てることができますか？(http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm)

私の元のコード（線形）：

int SimpleSort(int length) 
{ 
    int A[] = {25,5,20,10,50}; 
    int i = 25; //Less Than int 
    u = 2; //Greater Than 
    for(int Count = 0; Count < length; Count++) //Counter 
    { 
        if (A[Count] <= i && A[Count] >= u) //Checker 
            return true; 
    } return false;
}

私がこれまでに拾ってきたものからのサンプルコード（さまざまなことに何時間も取り組んだ後、別のサンプルコードを使用した後、運が悪かった：

int A[] = {5,10,25,30,50,100,200,500,1000,2000};
int i = 10; //Less Than
int u = 5;  //Greater Than


int min = 1;
int max = length;
int mid = (min+max)/2;

if (i < A[mid] && u > A[mid])
{
    min = mid + 1;

}
else
{
    max = mid - 1;
}
Until i <= A1[mid] && u >= A1[mid])

この質問が明確でない場合は、申し訳ありませんが、何か詳しく説明する必要があるかどうか尋ねてください.

4

3 に答える 3

3

入力ベクトルが常にソートされていると仮定すると、このようなものがうまくいくと思います。これは私が思いついた最も単純な形式で、パフォーマンスは O(log n) です。

bool inRange(int lval, int uval, int ar[], size_t n)
{
    if (0 == n)
        return false;

    size_t mid = n/2;
    if (ar[mid] >= std::min(lval,uval))
    {
        if (ar[mid] <= std::max(lval,uval))
            return true;
        return inRange(lval, uval, ar, mid);
    }
    return inRange(lval, uval, ar+mid+1, n-mid-1);
}

これは暗黙の範囲差分を使用します。つまり、常に 2 つの値の低い方を下限として使用し、2 つの値のうち高い方を上限として使用します。lvalおよびの入力値をuvalゴスペルとして扱うことが使用法で義務付けられている場合、およびそのためのすべての呼び出しがfalse を返す必要がある場合 (それは不可能であるため)、および展開lval > uvalを削除できます。いずれの場合も、外側のフロントローダーを作成し、(a) 絶対的な順序付けが必要な場合はすぐに false として返す、または (b) lval と uval を適切に事前に決定する、の順序を事前にチェックすることで、パフォーマンスをさらに向上させることができます。範囲差が必要な場合は注文してください。このような両方の外部ラッパーの例を以下に示します。std::min()std::max()lvaluvallval > uval

// search for any ar[i] such that (lval <= ar[i] <= uval)
//  assumes ar[] is sorted, and (lval <= uval).
bool inRange_(int lval, int uval, int ar[], size_t n)
{
    if (0 == n)
        return false;

    size_t mid = n/2;
    if (ar[mid] >= lval)
    {
        if (ar[mid] <= uval)
            return true;
        return inRange_(lval, uval, ar, mid);
    }
    return inRange_(lval, uval, ar+mid+1, n-mid-1);
}

// use lval and uval as an hard range of [lval,uval].
//  i.e. short-circuit the impossible case of lower-bound
//  being greater than upper-bound.
bool inRangeAbs(int lval, int uval, int ar[], size_t n)
{
    if (lval > uval)
        return false;
    return inRange_(lval, uval, ar, n);
}

// use lval and uval as un-ordered limits. i.e always use either
// [lval,uval] or [uval,lval], depending on their values.
bool inRange(int lval, int uval, int ar[], size_t n)
{
    return inRange_(std::min(lval,uval), std::max(lval,uval), ar, n);
}

あなたが欲しいと思うものを として残しましたinRange。メイン ケースとエッジ ケースをうまくカバーするために実行された単体テストと、結果の出力を以下に示します。

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <iterator>

int main(int argc, char *argv[])
{
    int A[] = {5,10,25,30,50,100,200,500,1000,2000};
    size_t ALen = sizeof(A)/sizeof(A[0]);
    srand((unsigned int)time(NULL));

    // inner boundary tests (should all answer true)
    cout << inRange(5, 25, A, ALen) << endl;
    cout << inRange(1800, 2000, A, ALen) << endl;

    // limit tests (should all answer true)
    cout << inRange(0, 5, A, ALen) << endl;
    cout << inRange(2000, 3000, A, ALen) << endl;

    // midrange tests. (should all answer true)
    cout << inRange(26, 31, A, ALen) << endl;
    cout << inRange(99, 201, A, ALen) << endl;
    cout << inRange(6, 10, A, ALen) << endl;
    cout << inRange(501, 1500, A, ALen) << endl;

    // identity tests. (should all answer true)
    cout << inRange(5, 5, A, ALen) << endl;
    cout << inRange(25, 25, A, ALen) << endl;
    cout << inRange(100, 100, A, ALen) << endl;
    cout << inRange(1000, 1000, A, ALen) << endl;

    // test single-element top-and-bottom cases
    cout << inRange(0,5,A,1) << endl;
    cout << inRange(5,5,A,1) << endl;

    // oo-range tests (should all answer false)
    cout << inRange(1, 4, A, ALen) << endl;
    cout << inRange(2001, 2500, A, ALen) << endl;
    cout << inRange(1, 1, A, 0) << endl;

    // performance on LARGE arrays.
    const size_t N = 2000000;
    cout << "Building array of " << N << " random values." << endl;
    std::vector<int> bigv;
    generate_n(back_inserter(bigv), N, rand);

    // sort the array
    cout << "Sorting array of " << N << " random values." << endl;
    std::sort(bigv.begin(), bigv.end());

    cout << "Running " << N << " identity searches..." << endl;
    for (int i=1;i<N; i++)
        if (!inRange(bigv[i-1],bigv[i],&bigv[0],N))
        {
            cout << "Error: could not find value in range [" << bigv[i-1] << ',' << bigv[i] << "]" << endl;
            break;
        };
    cout << "Finished" << endl;

    return 0;
}

出力結果:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
Sorting array of 2000000 random values.
Running 2000000 identity searches...
Finished
于 2012-11-08T09:02:38.950 に答える
1

配列がソートされていると仮定すると、実際にはかなり簡単です。シーケンスのそれぞれの左側または右側を常に見ることで、対数の複雑さを回避できます。

#include <iterator>

template <typename Limit, typename Iterator>
bool inRange(Limit lowerBound, Limit upperBound, Iterator begin, Iterator end) {
  if (begin == end) // no values => no valid values
    return false;
  Iterator mid = begin;
  auto const dist = std::distance(begin,end);
  std::advance(mid,dist/2); // mid might be equal to begin, if dist == 1
  if (lowerBound < *mid && *mid < upperBound)
    return true;
  if (dist == 1) // if mid is invalid and there is only mid, there is no value
    return false;
  if (*mid > upperBound)
    return inRange(lowerBound, upperBound, begin, mid);
  std::advance(mid,1); // we already know mid is invalid
  return inRange(lowerBound, upperBound, mid, end);
}

これを単純な配列に対して呼び出すには、次のようにします。

inRange(2,25,std::begin(A),std::end(A));
于 2012-11-08T08:04:28.973 に答える
0

私の理解では、特定の問題に分割統治法を使用しても有利にはなりません。ただし、少なくともあなたの例では、入力はソートされています。下限に達するまで値をスキップすることで、少し改善できるはずです。

于 2012-11-08T07:52:51.747 に答える