Databases
StackOverflow2013
Postsdbo
POMost effective search algorithm to find multiple incorrect values in an array
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMost effective search algorithm to find multiple incorrect values in an array
    primarykey
    data
    text
    <p>Suppose the next array:</p> <pre><code>int a[] = new int[15]; </code></pre> <p>Each value is a counter of some days in a specific state in a period in a database. Example: <strong>Period 1/1/2000 - 1/3/2000 (3 days, not 3 months)</strong>: Number of days in state <strong>XXXXX</strong>.</p> <p>What I want to do is check if the objects count is correct compared to the objects count on a website. The search itself takes some seconds at best if the website is not loaded.</p> <p>I had made a very simple test project which compares the values of a with some fixed values on another array and I randomly chose some values to be different, in fact 7 out of 15 were different.</p> <p>The current algorithm implemented is <strong>binary search</strong>. The output of this piece of code is correct, but the number of searches that would occur on the real application is 144 for the data provided, which is not efficient at all. Is there any other algorithm that I could use to minimize the number of searches (or summary calculations in this example)?</p> <p><strong>IMPORTANT NOTE:</strong> The periods can be as large as Sep 1, 2010 - Today, so for the moment searching each day independently is not an option.</p> <p><em>Ask me for explanations if needed.</em></p> <pre><code> 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 &lt;= 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); } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USiCantSeeSharp
    1. USiCantSeeSharp
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POMost effective search algorithm to find multiple incorrect values in an array
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHave you tried the binary search provided in .net framework? http://msdn.microsoft.com/en-us/library/system.array.binarysearch.aspx
      singulars
      1. POMost effective search algorithm to find multiple incorrect values in an array
      1. USCarlos Ferreira
    2. COAm I wrong, or does the algorithm mark [1,2,3,4] and [1,1,4,4] as _ok_, but [1,2,3,4] and [2,1,3,5] as _not ok at the fourth position_? And wouldn't it be easier to sum up everything once while at the same time looking for the first difference and return that if the result isn't equal?
      singulars
      1. POMost effective search algorithm to find multiple incorrect values in an array
      1. USNuffin
    3. COCould you add the test data?
      singulars
      1. POMost effective search algorithm to find multiple incorrect values in an array
      1. USNikola Davidovic
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload