Geek Answers Handbook

Parallel code for finding the sum of several elements in an array (subnet problem)

I have the following C # code snippet:

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, figure out the triplets a1, a2, a3 from array A, so 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 a question for interviews, and there are better alternative algorithms than the i, j, k loop. However, all I want to do is just figure out how to do this using Parallel extensions for C # in an efficient way.

+4
source share
1 answer

dan answer will work, and this is the correct way to use Parallel.For , but I ran into the problem of profiling code, and I think you will find that parallelizing this will not make it faster. Each Parellel.For creates several new threads, usually more than three, so with 3 nested Parellel.For you will have at least 3 ^ 3 (27) threads, which is more than the number of logical processors on any machine. Additional threads will, if anything, add overhead and slow it down.

So, why not just have one Parallel.For and 2 regular for loops - this will mean that there are about 3-4 threads that work fine on a dual-core 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 gives these results for the average runtime for each method: (in Release mode, using .Net 4.0, on a quad-core Intel Core i5 processor):

 Test0: 0.2544 ms Test1: 3.3433 ms Test2: 0.1391 ms
+8
source

More articles:


All Articles