読者です 読者をやめる 読者になる 読者になる

CとJavaで書いてみた

C言語のお勉強がてらに「珠玉のプログラミング」に載っていた「渡された配列の中で和が最大になる部分配列を探索する」アルゴリズムを実装してみました。


例えば配列{31, -41, 59, 26, -53, 58, 97, -93, -23, 84}が渡された場合は、{59, 26, -53, 58, 97}の合計187が最大値となるので、この部分配列を抜き出すのが正解となります。


一応javaでも書いてみたのですが、10000の長さのint配列をランダム生成して実行してみると
java:100秒ぐらい
C :500秒ぐらい


Cのほうが早いと思ってんですが、なんかコンパイルオプションとかあるのかな。
それとも俺のCの書き方が悪いんだろうか、、、、、


もうちょっと調べてみる
以下コードです

Cで書いた場合

#include <stdio.h>
#include <time.h>
#include <sys/time.h>

double gettimeofday_sec()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

long runsort(int intsort[], int intsort_len)
{
        long max = 0;
        long sumtemp = 0;
	printf("intsort_len=%d\n", intsort_len); 
        int i;
        int j;
        int k;
        for(i = 0; i < intsort_len; i++) {
                for(j = i; j < intsort_len; j++) {
                        if(j == i) {
                                continue;
                        }
			sumtemp = 0;
                        for(k = i; k <= j; k++) {
                                sumtemp += intsort[k];
                        }
			/* printf("sumtemp=%d\n", sumtemp); */
                        max = max < sumtemp ? sumtemp : max;
			/* printf("max=%d\n", max); */

                }
                if(i % 100 == 0) {
                        printf("%d\n", i);
                }
        }
        return max;
}


int main (void)
{
	int array1[10000];
	int array1_len = sizeof(array1) / sizeof(array1[0]);
	printf("length=%d\n", array1_len);
	int i;
	double t1,t2;
	srand((unsigned)time(NULL));

	for(i = 0; i < array1_len; i++) {
		array1[i] = (int)rand() % 60000 - 30000;
		/* printf("random=%d\n", array1[i]); */
	}

	printf("start sorting....\n");
	t1 = gettimeofday_sec();
        long result = runsort(array1, array1_len);
	t2 = gettimeofday_sec();

        printf("result=%d, time=%10.30f\n", result, t2-t1);
	return 0;
}

Javaで書いた場合


import java.util.Random;

/**
 * Hello world!
 *
 */
public class App2 
{
    public static void main( String[] args )
    {
//    	int[] target = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84}; //187
    	int[] target = new int[10000];
    	for(int i = 0; i < target.length; i++) {
    		Random r = new Random();
    		target[i] = r.nextInt();
    	}
    	App2 app = new App2();
    	long starttime = System.currentTimeMillis();
    	long result = app.sort(target);
    	System.out.println(result + ":" + (System.currentTimeMillis() - starttime) + "ms");

    }
   
    //配列中の最大の二つの要素を足した数を返す
    private long sort(int[] intsort) {
    	long max = 0;
    	for(int i = 0; i < intsort.length; i++) {
    		for(int j = i; j < intsort.length; j++) {
    			if(j == i) {
    				continue;
    			}
    			long sumtemp = 0;
    			for(int k = i; k <= j; k++) {
    				sumtemp += intsort[k];
    			}
    			max = max < sumtemp ? sumtemp : max;
    		}
    	if(i % 100 == 0) {
    		System.out.println(i);
    	}
    	}
    	return max;
    }
}