Parallel.For в C # - PullRequest
Новая
       8

Parallel.For в C #

5 голосов
/ 21 декабря 2010

Я пытаюсь преобразовать следующий алгоритм гипотезы Коллатца из: 

 public class CollatzConjexture
    {
        public static int Calculate(int StartIndex, int MaxSequence)
        {
            int ChainLength = 0;
            int key = 0;
            bool ContinuteCalulating = true;
            int LongestChain = 0;
            Int64 Remainder = 0;

            for (int i = StartIndex; i <= MaxSequence; i++)
            {
                ChainLength = 1;
                Remainder = i;
                ContinuteCalulating = true;

                while (ContinuteCalulating)
                {
                    Remainder = CalculateCollatzConjecture(Remainder);
                    if (Remainder == 1)
                        ContinuteCalulating = false;

                    ChainLength += 1;
                }

                if (ChainLength > LongestChain)
                {
                    LongestChain = ChainLength;
                    key = i;
                }
            }

            return key;
        }

        private static Int64 CalculateCollatzConjecture(Int64 Number)
        {
            if (Number % 2 == 0)
                return Number / 2;
            else
                return (3 * Number) + 1;
        }
    }

Вместо использования .NET 4.0 Parallel.For: 

int ChainLength = 0;
            int key = 0;
            bool ContinuteCalulating = true;
            int LongestChain = 0;
            Int64 Remainder = 0;

            int[] nums = Enumerable.Range(1, 1500000).ToArray();
            long total = 0;

            // Use type parameter to make subtotal a long, not an int
            Parallel.For<int>(1, nums.Length, () => 1, (j, loop, subtotal) =>
            {
                Remainder = j;

                while (ContinuteCalulating)
                {
                    Remainder = CalculateCollatzConjecture(Remainder);
                    if (Remainder == 1)
                        ContinuteCalulating = false;

                    ChainLength += 1;
                }

                if (ChainLength > LongestChain)
                {
                    LongestChain = ChainLength;
                    key = j;
                }
                return key;


            },
                (x) => Interlocked.Add(ref key, x)
            );

У меня такое чувствоне слишком далеко от него, знаменитые последние слова.

Заранее спасибо.

1 Ответ

9 голосов
/ 21 декабря 2010

Ваша проблема в том, что вы не хотите использовать Parallel.For в этом случае, потому что у вас уже есть массив (nums) для перебора, который требует Parallel.ForEach. Тем не менее, ваш массив создается с помощью Enumerable.Range, и вы фактически не используете его ни для чего, поэтому лучший способ сделать это с помощью AsParallel и LINQ (PLINQ): 

public static class CollatzConjexture2
{
    public static int Calculate(int StartIndex, int MaxSequence)
    {
        var nums = Enumerable.Range(StartIndex, MaxSequence);
        return nums.AsParallel()
                    // compute length of chain for each number
                   .Select(n => new { key = n, len = CollatzChainLength(n) })
                    // find longest chain
                   .Aggregate((max, cur) => cur.len > max.len ||
                    // make sure we have lowest key for longest chain
                      max.len == cur.len && cur.key < max.key ? cur : max)
                    // get number that produced longest chain
                   .key;
    }

    private static int CollatzChainLength(Int64 Number)
    {
        int chainLength;
        for (chainLength = 1; Number != 1; chainLength++)
            Number = (Number & 1) == 0 ? Number >> 1 : Number * 3 + 1;
        return chainLength;
    }
}

Этот метод примерно в два раза быстрее на моем компьютере, чем последовательная реализация. Также обратите внимание, что я оптимизировал основной цикл так, чтобы он выполнял вычисления внутри строки, а не вызывал функцию, и использовал битовую математику вместо умножения и деления. Это сделало это примерно в два раза быстрее. Компиляция для x64 вместо x86 также сделала это более чем в два раза быстрее.

...