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