DouKaku? 5098 tosik: Compiler: GCC 3.4.4 ...(コラッツ・角谷の問題)

Comment detail

Compiler: GCC 3.4.4
OS: Cygwin on Windows XP Pro SP2
CPU: Intel Centrino 1GHz
Memory: 504MB
----------------------
>time ./collatz.exe
f(837799) = 524

real    0m0.530s
user    0m0.400s
sys     0m0.060s
----------------------
簡単なキャッシュを実装したら0.5秒と、思った以上に高速化できました。
答えが皆さんと同じなので安心。
C++なのにCっぽく書きましたが、可読性は若干犠牲になりますが、速度面でプラスになってると思います。

#include <stdio.h>

const int MAX = 1048577;
int cache[MAX];

int collatz(unsigned long long int n, int org_n = 0, int depth = 0)
{
    if ( MAX >= n )
    {
        if ( cache[n] != -1 )
        {
            cache[org_n] = cache[n] + depth;
            return cache[n] + depth;
        }
    }

    if ( n % 2 == 0 )
    {
        return collatz( n / 2, org_n, depth + 1 );
    }
    else if ( n == 1 )
    {
        cache[org_n] = depth;
        return depth;
    }
    else
    {
        return collatz( n * 3 + 1, org_n, depth + 1 );
    }
}


int main(void)
{
    for ( int i=0; i<MAX; i++ )
        cache[i] = -1;

    int max_n = 0;
    int max_steps = 0;

    for(unsigned long long int i=1; i<MAX; i++)
    {
        int steps = collatz(i,i);
        if ( max_steps < steps )
        {
            max_steps = steps;
            max_n = i;
        }
    }

    printf("f(%d) = %d\n", max_n, max_steps);
    return 0;
}

tosikさんの#5098をC#に移植してみました。
わずか421ミリ秒でした。.NETがこんなに速いとは驚きです。
コード全体を読まずに構文ごとにC#に書き換えて、最後に型の帳尻を合わせただけなのでtosikさんの意図に沿ったコードになっているか心配です。

    if ( MAX >= n )
    {
        if ( cache[n] != -1 )
        {
            cache[org_n] = cache[n] + depth;
            return cache[n] + depth;
        }
    }

の部分でnがcacheの配列の境界を越えてしまったので
if ( MAX >= n )
を
if ( MAX > n )
にしたけどいいのだろうか…。
C++の配列の宣言の添え字は配列長そのもので良かった…筈…。

OS:Windows XP Home SP2 
CPU:AMD Sempron 3400+ 1.99GHz 
メモリ:480MB

using System;
class Program {
    const int MAX = 1048577;
    static int[] cache = new int[MAX];

    static int collatz(ulong n) {
        return collatz(n, 0, 0);
    }
    static int collatz(ulong n, ulong org_n) {
        return collatz(n, org_n, 0);
    }
    static int collatz(ulong n, ulong org_n, int depth) {
        if(MAX > n) {
            if(cache[n] != -1) {
                cache[org_n] = cache[n] + depth;
                return cache[n] + depth;
            }
        }

        if(n % 2 == 0) {
            return collatz(n / 2, org_n, depth + 1);
        } else if(n == 1) {
            cache[org_n] = depth;
            return depth;
        } else {
            return collatz(n * 3 + 1, org_n, depth + 1);
        }
    }


    static void Main() {
        long tick = DateTime.Now.Ticks;
        for(int i = 0; i < MAX; i++)
            cache[i] = -1;

        ulong max_n = 0;
        int max_steps = 0;

        for(ulong i = 1; i < MAX; i++) {
            int steps = collatz(i, i);
            if(max_steps < steps) {
                max_steps = steps;
                max_n = i;
            }
        }

        Console.WriteLine("f(" + max_n + ")=" + max_steps);
        Console.WriteLine((DateTime.Now.Ticks - tick) / 10000L + "ms");
        Console.ReadLine();
    }
}

移植ありがとうございます。
C++の添え字は長さです。これは僕のミスでした。
2^20までは偶然MAX==nになることはないので、正しく動作してましたが、n>2^20の場合は実行時にエラーがでることがあるでしょうね。
このミスは、はじめにMAX=2^20にしていたときのもので、今のMAX=2^20+1に直したときに修正を忘れたものです。

ちなみにですが、このコードを書くときにひとつのバグにてこずりました。
それは全て int 型にしていたことが原因で、オーバーフローでマイナス値を出していたのが原因でした。
# 不慣れなgdbを使って挑戦したのでなかなか解明できなかった＾＾；

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq