ParallelFor代码,用于查找数组中少数元素的总和(Subsetsum问题)

Question

我有以下C#代码片段:

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());

 }
}

上述程序的作用是从阵列A中找出三元组a1,a2,a3,使得三元组的总和为30.

我想知道如何使用C#Parallel.For扩展计算和计算.

我知道这被用作面试问题,并且有比i,j,k循环更好的替代算法.但是,我想要的只是了解如何使用C#的并行扩展以有效的方式执行此操作.

Answer 1

dan的答案将起作用并且是一种正确的使用方式Parallel.For,但我经历了分析代码的麻烦,我认为你会发现并行化并不会使它更快.每个都Parellel.For创建几个新线程,通常超过三个,所以使用3个嵌套Parellel.Fors,你将拥有至少 3 ^ 3(27)个线程,这比任何机器上的逻辑处理器数量更多.额外的线程将增加一个开销并减慢它.

那么为什么不只有一个Parallel.For和两个普通for循环 - 这意味着大约有3-4个线程可以在双核或四核机器上运行良好.喜欢这种方法:

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++; 
    });
}

使用以下用于分析两种方法的代码:

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);
    }
}

这为每种方法的平均执行时间产生了这些结果:(在发布模式下,使用.Net 4.0,在四核Intel Core i5机器上):

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