more-than-50-percent(转)

• RecentChanges

I've spent the last few weeks reading papers on data stream processing. (Data stream processing is a really facinating topic. The basic idea is that you have constantly arriving new data and you want to continuously execute queries, e.g., you want to know the average of the last N elements. The difficulty is that you don't have enough space to store the whole stream or even the last N elements, or you don't have the time required to scan the last N. As such, you need an algorithm that not only incrementally updates the state to include new elements as they arrive, but also somehow expires old elements as they eclipse the event horizon! See "STREAM: The Stanford Data Stream Management System" by Arasu et al. for a good overview of the problem.)

This blog post is not about stream processing, however. This blog post is about an algorithm, which I happened to come across it while researching that data stream processing. The algorithm is able to find the element that appears more than 50% of the time in an array, if there is one. That's not so amazing by itself. The amazing part is that it has an O(N) run time and an O(1) memory requirement. Further, the algorithm is amazingly short, yet not at all obvious to me. The algorithm is described in a paper entitled "Finding Repeated Elements" by Misra and Gries.

The algorithm consists of two steps. First, it identifies a candidate value. The candidate value either occurs >50% of the time or there is no element in the array that occurs >50% of the time. The second step verifies whether the candidate element does indeed occur >50% of the time. Here's the algorithm, implemented in C:

  #define undefined (-1)
  int
  find_element_that_occurs_more_than_half_the_time (int array[], int n)
  {
    /* Step 1: Find the element that occurs >50% of the time, if
       there is one.  */
    int c = 0;
    int candidate = undefined;
    for (int i = 0; i < n; i ++)
      {
        if (array[i] == candidate)
          /* Match.  */
          c += 2;
        else if (i == c)
          /* New candidate.  */
          {
            c += 2;
            candidate = array[i];
          }
      }

    /* Step 2: Verify that the candidate actually occurs >50% of the
       time.  */
    for (i = 0, c = 0; i < n; i ++)
      if (array[i] == candidate)
        c ++;

    if (c * 2 > n)
      return candidate;
    else
      return undefined;
  }

Does it work? Valdidating a candidate is easy. My problem was understanding that selecting the candidate really works. I found it best to work through some examples. Let's consider one example, the array: [ 0, 1, 2, 2, 0, 0, 0 ], and what happens at each iteration of the the first loop:

  Initial state: i = 0, c = 0, candidate = undefined
  array[i = 0] = 0 => New candidate => c = 2, candidate = 0
  array[i = 1] = 1 => Do nothing => c = 2, candidate = 0
  array[i = 2] = 2 => New candidate => c = 4, candidate = 2
  array[i = 3] = 2 => Match => c = 6, candidate = 2
  array[i = 4] = 0 => Do nothing => c = 6, candidate = 2
  array[i = 5] = 0 => Do nothing => c = 6, candidate = 2
  array[i = 6] = 0 => New candidate => c = 8, candidate = 0

Yup, it works.

The main insight required to understand the algorithm is that when c == i, there is no element that has appeared more than 50% of the time in the first i elements so the only possibility is array[i].