這是在看“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
Tags: Algorithm, Javascript, Speedup Performance, 演算法, 計算機科學