Archive

For the Java category

Ubuntu10.10 – Java, Flex4 SDK インストール –

No Comments

UbuntuにJavaとFlex4SDKをインストールする

Javaのインストール

インストール

SunのJDKをインストールしたい
デフォだとリストにないので、追加する

sudo vim /etc/apt/sources.list

として

## Uncomment the following two lines to add software from Canonical's
## 'partner' repository.
## This software is not part of Ubuntu, but is offered by Canonical and the
## respective vendors as a service to Ubuntu users.
# deb http://archive.canonical.com/ubuntu maverick partner
# deb-src http://archive.canonical.com/ubuntu maverick partner

# deb http://archive.canonical.com/ubuntu maverick partner
# deb-src http://archive.canonical.com/ubuntu maverick partner

この二つのコメントアウトを外す

一回updateして

sudo apt-get update

インストール

sudo apt-get install sun-java6-jdk

確認

試しに実行してみる

適当なとこでMain.javaを作る

public class Main{
        public static void main(String args[]){
                System.out.println("hoge");
        }

}

Main.java

書いたら、コンパイル

javac Main.java

Main.classができたら、実行

java Main
hoge

と出たらおk

Flex4 SDKのインストール

(参考:How to install and set up Adobe Flex SDK on Ubuntu linux « SteveLove.org)
how to に忠実にやってみます

インストール

ここらへんからzipを落としてくる
Download Flex 4 – Flex SDK – Adobe Open Source
Flex用のディレクトリを用意する

sudo mkdir /opt/flex

解凍

unzip flex_sdk_4.zip -d tempflex

解凍したものをさっき作ったディレクトリに移動する

