How to efficiently eliminate duplicate elements in double array (in C)?

Question

Although I have read through the interesting thread Algorithm: efficient way to remove duplicate integers from an array , I have not been able to find a satisfying answer to my question:

I have a one-dimensional array of doubles, which usually is rather small (containing only up to three elements) - although this need not be a criterion for the sake of generality.

Additionally, I don't want to find only real duplicates, but duplicates in a sense that the elements' difference lies below a certain threshold. While this requirement is fairly easy to handle, my actual question is: How can I implement the general duplicate removal in ANSI C with as little overhead as possible?

Remark: The main reasons I have not been able to find my solution from the mentioned thread are threefold:

1. Many of the given solutions employ languages other than pure C, so this is not of any particular help.
2. Some of the solutions won't work if all elements in the array are equal, which may likely be the case in my case.
3. Some of the described algorithms seem to be intended for integer values only. Being a C noob, any advice is greatly appreciated therefore.

ADDENDUM: In some kind of pseudo-code, what I would want to achieve is the following:

1) Sort the array in ascending manner
2) Loop through array until element before the last one
   - Check if difference of element i to element i+1 is smaller than threshold
     -> If yes, store mean value as first element of new array
     -> If no, store original value of element i as first element of new array
3) Start the same again in order to check if now the differences between the new array elements lie below the threshold
   -> Abort if no difference is smaller than the threshold anymore

Thus, my main problem is: How can I realize step 3 such that an arbitrary number of iterations is possible and the function runs as long as there are array elements that are "too close" (with respect to my threshold).

Answer 1

This problem is a variation of element distinctness problem.

Since you are looking not only for 'exact duplicates' - but also for 'close duplicates', the solution cannot contain hashing.

The solution is basically sorting the array, and then iterating it and 'skipping' elements which are dupes.

This solution is O(nlogn), and is optimal, since it is the optimal solution for arbitrary element distinctness.

C-like Pseudo code:

#define epsilon SOME_SMALL_TOLERANCE_VALUE
int trimDupes(double[] arr,int n) { 
   sort(arr);
   int i = 0;
   int currPos = 0;
   double last = -Infinity; //min double, negative infinity
   for (i = 0; i < n; i++) { 
      if (abs(last-arr[i]) > epsilon) {
          arr[currPos++] = arr[i];
          last = arr[i]; //getting this out of the condition gets a bit different behavior, think what you need.
       }
    }
    return curr; //new length of the array - after it everything is garbage.
}

This solution uses very little extra space [basically whatever space is required by the sorting algorithm + a few constants], and O(nlogn) time for sorting + an extra single iteration.

Answer 2

Sort the array. Then loop over the array, copying to another array. If the next item compared to the current item is within the threshold, then have an inner loop to compare the current item with all remaining items, skipping all within the threshold. When you get to an item outside the threshold you have the next current item.

By deciding that the starting element to start comparing from is in a specific order, then you sidestep the problem outlined in the comments to your question. But do note that the results will be different if you change the order (sorting ascending versus sorting descending).

Answer 3

I have now found a solution that works for me so far, although several function calls are needed and the complexity might not be optimal:

#include <math.h>
#include <stdlib.h>

int compareDouble (const void * a, const void * b)
{
  if ( *(double*)a <  *(double*)b ) return -1;
  if ( *(double*)a == *(double*)b ) return 0;
  if ( *(double*)a >  *(double*)b ) return 1;
}

int main(void)
{
  double x[6] = {1.0,4.0,17.0,4.0,17.0,17.0};
  size_t n = sizeof(x)/sizeof(x[0]);
  const double thresh = 5.0;

  qsort(x, n, sizeof(double), compareDouble);

  size_t i = 0;
  size_t j = 0;

  while(i<=n-1)
  {
    if(i==n-1)
    {
      x[j++] = x[i];
      break;
    }
    else if(fabs(x[i]-x[i+1])>thresh)
    {
      x[j++] = x[i++];
    }
    else
    {
      x[j++] = (x[i]+x[i+1])/2;
      i+=2;
    }
  } 

  for(i=0; i<j; i++)
  {
    printf("result[i] = %.2f\n",i,x[i]);
  }
}
return 0;

Any additional comments or remarks appreciated!