http://www.javaworld.com.tw/jute/post/view?bid=5&id=277737&tpg=1&ppg=1&sty=1&age=0#277737
雖然特地寫成 Tail-Recursion 形式的 recursion 有時有點矯情,形式上也沒有
其他較直觀的 recursion 的形式來的美...
我有寫了一個 Tail-Recursion 的 RecursiveSummarizer2 class:
package eu.plumbr.demo.inlining;
import tw.javaworld.optimizer.TailRecursionEliminated;
public class RecursiveSummarizer2 implements Summarizer {
@Override
public int sum(int[] array) {
return sumImpl(0, array, 0, array.length);
}
@TailRecursionEliminated
private int sumImpl(int acc, int[] data, int from, int to) {
if (from < to)
return sumImpl(acc + data[from], data, from + 1, to);
return acc;
}
}
並稍微修改原作者的 test case:
package eu.plumbr.demo.inlining;
public class Main {
static final int COUNT = 200; //我改成 200,暖身久一點
public static void main(String[] args) {
Summarizer[] summarizers = new Summarizer[] {
new InlineSummarizer(), new IterativeSummarizer(),
new RecursiveSummarizer(), new RecursiveSummarizer2(),
};
int[] array = initArray();
for (Summarizer s : summarizers) {
// Warm-up to discard runs where JIT optimizations were not
// yet completed. Check it out by switching on JIT log
// -XX:+PrintCompilation. You probably need to tweak the Main.COUNT
// on different architectures.
for (int j = 0; j < 5; j++) {
long start = System.nanoTime();
for (int i = 0; i < COUNT; i++)
s.sum(array);
long end = System.nanoTime();
logTime(s.getClass().getName(), start, end);
}
}
}
private static void logTime(String message, long start, long end) {
System.out.println(message + ":" + (end - start) / COUNT + " ns.");
}
private static int[] initArray() {
int[] array = new int[1024];
for (int i = 0; i < array.length; i++) {
array[i] = i;
}
return array;
}
}
我有試過分別啓用與不啓用 TailRecursionEliminated 功能的情況,
我感覺暖身似乎可能還是不太夠,因為跑個幾次覺得輸出的數值落差還不算小。
由於待加數值只有 1024 個,所以是不會有炸掉 thread stack 的情事,那
啟用 TailRecursionEliminated 的情況就變成是把遞迴偷偷改成 iteration。
我貼上我跑幾次中的結果之一
無啓用 TailRecursionEliminated 時:
eu.plumbr.demo.inlining.InlineSummarizer:31460 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1420 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1840 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1415 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1420 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:78895 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:32005 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:15470 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:10285 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:6460 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:77360 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7915 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7990 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7695 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7760 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:24725 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5695 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5565 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5930 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5530 ns.
有啓用 TailRecursionEliminated 時:
eu.plumbr.demo.inlining.InlineSummarizer:29790 ns.
eu.plumbr.demo.inlining.InlineSummarizer:3255 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1415 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1415 ns.
eu.plumbr.demo.inlining.InlineSummarizer:1415 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:84275 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:35055 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:10835 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:10555 ns.
eu.plumbr.demo.inlining.IterativeSummarizer:6715 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:90520 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:8115 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:8045 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:8040 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer:7980 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:23120 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5550 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5445 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5515 ns.
eu.plumbr.demo.inlining.RecursiveSummarizer2:5460 ns.
從這些數據來看,我認為似乎寫成 Tail-Recursion 的形式,JVM 就有一部分
優化,導致 RecursiveSummarizer2 的數據更接近 IterativeSummarizer。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.172.191.203
※ 編輯: sbrhsieh 來自: 1.172.191.203 (03/20 02:25)
希望沒有扯的太牽強。
或許有人還是偏愛遞迴的寫法,無法割捨...
那講到遞迴除了考慮效能,另外一點就是遞迴 depth 太深會炸掉 stack 的問題。
ㄟ... 這些部分有興趣的人不妨看一下這一篇: