15

次のrubyコードは約15秒で実行されます。CPU /メモリをほとんど使用しません（1つの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％使用し、ルビーバージョンよりも桁違いに遅くなります。

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

なぜルビーはC＃よりも速く実行されるのですか？Rubyは遅いと言われました。アルゴリズムに関してはそうではありませんか？

修正後のパフォーマンス：

  • Ruby（非並列）：14.62秒
  • C＃（非並列）：2.22秒
  • C＃（TPLあり）：0.64秒
4

3 に答える 3

30

実際、バグは非常に微妙で、スレッドとは何の関係もありません。C# バージョンが非常に長くかかる理由は、collatzメソッドによって計算された中間値が最終的に型をオーバーフローし始めint、その結果、負の数になり、収束に時間がかかる可能性があるためです。

これiは が 134,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 に答える