2009-12-05

2分木を作ってみた

大学のTAで、2年生向けに二分木をCで実装する実験をした。
復習がてら、Javaで二分木を実装したので、載せてみる。

BinaryTree.java

public class BinaryTree<E extends Comparable<E>> {
  BinaryNode root;

  //生成
  public BinaryTree(){
    root=null;
  }

  //挿入
  public void insert(E t){
    if(root==null){
      root=new BinaryNode(t);
      return;
    }

    BinaryNode cur=root;
    BinaryNode parent=null;
    boolean isLeft=false;

    while(cur!=null){
      if(cur.e.compareTo(t)>0){
        isLeft=true;
        parent=cur;
        cur=cur.left;
      }else if(cur.e.compareTo(t)<0){
        isLeft=false;
        parent=cur;
        cur=cur.right;
      }else if(cur.e.compareTo(t)==0){
        System.out.println("This element has already exit!");
        return;
      }else{
        System.out.println("Error! exit this program");
        System.exit(1);
      }
    }
    cur=new BinaryNode(parent,t);
    if(isLeft)
      parent.left=cur;
    else
      parent.right=cur;
  }

  //検索
  public BinaryNode search(E t){
    BinaryNode cur=root;

    while(cur!=null){
      if(cur.e.compareTo(t)==0)
        break;

      else if(cur.e.compareTo(t)>0)
        cur=cur.left;
      else if(cur.e.compareTo(t)<0)
        cur=cur.right;

      else{
        System.out.println("This Element don't exit");
        cur=null;
      }
    }
    return cur;
  }

  //要素を削除
  public void remove(E t){
    BinaryNode cur=search(t);
    BinaryNode parent=cur.parent;
    if(cur!=null){
      //子を持たない時
      if(cur.left==null && cur.right==null){
        if(cur.e.compareTo(parent.e)>0)
          parent.left=null;
        else
          parent.right=null;
      }

      //子を1つしか持たない時
      else if(cur.left==null){
        if(cur.e.compareTo(parent.e)>0){
          parent.left=cur.right;
        }else{
          parent.right=cur.right;
        }
        cur.right.parent=parent;
      }else if(cur.right==null){
        if(cur.e.compareTo(parent.e)>0){
          parent.left=cur.left;
        }else{
          parent.right=cur.left;
        }
        cur.left.parent=parent;
      }

      //子を2つもつ時
      else{
        int l=getDepth(cur.left);
        int r=getDepth(cur.right);
        if(l>r){
          BinaryNode max=removeMax(cur.left);
          if(parent.e.compareTo(max.e)>0)
            parent.left=max;
          else
            parent.right=max;
        }else{
          BinaryNode min=removeMin(cur.right);
          if(parent.e.compareTo(min.e)>0)
            parent.left=min;
          else
            parent.right=min;
        }
      }
    }
  }

  //最大の要素を削除する
  public BinaryNode removeMax(BinaryNode cur){
    BinaryNode parent=cur.parent;
    while(cur!=null){
      parent=cur;
      cur=cur.right;
    }
    parent.parent.right=null;
    return parent;
  }

  //最小の要素を削除する
  public BinaryNode removeMin(BinaryNode cur){
    BinaryNode parent=cur.parent;
    while(cur!=null){
      parent=cur;
      cur=cur.left;
    }
    parent.parent.left=null;
    return parent;
  }

  //ノードから深さを取得する
  public int getDepth(BinaryNode cur){
    if(cur==null)
      return -1;

    int l,r;
    l=r=0;
    l=getDepth(cur.left)+1;
    r=getDepth(cur.right)+1;

    return (l>r)?l:r;
  }
  
  //木の要素を表示する
  public String toString(){
    return ""+root;
  }
}

BinaryNode.java

public class BinaryNode<E extends Comparable<E>> {

  BinaryNode parent;
  BinaryNode left,right;
  E e;

  public BinaryNode(E t){
    parent=null;
    left=right=null;
    e=t;
  }

  public BinaryNode(BinaryNode parent,E t){
    this.parent=parent;
    e=t;
  }
  
  public String toString(){
    String sl=(left!=null)?"  "+left+"\n":"";
    String sr=(right!=null)?"  "+right+"\n":"";
    return "  "+e+"\n"+sl+""+sr;
      //return ""+e+"\n"+((left!=null)?"  "+left+"\n":"")+""+((right!=null)?"  "+right+"\n":"");
  }
}

削除と追加を適当に実装したので、また後で改良してみる。

2009-08-06

n次元球面上への一様分布-続

コンピュータ・IT

前回に引き続き、
n次元球面上への一様分布の改良を行ってみた

/*
**  Sphere.java  -  n次元球面への一様分布を行う
*/

public class Sphere{

  //n次元球面上に一様分布な入力を作成する
  public VectorND makeRandom(int dim){
    if(dim<2) return null;

    VectorND x=new VectorND(dim);

    if(dim==2)  x=make1D();
    else if(dim==3) x=make2D();
    else x=makeND(dim);
    
    return x;
  }

  //2次元球面上への一様分布 - 1次元分布
  public VectorND make1D(){
    VectorND x=new VectorND(2);
    double phi=Math.random()*Math.PI*2;
    x.e[0]=Math.sin(phi);
    x.e[1]=Math.cos(phi);
    
    return x;
  }

