Entry

プログラミング・メモ - Java プログラマもスタックサイズには要注意の巻

2008年12月15日

この前ちょっと書いた最大値を求める話で,とむよんさんのこちらのコードから(インデント変えてます)。

public class Moge {

  public static void main(String[] args) {
    int[] a = {1,5,2,3,6,4};
    System.out.println(Moge.max(a)); //output '6'
  }

  public static int max(int[] a){
    return Moge._max(a, 0, a[0]);
  }

  private static int _max(int[] a, int ind, int max){
    if(a.length-1 == ind) return max;
    return Moge._max(a, ind+1, Math.max(a[ind], a[ind+1]));
  }
}

あまりスマートでは無いですが。。

codeなにがし::最大値の取得(java)

再帰を使う方法。スタックに積むのにオーバーヘッドがかかるんですけれど,ソートよりはずっと性能はいいはず。最大値ひとつ見つけるのに,O(N**2) (あるいは O(Nlog(N)))ってねぇ……(←しつこい)。

再帰を使う方法は,見た目がスマートなもんでウケる人にはウケるんですけれど,ひとつ気をつけなくちゃいけないのが,スタックサイズです。for-文でクルクルやる時は,int をインデックスにすると,2^31-1まで数えられるけど,通常,スタックサイズはこれよりずっと小さい。

つことで試してみた。

public class Moge {
  public static void main(String[] args) {
    int[] a = {
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6
      };
    System.out.println(Moge.max(a)); //output '9'
  }
  
  public static int max(int[] a){
    return Moge._max(a, 0, a[0]);
  }
  
  private static int _max(int[] a, int ind, int max){
    if(a.length-1 == ind) return max;
    return Moge._max(a, ind+1, Math.max(a[ind], a[ind+1]));
  }
}

普通にコンパイルできます。ただ,実行すると,

Exception in thread "main" java.lang.StackOverflowError
    at Moge._max(Moge.java:230)
    at Moge._max(Moge.java:230)
    at Moge._max(Moge.java:230)
    at Moge._max(Moge.java:230)
    at Moge._max(Moge.java:230)
    at Moge._max(Moge.java:230)
    at Moge._max(Moge.java:230)
    at Moge._max(Moge.java:230)
    :

スタックを使い果たして死んでしまいます。Java で StackOverflowError が出るところって見たことなかったんですけど,やっぱ出るときゃ出るんですね(何言ってんだか)。

もちろん,こっちだと普通に動きます(配列の部分は省略)。当たり前ですが。多分,StackOverflowError が出ない大きさの配列の場合であっても,こっちの方がスタックに積まない分だけ若干速い。C/C++ なら,ポインタを使ってもっと速くできる。ま,そんなに速くすることもないんですが。

public class Moge {
  public static void main(String[] args) {
    int[] a = {
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,4,9,3,9,4,1,5,2,3,6,
      :
      };
    int max = a[0];
    for (int i = 0; i < a.length; i++) {
      max = (max < a[i]) ? a[i] : max;
    }
    System.out.println(max); //output '9'
  }
}

codeなにがしのお題では,配列の大きさが明示されていなかったので(「多量」らしい),スタックサイズが十分にあると想定するのは危険なのかも。と,外野でゴニョゴニョ。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN