Note that this problem is equivalent to finding the longest line segment defined by any two points in a collection of 3D coordinates, which may be an easier way to visualize the problem, and is almost certainly a version that has received more research.

Essentially, given a List<Color> and this method...

public static int ColorDiff(Color a, Color b)
{
    int rDiff = a.R - b.R;
    int gDiff = a.G - b.G;
    int bDiff = a.B - b.B;
    return (int)Math.Sqrt(rDiff * rDiff + gDiff * gDiff + bDiff * bDiff);
}

... I'd like to get the highest ColorDiff value for any pair of points in the list.

Informed Sequential Approach

int max = 0;
for (int i = 0; i < colors.Count - 1; i++)
{
    for (int j = i + 1; j < colors.Count; j++)
    {
        int temp = ColorDiff(colors[i], colors[j]);
        if (temp > max)
            max = temp;
    }
}

Naive LINQ Parallel Approach

int max = colors.AsParallel().Max(a => colors.Max(b => ColorDiff(a, b)));

Informed Parallel Approach

int max = 0;
Object locker = new Object();
System.Threading.Tasks.Parallel.For(0, colors.Count - 1, () => 0,
    (i, unused, localMax) =>
    {
        int temp = 0;
        for (int j = i + 1; j < colors.Count; j++)
            temp = Math.Max(temp, ColorDiff(colors[i], colors[j]));
        return Math.Max(localMax, temp);
    }, localMax =>
    {
        lock (locker)
        {
            if (localMax > max)
                max = localMax;
        }
    });

My testing indicates the naive LINQ approach takes about 60-70% of the time the sequential approach takes. However, I'm pretty sure it's naively doing the comparisons twice (ColorDiff(colors[i], colors[j]) and ColorDiff(colors[j], colors[i])), and that the speedup is entirely due to the parallelization across 4 cores. The performance of the informed parallel approach supports that; it takes approximately 30-40% of the time the LINQ approach takes, making it about 5 times faster than the informed sequential approach.

The LINQ approach is taking approximately 1 minute on my trial datasets (about 60 thousand elements in the list), and a little over 15 minutes on a larger dataset (230 thousand elements). I don't even want to know how long it will take on a full size dataset (about 1.1 million elements in the list).

Can I improve the brute force approach any further? Or better yet, is there an algorithm I can easily implement in C# that's better than O(n2)? A good approximation of the max value (within 5% of the true max) would probably be acceptable.

Extra information:

  1. Because these are colors rather than points, their R, G, and B values are guaranteed to be in the range 0 to 255. I don't know if knowing the area the points will be inside helps, though; the way the colors are generated results in them often being clustered in a small sub-space of the total range.

  2. Because of the way the colors are generated, every color will have N exact duplicates in the list (N >= 0, usually < 4). The value of N will be known at this point, but the ordering of the list must be preserved and is not guaranteed to keep duplicates near each other. A shallow copy of the list can be made and ordered if that helps (and is worth the extra CPU time & memory).

  • Using the RGB color space might not give you the most meaningful results. – 200_success Jun 1 '15 at 20:28
  • @200_success Can you suggest an alternative? I can apply the same algorithm to the HSB space but I'm not sure that offers any performance advantages (as well as needing additional balancing since those 3 values aren't all in the same range). – Oblivious Sage Jun 1 '15 at 20:31
  • @200_success That's... wow. It's awesome that someone did the research to find those formulas, but my algorithm is already painfully slow (hence this question) and making the part that gets repeated millions of times more expensive might not be the way to go. – Oblivious Sage Jun 1 '15 at 20:34
  • Any chance of sharing a dataset or some code that generates a representative sample? – RobH Jun 3 '15 at 7:47

Ramos (2001) gives a \$O(n \log n)\$ algorithm, but the paper is not freely available, and apparently the algorithm is very complex. So take a look instead at Malandain and Boissonnat (2004) who give a simple algorithm that is \$O(n^2)\$ in the worst case, but apparently performs well for distributions found in practice.

  • I found this link to be more useful as it includes their implementation, including the hybrid of their approach with Har-Peled's. According to the paper the hybrid approach was slightly slower in all cases but never exhibited pathological worst-case behavior the way their non-hybridized algorithm and Har-Peled's non-hybridized algorithm did. – Oblivious Sage Jun 2 '15 at 13:27

You don't actually need the square root until the end - it seems like that would save some time:

private int SumOfDifferences(Color a, Color b)
{
    int rDiff = a.R - b.R;
    int gDiff = a.G - b.G;
    int bDiff = a.B - b.B;
    return rDiff * rDiff + gDiff * gDiff + bDiff * bDiff;
}

Then to get your max:

double max = Math.Sqrt(
    colors
    .AsParallel()
    .Max(a => colors.Max(b => SumOfDifferences(a, b))));

It might speed it up a bit.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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