c# - C# 中的并行.For

Question

我正在尝试转换以下 Collat​​z 猜想算法:

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

我有一种感觉，我离它不远了，著名的遗言。

提前致谢。

Answer 1

你的问题是你不想在这种情况下使用 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 编译它也使它的速度快了一倍以上。