代码之家 › 专栏 › 技术社区 › Sankar

用于查找数组中几个元素之和的Parallelfor代码(子类问题)

mono loops data-structures algorithm c#

Sankar · 技术社区 · 14 年前

我有以下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.进行求和计算。

我知道这是一个面试问题,有比I,J,K循环更好的替代算法。但是,我只想了解如何有效地使用C的并行扩展来执行这个操作。

1 回复 | 直到 14 年前

Callum Rogers 14 年前

丹的答案是有效的,是正确的使用方法 Parallel.For 但是我在分析代码时遇到了麻烦,我想您会发现并行处理这不会使它更快。各 Parellel.For 生成多个新线程,通常超过三个,因此有三个嵌套线程 Parellel 你将拥有至少 3^3(27)个线程,这比任何计算机上的逻辑处理器数量都要多。额外的线程会增加开销并降低速度。

所以为什么不吃一个呢 平行的 2普通 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);
    }
}

这将为每个方法的平均执行时间生成以下结果:(在发布模式下,在四核Intel Core i5计算机上使用.NET 4.0):

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