为什么Ruby中的这个算法运行得比Parallel'd C#快？

Question

以下ruby代码在〜15秒内运行.它几乎不使用任何CPU /内存(约占一个CPU的25%):

def collatz(num)
   num.even? ? num/2 : 3*num + 1
end

start_time = Time.now
max_chain_count = 0
max_starter_num = 0
(1..1000000).each do |i|
    count = 0
    current = i
    current = collatz(current) and count += 1 until (current == 1)
    max_chain_count = count and max_starter_num = i if (count > max_chain_count)
end

puts "Max starter num: #{max_starter_num} -> chain of #{max_chain_count} elements. Found in: #{Time.now - start_time}s"

以下TPL C#将我的所有4个内核的使用率提高到100%,并且比ruby版本慢了几个数量级:

static void Euler14Test()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    int max_chain_count = 0;
    int max_starter_num = 0;
    object locker = new object();
    Parallel.For(1, 1000000, i =>
    {
        int count = 0;
        int current = i;
        while (current != 1)
        {
            current = collatz(current);
            count++;
        }
        if (count > max_chain_count)
        {
            lock (locker)
            {
                max_chain_count = count;
                max_starter_num = i;
            }
        }
        if (i % 1000 == 0)
            Console.WriteLine(i);
    });
    sw.Stop();
    Console.WriteLine("Max starter i: {0} -> chain of {1} elements. Found in: {2}s", max_starter_num, max_chain_count, sw.Elapsed.ToString());
}

static int collatz(int num)
{
    return num % 2 == 0 ? num / 2 : 3 * num + 1;
}

为什么ruby比C#运行得更快？我被告知Ruby很慢.在算法方面,这不是真的吗？

---

Perf AFTER校正:

• Ruby(非并行):14.62s
• C#(非并行):2.22s
• C#(With TPL):0.64s

Answer 1

实际上,这个bug非常微妙,与线程无关.你的C#版本需要这么长时间的原因是该collatz方法计算的中间值最终会开始溢出该int类型,导致负数可能需要很长时间才能收敛.

该第一发生时i是134379,为此,129 ^次术语(假设为基础的一个计数)是2482111348.这超过了最大值2,147,483,647,因此存储为-1,812,855,948.

要在C#版本上获得良好的性能(和正确的结果),只需更改:

int current = i;

…至:

long current = i;

…和:

static int collatz(int num)

…至:

static long collatz(long num)

这将使你的表现降低到可观的1.5秒.

编辑:在调试面向数学的应用程序时,CodesInChaos提出了一个关于启用溢出检查的非常有效的观点.这样做可以立即识别错误,因为运行时会抛出错误OverflowException.

Answer 2

应该:

Parallel.For(1L, 1000000L, i =>
    {

否则,您有整数溢出并开始检查负值.相同的collatz方法应该使用长值.