15

以下 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 秒
4

3 回答 3

30

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

这首先发生在i134,379 时，其中第 129项（假设从 1 开始计数）是 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.

溢出检查

溢出异常

于 2012-12-06T14:41:03.953 回答
6

应该：

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

否则，您有整数溢出并开始检查负值。相同的collatz方法应该对长值进行操作。

于 2012-12-06T14:41:19.027 回答
-1

我经历过类似的事情。我发现这是因为您的每个循环迭代都需要启动其他线程，这需要一些时间，在这种情况下，它与您在循环体中实际执行的操作相当（我认为它需要更多时间）。

有一个替代方案：您可以获得多少 CPU 内核，而不是使用具有相同数量迭代的并行循环，每个循环将评估您想要的实际循环的一部分，它是通过制作一个内部依赖于并行循环的 for 循环。

编辑：示例

int start = 1, end = 1000000;
Parallel.For(0, N_CORES, n =>
{
    int s = start + (end - start) * n / N_CORES;
    int e = n == N_CORES - 1 ? end : start + (end - start) * (n + 1) / N_CORES;
    for (int i = s; i < e; i++)
    {
        // Your code
    }
});

你应该试试这段代码，我很确定这会更快地完成这项工作。

编辑：说明

好吧，自从我回答这个问题以来已经很长时间了，但是我再次面对这个问题，终于明白了发生了什么。

我一直在使用 Parallel for 循环的 AForge 实现，看起来，它会为循环的每次迭代触发一个线程，所以，这就是为什么如果循环需要相对较少的时间来执行，你最终会得到一个低效的并行性。

所以，正如你们中的一些人所指出的，System.Threading.Tasks.Parallel 方法是基于任务的，这是一种更高级别的线程抽象：

“在幕后，任务排队到 ThreadPool，该线程池已通过确定和调整线程数量的算法得到增强，并提供负载平衡以最大限度地提高吞吐量。这使得任务相对轻量级，您可以创建许多任务以启用细粒度的并行性。”

所以，是的，如果你使用默认库的实现，你就不需要使用这种“伪造的”。

于 2012-12-06T14:39:40.213 回答