  //3次元球面上への一様分布 - 2次元分布
  public VectorND make2D(){
    VectorND x=new VectorND(3);
    double theta=Math.random()*2-1;
    double phi=Math.random()*Math.PI*2;
    x.e[0]=theta;
    x.e[1]=Math.sqrt(1-(theta*theta))*Math.sin(phi);
    x.e[2]=Math.sqrt(1-(theta*theta))*Math.cos(phi);
    
    return x;
  }

  //N次元球面上への一様分布 - n-1次元分布
  public VectorND makeND(int dim){
    VectorND x=new VectorND(dim);
    VectorND v;
    double phi=Math.random()*Math.PI*2;
    double theta=Math.random();
    
    v=makeRandom(dim-2);
    for(int i=0;i<dim-2;i++)
      x.e[i]=v.e[i]*Math.pow(theta,1/(double)(dim-2));
    x.e[dim-2]=Math.sqrt(1-Math.pow(theta,2/(double)(dim-2)))*Math.sin(phi);
    x.e[dim-1]=Math.sqrt(1-Math.pow(theta,2/(double)(dim-2)))*Math.cos(phi);
    
    return x;
  }

  //テスト用のメイン
  public static void main(String[] args){
    int num=1000;
    int dim=10;
    Sphere sp=new Sphere();

    for(int i=0;i<num;i++){
      VectorND x=sp.makeRandom(dim);
      System.out.println("["+i+"]="+x.norm());
    }
  }
}

実行してみた感じでは、ちゃんと上手く動いてると思う。*1

*1:参考になりました。http://d.hatena.ne.jp/waman/20090515/1242351513

2009-08-04

n次元球面への一様分布入力

コンピュータ・IT

ここを参考にn次元球面への一様分布入力を行うプログラムを作ってみた。

/*
**  Sphere.java  -  n次元球面への一様分布を行う
*/

import java.util.*;

public class Sphere{
  
  //n次元球面上に一様分布な入力を作成する
  public VectorND makeRandom(int d){
    int dim=d-1;
    VectorND x;
    if(dim%2==0)  x=evenSphere(dim);
    else  x=oddSphere(dim);

    return x;
  }

  //奇数次元球面の場合
  public VectorND oddSphere(int dim){
    int m=(dim+1)/2;
    VectorND x;
    if(m<2){
      x=new VectorND(2);
      double phi=Math.random()*2*Math.PI;
      x.e[0]=Math.sin(phi);
      x.e[1]=Math.cos(phi);
    }else{
      double theta=Math.random();
      double phi=Math.random()*2*Math.PI;
      x=new VectorND(2*m);
      VectorND v=oddSphere(2*m-3);
      for(int i=0;i<2*m-2;i++)
        x.e[i]=v.e[i]*Math.sqrt(Math.pow(theta,1/(double)(m-1)));
      x.e[2*m-2]=Math.sqrt(1-Math.pow(theta,1/(double)(m-1)))*Math.sin(phi);
      x.e[2*m-1]=Math.sqrt(1-Math.pow(theta,1/(double)(m-1)))*Math.cos(phi);
    }
      return x;
  }


  //偶数次元の球面の場合
  public VectorND evenSphere(int dim){
    int m=dim/2;
    VectorND x;
    if(m<2){
      double theta=Math.random()*2-1;
      double phi=Math.random()*2*Math.PI;
      x=new VectorND(3);
      x.e[0]=theta;
      x.e[1]=Math.sqrt(1-theta*theta)*Math.sin(phi);
      x.e[2]=Math.sqrt(1-theta*theta)*Math.cos(phi);
    }else{
      double theta=Math.random();
      double phi=Math.random()*2*Math.PI;
      x=new VectorND(2*m+1);
      VectorND v=evenSphere(2*m-2);
      for(int i=0;i<2*m-2;i++)
        x.e[i]=v.e[i]*Math.pow(theta,1/(double)(2*m-1));
      x.e[2*m-1]=Math.sqrt(1-Math.pow(theta,2/(double)(2*m-1)))*Math.sin(phi);
      x.e[2*m]=Math.sqrt(1-Math.pow(theta,2/(double)(2*m-1)))*Math.cos(phi);
    }
    return x;
  }

  //メイン
  public static void main(String[] args){
    int n=1000;
    int dim=3;
    Sphere sp=new Sphere();

    for(int j=0;j<n;j++){
      VectorND x=sp.makeRandom(dim);
      for(int i=0;i<x.e.length;i++)
        System.out.print(x.e[i]+" ");
      System.out.println();
    }
  }
}

」

これでOK！かと思ったら、
改・一般次元での単位球体内・球面上の一様分布
がありました。実装しなおそう

2009-06-05

BackPropagationを実装してみた

コンピュータ・IT

講義でBackPropagationを実装したので、メモとして。*1
入力は2ビットで排他的論理輪を学習するというもの。
中間層は2つのニューロンで、学習係数は0.1、慣性係数は0.01で実装した。
BackPropagation.jar
以下が結果になる。

大体10万回ぐらいで収束。

*1:参考
バックプロパゲーション入門

2009-05-10

講演会「ソフトウェアエンジニアの心得」に参加してみました

コンピュータ・IT

講演者は柴田芳樹さんで、会場には学生っぽい人が結構いました。
話としては、コーディングする時の注意点や、エンジニアとして働く上で大切なことについて話をしました。
こんな講演行ったことなかったので、どんな堅い内容になるんだろうと思ってましたが、
意外と技術的な話ではなく、心構えのような話が多かったです。
話に出た中で