Posts Tagged ‘演算法’

神奇的Duff’s Device演算法

Thursday, November 18th, 2010

這是在看“Professional JavaScript for Web Developers 2nd Edition”這本書時看到的。

這個演算法的目的是為了降低一般for/while迴圈初始時的額外資源和一直去check condition所造成的額外運算,而改成每次”直接”執行8次要做的process流程。Tradeoff是code會寫比較多。較適用於資料量龐大的Array,若是小資料則沒有使用的必要。以下範例code以JavaScript為例。

原本的code

for( var i=0; i<values.length; i++ ) {
	process(values[i]);
}

改良版的Duff’s Device code

// calculate the values
var iterations = Math.floor(values.length / 8);
var leftover = values % 8;
var i = 0;

// execute the remain values
if( leftover > 0 ) {
	do {
		process(values[i++]);
	} while (--leftover > 0 );
}

// execute values 8 times per loop
do {
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
	process(values[i++]);
} while(--iterations > 0);

不過經過我實際測試的結果,好像沒什麼差… :???:

相關的參考文章:
http://en.wikipedia.org/wiki/Duff’s_device