Код 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());

 }
}

То, что делает вышеупомянутая программа, находит триплеты a1, a2, a3 из массива A, так что сумма триплетов равна 30.

Я хочу знать, как я могу сделать расчет суммы, используя расширение C # Parallel.For.

Я знаю, что это используется в качестве вопроса для собеседования, и существуют лучшие альтернативные алгоритмы, чем цикл i, j, k.Тем не менее, все, что я хочу, это просто понять, как выполнить это, используя параллельные расширения для C #, эффективным способом.

Answer 1

ответ Дана будет работать и это правильный способ использования Parallel.For, но я столкнулся с проблемой профилирования кода, и я думаю, вы обнаружите, что распараллеливание этого не сделает его быстрее. Каждый Parellel.For создает несколько новых потоков, обычно более трех, поэтому при 3 вложенных Parellel.For с у вас будет не менее 3 ^ 3 (27) потоков, что намного больше, чем число логических процессоров на любой машине. Дополнительные потоки будут, если что-нибудь добавить, накладные расходы и замедлить их.

Так почему бы просто не иметь один Parallel.For и 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);
    }
}

Это дает следующие результаты для среднего времени выполнения для каждого метода: (в режиме Release, используя .Net 4.0, на четырехъядерном компьютере Intel Core i5):

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