Archive

For 6月, 2008

素数を求める~エラトステネスの篩 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

FLASH OOP for ActionScript 3.0

No Comments

もういっちょ紹介

FLASH OOP for ActionScript 3.0 FLASH OOP for ActionScript 3.0
(2008/07/03)
Flash OOP Japan

商品詳細を見る

こっちは7月3日発売
執筆者総勢16名の大作
めっちゃいろんなことが書かれてます
PV3とかFlashDevelopで開発とか・・・
ぜひ欲しいです
予約しとこうかな・・・・

Adobe AIRプロフェッショナルガイド Windows & Macintosh対応

No Comments
Adobe AIRプロフェッショナルガイド Windows & Macintosh対応 Adobe AIRプロフェッショナルガイド Windows & Macintosh対応
(2008/06/25)
クジラ飛行机

商品詳細を見る

6月25日発売
そろそろちゃんとAIRやらないとなーと思ってたのでちょっとほしい
著者はなでしこ開発者

本屋さんにあったら買おうw

フラクタル~樹木曲線~

No Comments

樹木曲線はフラクタルで木を再現したもので、コンピュータアートの分野では有名です
ある程度ランダムな要素を入れるとかなり現実の木に近くなります

※クリックでstart

This movie requires Flash Player 9

Line.as


package {
	import flash.display.Sprite;
	import flash.geom.Point;
	public class Line extends Sprite {
		public var startP:Point;
		public var endP:Point;
		public var distance:Number;
		public var angle:Number;
		function Line(startP:Point, endP:Point) {
			this.startP = startP;
			this.endP = endP;
			angle = Math.atan2(endP.y-startP.y, endP.x-startP.x);
			distance = Point.distance(startP, endP);
			graphics.lineStyle(0,0x000000);
			graphics.moveTo(startP.x, startP.y);
			graphics.lineTo(endP.x, endP.y);
			graphics.endFill();
		}
	}
}

TreeCurve.as


package {
	import flash.display.Sprite;
	import flash.events.MouseEvent;
	import flash.events.Event;
	import flash.geom.Point;
	public class TreeCurve extends Sprite {
		private var list:Array = [];
		private const W:int = 300;
		private const H:int = 300;
		private const RAD:Number = Math.PI/8;
		private const a:Number = 0.75;
		function TreeCurve() {
			var line:Line=new Line(new Point(W/2, H), new Point(W/2, H*4/5));
			list.push(line);
			stage.addChild(line);
			stage.addEventListener(MouseEvent.CLICK,onClick);
			function onClick(event:MouseEvent):void {
				stage.addEventListener(Event.ENTER_FRAME,onEnterFrameHandler);
				stage.removeEventListener(MouseEvent.CLICK,onClick);
			}
		}
		private function onEnterFrameHandler(event:Event):void {
			var line:Line=list[0];
			list.splice(0, 1);
			if (line.distance <= 8) {
				stage.removeEventListener(Event.ENTER_FRAME, onEnterFrameHandler);
				return;
			}
			var p:Point = new Point(line.endP.x + line.distance * a * Math.cos(line.angle + RAD), line.endP.y + line.distance * a * Math.sin(line.angle+RAD));
			var newLine:Line = new Line(line.endP, p);
			list.push(newLine);
			stage.addChild(newLine);
			p = new Point(line.endP.x + line.distance * a * Math.cos(line.angle - RAD), line.endP.y + line.distance * a * Math.sin(line.angle - RAD));
			newLine = new Line(line.endP, p);
			list.push(newLine);
			stage.addChild(newLine);
		}
	}
}

AIR1.1公開!その3

No Comments

AdobeAIR1.1についての記事です

CNET Japan 「Adobe AIR 1.1」公開、日本語に正式対応
@IT 日本語環境に対応した「Adobe AIR 1.1」登場
ITmedia 日本語に正式対応した「AIR 1.1」リリース
ITpro アドビシステムズが日本語環境に対応したAIR新版をリリース
IT-PLUS アドビ、日本語環境対応のAIRランタイム「Adobe AIR 1.1」を提供開始
マイコミジャーナル 日本語環境に正式対応した「Adobe AIR 1.1」がリリース

Adobe AIR Update Framework

No Comments

AIR1.1公開記念ついでにこっちも紹介

Adobe AIR Update FrameworkのBetaが公開されています

これはAIRアプリケーションのアップデート機能を簡単に実装できるようにしたフレームワークです
決められたフォーマットのXMLをサーバ側に置いておけば定期的にアップデートの有無を確認してくれ、アップデートがあれば直接インストールできます

