ParallelFor code for finding sum of few elements in an array (Subsetsum problem)

Question

I have the following C# code fragment:

using System;

class count {
 public static void Main()
 {
  int [] a = {-30, 30, -20, -10, 40, 0, 10, 5};
  int i,j,k;
  int N=8;

  for (i=0; i < N; ++i)
   for (j=i+1; j < N; ++j)
    for (k=j+1; k < N; ++k)
     if (a[i] + a[j] + a[k] == 30)
      Console.WriteLine (a[i].ToString () + a[j].ToString() + a[k].ToString());

 }
}

What the above program does is, find out the triplets a1, a2, a3 from an Array A, such that the sum of the triplets is 30.

I want to know how I can do the sum calculation using the C# Parallel.For extension.

I know that this is used as an interview question and there are better alternative algorithms than an i,j,k loop. However, all I want is just to understand how to perform this using Parallel extensions for C# , in an effective way.

Answer 1

dan's answer will work and is a correct way to use Parallel.For, but I went through the trouble of profiling the code and I think you'll find that parallelising this won't make it any faster. Each Parellel.For makes several new threads, usually more than three, so with 3 nested Parellel.Fors you will have have at least 3^3 (27) threads, which is more way more than the number of logical processors on any machine. The extra threads will if anything add an overhead and slow it down.

So why not just have one Parallel.For and 2 ordinary for loops - this will mean that there are around 3-4 threads which will work great on a dual or quad core machine. Like this method:

static void Test2(int[] a)
{
    int N = a.Length;
    int total = 0;
    Object locker = new object();

    Parallel.For(0, N, i => 
    {
       for (int j = i + 1; j < N; ++j)
            for (int k = j + 1; k < N; ++k)
                if (a[i] + a[j] + a[k] == 30)
                    lock(locker)
                        total++; 
    });
}

Take the following code used to profile both methods:

class Program
{
    static void Main(string[] args)
    {
        Random r = new Random();
        int[] arr = new int[100];
        arr = arr.Select(i => r.Next(-30, 30)).ToArray();            

        Profile(Test0, arr, 20);
        Profile(Test1, arr, 20);
        Profile(Test2, arr, 20);

        Console.WriteLine("Test0: {0} ms", Profile(Test0, arr, 100).TotalMilliseconds);
        Console.WriteLine("Test1: {0} ms", Profile(Test1, arr, 100).TotalMilliseconds);
        Console.WriteLine("Test2: {0} ms", Profile(Test2, arr, 100).TotalMilliseconds);

        Console.ReadLine();
    }

    static void Test0(int[] a)
    {
        int N = a.Length;
        int total = 0;

        for (int i = 0; i < N; ++i)
            for (int j = i + 1; j < N; ++j)
                for (int k = j + 1; k < N; ++k)
                    if (a[i] + a[j] + a[k] == 30)
                        total++;
    }

    static void Test1(int[] a)
    {
        int N = a.Length;
        int total = 0;
        Object locker = new object();

        Parallel.For(0, N, i => Parallel.For(i+1, N, j => Parallel.For(j+1, N, k =>
        {
            if (a[i] + a[j] + a[k] == 30)
                lock(locker)
                    total++;
        })));
    }

    static void Test2(int[] a)
    {
        int N = a.Length;
        int total = 0;
        Object locker = new object();

        Parallel.For(0, N, i => 
        {
            for (int j = i + 1; j < N; ++j)
                for (int k = j + 1; k < N; ++k)
                    if (a[i] + a[j] + a[k] == 30)
                        lock(locker) 
                            total++;
        });
    }

    static TimeSpan Profile<T>(Action<T> action, T param, int repeats)
    {
        Stopwatch s = new Stopwatch();

        for (int i = 0; i < repeats; i++)
        {
            s.Start();
            action(param);
            s.Stop();
        }

        return new TimeSpan(s.ElapsedTicks/repeats);
    }
}

This yields these results for average execution time for each method: (in Release mode, using .Net 4.0, on a quad core Intel Core i5 machine):

Test0: 0.2544 ms
Test1: 3.3433 ms
Test2: 0.1391 ms