【LinkedListTest】連結リストによる高速化

連結リストによる高速化
自分の環境では処理時間を21%ほどに短縮できた

by wetcradle 24 Mar 2010

Tags

linkedlist データ構造 連結リスト
Embed

/**
 * Copyright wetcradle ( http://wonderfl.net/user/wetcradle )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/szJO
 */

/**
連結リストによる高速化
自分の環境では処理時間を21%ほどに短縮できた
*/
package {
	import flash.display.Sprite;
	import flash.text.TextField;
	public class LinkedListTest extends Sprite {
		private var textField:TextField;
		private var vector:Vector.<LinkedListItem>;
		private var linkedList:LinkedListItem;
		private const LENGTH:uint = 1e+6;
		public function LinkedListTest():void {
			configTextField();
			initializeList();
			
			var vectorSum:Number = 0;
			var linkedSum:Number = 0;
			for (var i:int=0; i<10; i++) {
				var vectorTime:Number = doTestVector();
				var linkedTime:Number = doTestLinked();
				vectorSum += vectorTime;
				linkedSum += linkedTime;
				textField.appendText(String(vectorTime)+", "+String(linkedTime)+"\n");
			}
			textField.appendText("\n"+String(vectorSum)+", "+String(linkedSum)+"\n");
		}
		private function configTextField():void {
			textField = new TextField();
			textField.width = textField.height = 400;
			addChild(textField);
			textField.text = "vector, linked\n";
		}
		private function initializeList():void {
			var prevLinkedListItem:LinkedListItem = linkedList = new LinkedListItem();
			vector = new Vector.<LinkedListItem>(LENGTH);
			for (var i:int=0; i<LENGTH; i++) {
				vector[i] = new LinkedListItem();
				prevLinkedListItem = prevLinkedListItem.next = new LinkedListItem();
			}
		}
		private function doTestVector():Number {
			var startDate:Date = new Date();
			for (var i:int=0; i<LENGTH; i++) {
				vector[i].value++;
			}
			return new Date().time - startDate.time;
		}
		private function doTestLinked():Number {
			var startDate:Date = new Date();
			var tempLinkedListItem:LinkedListItem = linkedList;
			while (tempLinkedListItem = tempLinkedListItem.next) {
				tempLinkedListItem.value++;
			}
			return new Date().time - startDate.time;
		}
	}
}

class LinkedListItem {
	public var next:LinkedListItem;
	public var value:Number = 0;
}