-1
\$\begingroup\$

I would like to merge two double arrays and remove from the result array approximately equal items.

My two input arrays have length up to 100000 and are sorted. Them self they don't contain approximately equal items.

What are approximately equal items, see System.Double documentation and there the example IsApproximatelyEqual

static bool IsApproximatelyEqual(double value1, double value2, double epsilon)
{
   // If they are equal anyway, just return True.
   if (value1.Equals(value2))
      return true;

   // Handle NaN, Infinity.
   if (Double.IsInfinity(value1) | Double.IsNaN(value1))
      return value1.Equals(value2);
   else if (Double.IsInfinity(value2) | Double.IsNaN(value2))
      return value1.Equals(value2);

   // Handle zero to avoid division by zero
   double divisor = Math.Max(value1, value2);
   if (divisor.Equals(0)) 
      divisor = Math.Min(value1, value2);

   // https://github.com/dotnet/samples/pull/1152/
   return Math.Abs((value1 - value2) / divisor) <= epsilon;
}

I wrote the following method, but it gets very slow using large arrays.

public static double[] Union(double[] a, double[] b)
{
    List<double> alist = new List<double>(a);
    for (int i = 0; i < b.Length; i++)
    {
        if (!alist.Exists(ai => IsApproximatelyEqual(ai, b[i], 1e-15))
            alist.Add(b[i]);
    }
    alist.Sort();
    return alist.ToArray();
}

Then I wrote the following method, which is much faster:

public static double[] Union2(double[] a, double[] b)
{
    int i1 = 0, i2 = 0;
    int n1 = a.Length, n2 = b.Length;
    List<double> c = new List<double>(n1 + n2);
    while (i1 < n1 || i2 < n2)
    {
        if (i1 < n1)
        {
            if (i2 < n2)
            {
                if (IsApproximatelyEqual(a[i1], b[i2], 1e-15))
                {
                    c.Add(a[i1++]);
                    i2++;
                }
                else if (a[i1] < b[i2])
                {
                    c.Add(a[i1++]);
                }
                else
                {
                    c.Add(b[i2++]);
                }
            }
            else
            {
                c.Add(a[i1++]);
            }
        }
        else //if (i2 < n2)
        {
            c.Add(b[i2++]);
        }
    }
    return c.ToArray();
}

You can try it out online.

Is there a way to speed up the above code?

For epsilon I'm using 1e-15 because a double has a maximum precision of 15 digits and an internal precision of 17 digits.

\$\endgroup\$
  • 1
    \$\begingroup\$ You should be able to sort both arrays then iterate through them checking if values are close to determine which to keep. This would also mean the result was sorted since you seem to need that at the end anyway. \$\endgroup\$ – juharr Aug 8 at 15:28
  • \$\begingroup\$ How many items do your real arrays contain? \$\endgroup\$ – t3chb0t Aug 8 at 16:00
  • 1
    \$\begingroup\$ I don't understand the "remove the duplicates" requirement: could you make that clearer? \$\endgroup\$ – VisualMelon Aug 8 at 16:00
  • 2
    \$\begingroup\$ @t3chb0t It's a confusing question. I propose OP to clarify with proper use cases that show difference between absolute and relative tolerance. Also, when swapping array a with b, I think different results could yield. \$\endgroup\$ – dfhwze Aug 8 at 16:31
  • 1
    \$\begingroup\$ "which have a relative accuracy of 1e-15" is that the chance of them being rightfully a duplicate or the chance they're not? That's a major difference. The way you phrase it now, it looks like random chance has a higher accuracy than your program. \$\endgroup\$ – Mast Aug 8 at 17:21
3
\$\begingroup\$

Wait, are the arrays already sorted?

These are just my initial thoughts, but:

  • The initial creation of your new list I'm guessing is \$O(n)\$ to create a copy of array a (\$n\$ is the length of a). This might be unavoidable if you want a nondestructive function, though the arrays are passed in by value, so it may not be necessary.

  • List.Exists is that it's a linear operation, so the combination of the two arrays I think will be \$O(m(n+m))\$ (\$m\$ is the length of b). I arrived at this conclusion because for every element in b, we have to search through our combined list. so that's \$m\$ * the search complexity. For the search complexity, since this is big \$O\$ notation, I assumed that a did not contain any of b's elements, so as we insert an element from b into our combined list, the search complexity grows, up until the size of a + b. There's actually a little more complexity to the List.Add operation due to some nuances, but we'll just say it's \$O(1)\$.

  • Finally, you sort the list after combining everything, so I imagine C# uses one of the faster sorting algorithms, and that is \$O(xlog(x))\$ (\$x\$ is the length of the final combined list).

So in terms of complexity, if all of this is true, we have \$n + m(m+n) + xlogx\$.

Back to my initial question, if the arrays are already sorted coming in, I'm thinking you can find any element with a binary search which is \$O(log(y))\$ (\$y\$ is the size of the array you're searching in), so you can search for every element in b within a, and we can probably tweak the binary search to return the left and/or right indexes if the number wasn't found, in which case we simply have to insert between those indexes. The operation then would be \$O(mlog(n))\$ + the complexity to insert. Unfortunately, and in shameful admittance, random access inserts of arrays is where this algorithm falls off, but you can optimize the insert complexity by choosing a different data structure from an array.

