c# - 为什么这个算法在 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 很慢。算法不是这样吗？

---

修正后的表现:

• Ruby(非并行):14.62s
• C#(非并行):2.22s
• C#(使用 TPL):0.64 秒

Answer 1

其实这个bug很微妙，和线程无关。您的 C# 版本需要这么长时间的原因是 collat​​z 方法计算的中间值最终开始溢出 int 类型，导致负数可能需要很长时间收敛。

这首先发生在 i 为 134,379 时，第 129 个^th 项(假设从一开始计数)为 2,482,111,348。这超过了最大值 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。