sudo mv tempflex/* /opt/flex/

移動して確認

cd /opt/flex
ls

ちゃんとできてたら、次はパスを通す

vim ~/.bashrc

一番下に、以下を追加して保存

export PATH=/opt/flex/bin:$PATH

一回ターミナルを終了して、もっかい入りなおしてからパス通ってるか確認

mxmlc -help

こんなん出てきたらおk

Adobe Flex Compiler (mxmlc)
Version 4.1.0 build 16076
Copyright (c) 2004-2009 Adobe Systems, Inc. All rights reserved.
...
...

確認

試しに実行してみる
Main.asを書く

package {

	import flash.display.Sprite;

	public class Main extends Sprite {

		public function Main():void {
			graphics.beginFill(0xff0000);
			graphics.drawCircle(100, 100, 100);
			graphics.endFill();
		}	
	}	
}

コンパイル

mxmlc Main.as

Main.swfができてるはず
ウェブサーバー立ててたらこれを公開ディレクトリに置いたりしてブラウザから見れたらおk

素数を求める~エラトステネスの篩 2~

No Comments

前回の[アルゴリズム]素数を求める~エラトステネスの篩~の改良版を作ってみた

前回作ったものは何も考えずにwikipediaさんに言われた通りそのままにやったのでやっぱり効率が悪かった。
しかも、ある数が素数かどうか調べるためにまたリストを走査しなきゃいけなかった。これは明らかに欠陥w

ってことでboolean配列にして添字の数が素数ならtrueとするようにした
こうするのが本当なんですよねきっとw


final int MAX = 1000000 + 1;
boolean[] primes = new boolean[MAX];
primes[2] = true;
for (int i = 3; i < MAX; i += 2) {
    primes[i] = true;
}
for (int i = 3; i * i < MAX; i += 2) {
    if (primes[i]) {
        for (int j = i * 2; j < MAX; j += i) {
            primes[j] = false;
       }
   }
}

やってることは前回と同じ
効率化のために2の倍数は最初から除外するようにした

前回のソースと今回のソースでどれだけ速度が違うかテストしてみました
100万までの素数を求めるまでの時間を計測
前回のと今回のを交互に実行、それぞれ合計11回繰り返し、一番遅かったものを除外
計10回の平均をとりました
これだけ繰り返してるとメモリの確保に時間がかかって大きな誤差が生まれるので
オブジェクト生成の時間は含めないことにしました

Test.java


import java.util.Iterator;
import java.util.LinkedList;
public class Test {
 public static void main(String[] args) {
  final int N = 10;
  long sum = 0, sum2 = 0;
  long time;
  long m = 0, m2 = 0;
  final int MAX = 1000000;
  System.out.println("t前回t改良版");
  for (int i = 1; i <= N+1; i++) {
   System.out.print(i + "回目t");
   System.out.print(time = eratosthenes(MAX));
   m = Math.max(m, time);
   sum += time;
   System.out.print("t");
   System.out.println(time = eratosthenes2(MAX));
   m2 = Math.max(m2, time);
   sum2 += time;
  }
  System.out.println("-------------------------");
  System.out.println("平均t" + (sum-m)/N + "t" + (sum2-m2)/N);
 }
 static long eratosthenes(int max) {
  LinkedList primes = new LinkedList();
  LinkedList numbers = new LinkedList();
  long time = System.currentTimeMillis();
  for (int i = 2; i <= max; i++) {
   numbers.add(i);
  }
  int prime;
  Iterator it;
  do {
   prime = numbers.getFirst();
   primes.add(prime);
   it = numbers.iterator();
   while (it.hasNext()) {
    if (it.next() % prime == 0)
     it.remove();
   }
  } while (numbers.getLast() > prime * prime);
  it = numbers.iterator();
  while (it.hasNext()) {
   primes.add(it.next());
  }
  return System.currentTimeMillis() - time;
 }
 static long eratosthenes2(int max) {
  int _max = max + 1;
  boolean[] primes = new boolean[_max];
  long time = System.currentTimeMillis();
  primes[2] = true;
  for (int i = 3; i < _max; i += 2) {
   primes[i] = true;
  }
  for (int i = 3; i * i < _max; i += 2) {
   if (primes[i]) {
    for (int j = i * 2; j < _max; j += i) {
     primes[j] = false;
    }
   }
  }
  return System.currentTimeMillis() - time;
 }
}

出力結果

前回	改良版
1回目	6309	20
2回目	6169	10
3回目	6209	10
4回目	6329	10
5回目	6349	10
6回目	6299	20
7回目	6339	10
8回目	6279	10
9回目	6299	20
10回目	6360	10
11回目	6449	10
-------------------------
平均	6294	12

違いすぎるw
前回のが効率悪すぎただけですねすいませんw

素数を求める~エラトステネスの篩~

No Comments

エラトステネスの篩(エラトステネスのふるい)は素数判定法の一種で、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。 ※Wikipediaより

Wikipediaさんを参考にエラトステネスの篩で素数を求めるプログラムを作ってみようと思います

まず手順 Wikipediaさんのそのままですが・・・w

1
整数を最初の素数である 2 から昇順で探索リストに羅列する。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2
リストの先頭の数を素数リストに記録する。
素数リスト:2
探索リスト:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

3
前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する。
素数リスト:2
探索リスト:3 5 7 9 11 13 15 17 19

4
探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。探索リストの最大値が素数リストの最大値の平方よりも大きい場合、ステップ 2 に戻る。
19 は 2 の平方よりも大きいので、ステップ 2 に戻る。
2
素数リスト:2 3
探索リスト:3 5 7 9 11 13 15 17 19
3
素数リスト:2 3
探索リスト:5 7 11 13 17 19
4
19 は 3 の平方よりも大きいので、ステップ 2 に戻る。
2
素数リスト:2 3 5
探索リスト:5 7 11 13 17 19
3
素数リスト:2 3 5
探索リスト:7 11 13 17 19
4
19 は 5 の平方よりも小さいので、リストに残っている数が素数である。
結果:2 から 20 までの数に含まれる素数は、
2 3 5 7 11 13 17 19

この手順の通りにJavaで書いてみた



import java.util.Iterator;
import java.util.LinkedList;
public class Eratosthenes {
	static LinkedList primes = new LinkedList(); //素数リスト
	static LinkedList numbers = new LinkedList(); //探索リスト
	static int N = 100000; //Nまでの素数を求める
	public static void main(String[] args) {
		//1.整数を最初の素数である 2 から昇順で探索リストに羅列する。
		for(int i = 2; i <= N; i++){
			numbers.add(i);
		}
		int prime;
		Iterator it;
		do{
			//2.リストの先頭の数を素数リストに記録する
			prime = numbers.getFirst();
			primes.add(prime);
			//3.前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する
			it = numbers.iterator();
			while(it.hasNext()){
				if(it.next() % prime == 0)	it.remove();
			}
		//4.探索リストの最大値が素数リストの最大値の平方よりも大きい場合、ステップ 2 に戻る
		}while(numbers.getLast() > prime*prime);
		//4.探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる
		it = numbers.iterator();
		while(it.hasNext()){
			primes.add(it.next());
		}
	}
}

本当に手順そのまま書けたw
もうちょっと改善の余地がありそうだけど、手順通りのほうが理解しやすいしよほど効率が求められない限りこれで十分かな
覚えとこー

Blue Taste Theme created by Jabox