1

次の配列があるとします。

int a[] = new int[15];

各値は、データベース内の期間内の特定の状態にある数日間のカウンターです。例: 2000 年 1 月 1 日から 2000 年 1 月 3 日までの期間 (3 か月ではなく 3 日) : XXXXX状態の日数。

私がやりたいのは、オブジェクト数が Web サイトのオブジェクト数と比較して正しいかどうかを確認することです。Web サイトがロードされていない場合、検索自体にはせいぜい数秒かかります。

a の値を別の配列のいくつかの固定値と比較する非常に単純なテスト プロジェクトを作成し、異なる値をランダムに選択しました。実際、15 のうち 7 が異なっていました。

現在実装されているアルゴリズムは二分探索です。このコードの出力は正しいですが、実際のアプリケーションで発生する検索の数は、提供されたデータに対して 144 であり、まったく効率的ではありません。検索数 (またはこの例では集計計算) を最小限に抑えるために使用できる他のアルゴリズムはありますか?

重要な注意:期間は 2010 年 9 月 1 日から今日までになる可能性があるため、現時点では、毎日個別に検索することはできません。

必要に応じて説明を求めてください。

    a = new int[15];
    b = new int[15];
    searchCount = 0;

    // Fill a and b with some test values
        a[0] = 12;
        a[1] = 13;
        a[2] = 26;
        a[3] = 30;
        a[4] = 6;
        a[5] = 3;
        a[6] = 1;
        a[7] = 2;
        a[8] = 8;
        a[9] = 12;
        a[10] = 19;
        a[11] = 21;
        a[12] = 56;
        a[13] = 100;
        a[14] = 80;

        b[0] = 11;
        b[1] = 9;
        b[2] = 26;
        b[3] = 30;
        b[4] = 8;
        b[5] = 3;
        b[6] = 1;
        b[7] = 5;
        b[8] = 8;
        b[9] = 13;
        b[10] = 19;
        b[11] = 21;
        b[12] = 55;
        b[13] = 99;
        b[14] = 80;
    // Filled.

    void BinarySearch(int start, int end)
    {
        if (AreSumsEqual(start, end))
        {
            Debug.WriteLine("Values from positions" + start + " to " + end + " are ok");
        }
        else if (start == end)
        {
            Debug.WriteLine("Value at position " + start + " is not ok");
        }
        else
        {
            int mid = Middle(start, end);
            BinarySearch(start, mid - 1);
            BinarySearch(mid, end);
        }
    }

    int Middle(int start, int end)
    {
        return (int)Math.Ceiling((start + end) / 2.0);
    }

    bool AreSumsEqual(int start, int end)
    {
        bool areEqual = false;
        int sumA = 0;
        int sumB = 0;
        for (int i = start; i <= end; i++)
        {
            sumA += a[i];
            sumB += b[i];
            searchCount += 2; // Each sum calculated is the same as one 
            // website search. This takes the most time in real application, so
            // repeat it as few times as possible.
        }

        return areEqual = (sumA == sumB);
    }
4

2 に答える 2

1

すべての[開始、終了]の組み合わせをチェックする必要があるため、ここでは二分探索を使用できません。また、二分探索で両方向に検索する場合、とにかく二分探索ではありません。

次の解決策をお勧めします。

// Remove this, if you want all matches
bool found = false;

for (int start = 0; start < a.count; start++)
{
      // Maybe you need end = start + 1, not sure
    for (int end = start; end < a.count; end++)
    {
        if (AreSumsEqual(start, end)
        {
            // Found! Let's break to avoid useless iterations,
            // if we only want one match.
            found = true;
            break;
        }
    }

    if (found)
    {
        break;
    }   
}

これは、最悪の場合O（n²）であるO（[n（n-1）] / 2）（私が間違っていない場合）で実行されます。すべての[開始、終了]の組み合わせをチェックする必要があるため、これをより小さな桁で解決することはできません。

編集：これは私があなたの質問を理解したことを条件としています。

于 2012-11-14T10:41:28.427 に答える
0 
var SearchResults = a.Select((value, index) => a[index] == b[index]);

for (int i=0;i<a.Length;i++)
{
  Debug.WriteLine("Values in position {0} are {1}", i, SearchResults.ToList()[i]);
}

コメントで述べたように、必要なのは 2 つの配列の各位置を簡単に比較することだけです。

于 2012-11-14T11:08:06.347 に答える