Of course, this method actually only requires one of the arrays be sorted before starting, and sorting one array beforehand would be faster than sorting the whole array at the end.

So in conclusion, you can drop the sort at the end, and you can work to remove the linear List.exists operation to speed up your code. If you're truly gungho you can try using a different data structure that can amortize both search and insert operations.

\$\endgroup\$
  • 2
    \$\begingroup\$ You don't need a binary search - just a similar approach to Merge Sort: starting from the front of both inputs, take the lower one, and enter it into the result array, unless it's the same value (within tolerance) as the current back of the result. \$\endgroup\$ – Toby Speight Aug 8 at 17:03
  • \$\begingroup\$ @TobySpeight But it is not clear how to calculate the tolerance. depending which array is a and which b 2 values are either equivalent or not. \$\endgroup\$ – dfhwze Aug 8 at 17:05
  • 1
    \$\begingroup\$ It shouldn't matter - the difference between b-a < 1e-15 × b and b-a < 1e-15 × a is only 1e-30 × b, which is near the limit of precision. \$\endgroup\$ – Toby Speight Aug 8 at 17:21
  • 1
    \$\begingroup\$ You feel your answer got invalidated because of the updated question? If so, I suggest OP to post a new question as follow-up to this one and we'll revert this one and keep it closed. \$\endgroup\$ – dfhwze Aug 9 at 11:46
  • 2
    \$\begingroup\$ @dfhwze I think this answer is still valid as the only point where it speaks about OP's code is that the arrays are sorted... and they still are. Anything else is very abstract and general. \$\endgroup\$ – t3chb0t Aug 9 at 17:05
1
\$\begingroup\$

If you need performance optimized code, your solution looks very well. I think the performance can be optimized best by using a simplified aproximation approach (e.g.: Math.Abs(value1 - value2) <= Double.Epsilon).

Another note (that actually doesn't affect performance): Use '||' instead of use '|' because the second one evaluates always both conditions whereas the firs one stops as soon as the result is known.

However, for 100.000 sorted values, performance doesn't matter. For that use case I would optimize code for maintainablity and readability:

public class ApproximatelyDoubleComparer : IEqualityComparer<Double>
{
    private readonly double epsilon;

    public ApproximatelyDoubleComparer(double epsilon)
    {
        this.epsilon = epsilon;
    }

    public bool Equals(double value1, double value2)
    {
        // If they are equal anyway, just return True.
        if (value1.Equals(value2))
            return true;

        // Handle NaN, Infinity.
        if (Double.IsInfinity(value1) | Double.IsNaN(value1))
            return value1.Equals(value2);
        else if (Double.IsInfinity(value2) | Double.IsNaN(value2))
            return value1.Equals(value2);

        // Handle zero to avoid division by zero
        double divisor = Math.Max(value1, value2);
        if (divisor.Equals(0))
            divisor = Math.Min(value1, value2);

        // https://github.com/dotnet/samples/pull/1152/
        return Math.Abs((value1 - value2) / divisor) <= epsilon;
    }

    public int GetHashCode(double obj)
    {
        return obj.GetHashCode();
    }
}

Usage;

var union = a1.Concat(a2)
              .Distinct(new ApproximatelyDoubleComparer(1e-15))
              .OrderBy(x => x) // if a sorted list is required
              .ToArray();
\$\endgroup\$
  • \$\begingroup\$ Your first statement does change the specification of the OP's intended precision. I don't think we should change spec for the mere purpose of optimizing performance. \$\endgroup\$ – dfhwze Aug 9 at 18:09
  • \$\begingroup\$ Do you mean Math.Abs(value1 - value2) <= Double.Epsilon? \$\endgroup\$ – JanDotNet Aug 9 at 18:12
  • \$\begingroup\$ Yes or am I missing your point here? \$\endgroup\$ – dfhwze Aug 9 at 18:13
  • \$\begingroup\$ You are right. My point was: There is not much potential in the algorithm for perfomance optimization. If performance optimization is a requirement, a simplified definition of "Approximately" has the most potential ;). \$\endgroup\$ – JanDotNet Aug 9 at 18:17
  • \$\begingroup\$ Fair enough :-) \$\endgroup\$ – dfhwze Aug 9 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.