詳しい説明はAdobe AIR Update Framework(英語)とakihiro kamijoさんとのころで

AIR1.1公開!その2

No Comments

さきほどは時間がなくて報告のみだったのでもうちょっと詳しい説明を。

AdobeAIR1.1のダウンロードは先ほどと同じ場所でダウンロードできます
最新バージョンのAdobe AIRをダウンロード

日本語を含む10言語を正式対応
詳しいことはakihiro kamijoさんのところが参考になります

本家での説明はAdobe AIR resourcesに書いてあります ※英語

自分が使っているAdobeFlashCS3をAIR1.1に対応させるにはInstalling Adobe Air 1.1 Update for Flash CS3 Professionalに書いてある手順で行えばいけます
英語の上にちょっとめんどうなのでさきほどのakihiro kamijoさんのところに日本語で詳しく書いてあるのでそっちのほうがいいかも FlexBuilder3、DreamweaverCS3のアップデート方法も書いてあります

FlexSDKはバージョン3.0.2からAIR1.1対応ですのでよくバージョンを確認してください

・400 以上のバグフィックスとメモリ利用の効率化
これはうれしいww

AIR1.1公開!

No Comments

AIR1.1が公開されました!!
http://get.adobe.com/air/?loc=jp
ここから入手できます

フラクタル~ドラゴン曲線~

No Comments

はいはいフラクタルフラクタル

今回はドラゴン曲線
ドラゴン曲線を考えた人はググっても出てきませんでしたw
できた形がドラゴンに似てるからドラゴン曲線らしいです
ドラゴンなのか・・・・?w

ドラゴン曲線を見てもらう前にちょっと説明

コッホ曲線もC曲線も線分を三角形にどんどん置き換えていくことでできあがるものでした
でも、線分の上側に三角形ができるのか下側にできるのかわからないんじゃ・・・?って思った人もいるはずです
そう、実はちゃんと向きがあるのです

こんな感じ
Koch&C Arrow

この規則にしたがって書いていくとコッホ曲線とC曲線ができあがります

さて、本題のドラゴン曲線ですが、実はC曲線とほぼ一緒です
ただ一箇所矢印の向きが違うだけなのです
doragon

たったこれだけで全く違うものになります
なので当然フラクタルも無限にあります
名前の付いているフラクタルは無限にあるフラクタルの内の数個でしかないのです
暇があれば自分でおもしろい形のフラクタルを探してみるのもいいかも・・・?w

繰り返しは10回
※クリックでstart

This movie requires Flash Player 9

ソースはほぼC曲線と同じです
どこが違うか探してみてくださいw

Line.as


package {
	import flash.display.Sprite;
	import flash.geom.Point;
	public class Line extends Sprite{
		public var startP:Point;
		public var endP:Point;
		public var distance:Number;
		public var angle:Number;
		function Line(startP:Point, endP:Point) {
			this.startP = startP;
			this.endP = endP;
			distance = Point.distance(startP, endP);
			angle = Math.atan2(endP.y-startP.y, endP.x-startP.x);

			graphics.lineStyle(0,0x000000);
			graphics.moveTo(startP.x, startP.y);
			graphics.lineTo(endP.x, endP.y);
			graphics.endFill();
		}
	}
}

DoragonCurve.as


package {
	import flash.display.Sprite;
	import flash.events.MouseEvent;
	import flash.events.Event;
	import flash.geom.Point;
	public class DoragonCurve extends Sprite {
		private var list:Array = [];
		private var endPoint:Point;
		private var count:int=0;
		private const N:int=10;
		private const W:int = 300;
		private const H:int = 300;
		function DoragonCurve() {
			var line:Line=new Line(new Point(W/4,H*2/3),new Point(W-W/4, H*2/3));
			endPoint=line.startP;
			list.push(line);
			stage.addChild(line);

			stage.addEventListener(MouseEvent.CLICK,onClick);
			function onClick(event:MouseEvent):void {
				stage.addEventListener(Event.ENTER_FRAME,onEnterFrameHandler);
				stage.removeEventListener(MouseEvent.CLICK,onClick);
			}

		}
		private function onEnterFrameHandler(event:Event):void {
			var line:Line=list[0];
			stage.removeChild(line);
			list.splice(0, 1);

			var p1:Point=new Point();
			p1.x= line.distance/2 * Math.SQRT2 * Math.cos(line.angle-Math.PI/4) + line.startP.x;
			p1.y= line.distance/2 * Math.SQRT2 * Math.sin(line.angle-Math.PI/4) + line.startP.y;

			newLine=new Line(line.endP,p1);
			stage.addChild(newLine);
			list.push(newLine);
			var newLine:Line=new Line(line.startP,p1);
			stage.addChild(newLine);
			list.push(newLine);

			if (line.startP == endPoint) {
				count++;
				trace(count);
				if (count == N) {
					stage.removeEventListener(Event.ENTER_FRAME,onEnterFrameHandler);
				}
			}

		}
	}
}

