Блог

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

  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.Для :

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

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

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

Ваша проблема в том, что вы не хотите использовать 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 amp;amp; 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 amp; 1) == 0 ? Number >> 1 : Number * 3   1;
        return chainLength;
    }
}
  

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