次の配列があるとします。
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);
}