おまけ

ドラゴン曲線は実際に作ることができます
作り方は細長い紙を同じ方向に半分に折り続けていき、それを開いたあと折り目が90度になるように整えるだけです
実際に作ってみました
写真は5回折ったものです
手作りDoragonCurve

繰り返しを5回にしたflashと比べてみてください

※クリックでstart

This movie requires Flash Player 9

多少雑ですが同じ形になりました(よかったw)
実際に折ってみるとわかりますが、ドラゴン曲線はお互いの線が一回も交わりません
なんでだろー?w
暇つぶしに作ってみるのもおもしろいかもw
10回折りの手作りドラゴン曲線を作れば英雄に?!w

フラクタル~C曲線~

No Comments

ま た か
ってことでフラクタルw

C曲線とはレヴィさんが考えたフラクタルのことで、Cに似た形になることからC曲線と名づけたそうです。
適当だなおいw

C曲線はコッホ曲線と似ています
コッホ曲線は線分を3分割し、真ん中の線分を正三角形に置き換えていました
C曲線では線分全体を直角二等辺三角形に置き換えます

Koch&C

これだけでできあがる形はまったく違うものになります
これは「ほんのわずかな初期条件の違いが予想もつかないほど大きく違った結果を生む」というカオスの特徴でもあります
実はカオスとフラクタルは密接に関係しており、自然界で多くみられるカオスをグラフにプロットするとそのグラフはフラクタルな性質を示すことが知られています

すごいですなぁw

※クリックでstart

This movie requires Flash Player 9

Line.as


package {
	import flash.display.Sprite;
	import flash.geom.Point;
	public class Line extends Sprite{
		public var startP:Point;
		public var endP:Point;
		public var distance:Number;
		public var angle:Number;
		function Line(startP:Point, endP:Point) {
			this.startP = startP;
			this.endP = endP;
			distance = Point.distance(startP, endP);
			angle = Math.atan2(endP.y-startP.y, endP.x-startP.x);
			
			graphics.lineStyle(0,0x000000);
			graphics.moveTo(startP.x, startP.y);
			graphics.lineTo(endP.x, endP.y);
			graphics.endFill();
		}
	}
}

CCurve.as


package {
	import flash.display.Sprite;
	import flash.events.MouseEvent;
	import flash.events.Event;
	import flash.geom.Point;
	public class CCurve extends Sprite {
		private var list:Array = [];
		private var endPoint:Point;
		private var count:int=0;
		private const N:int=10;	
		private const W:int = 300;
		private const H:int = 300;
		function CCurve() {
			var line:Line=new Line(new Point(W/4,H*2/3),new Point(W-W/4, H*2/3));
			endPoint=line.endP;
			list.push(line);
			stage.addChild(line);

			stage.addEventListener(MouseEvent.CLICK,onClick);
			function onClick(event:MouseEvent):void {
				stage.addEventListener(Event.ENTER_FRAME,onEnterFrameHandler);
				stage.removeEventListener(MouseEvent.CLICK,onClick);
			}

		}
		private function onEnterFrameHandler(event:Event):void {
			var line:Line=list[0];
			stage.removeChild(line);
			list.splice(0, 1);

			var p1:Point=new Point();
			p1.x= line.distance/2 * Math.SQRT2 * Math.cos(line.angle-Math.PI/4) + line.startP.x;
			p1.y= line.distance/2 * Math.SQRT2 * Math.sin(line.angle-Math.PI/4) + line.startP.y;

			var newLine:Line=new Line(line.startP,p1);
			stage.addChild(newLine);
			list.push(newLine);
			newLine=new Line(p1, line.endP);
			stage.addChild(newLine);
			list.push(newLine);

			if (line.endP == endPoint) {
				count++;
				trace(count);
				if (count == N) {
					stage.removeEventListener(Event.ENTER_FRAME,onEnterFrameHandler);
				}
			}
		}
	}
}

Blue Taste Theme created by Jabox