1
我使用HashMap緩存通過遞歸算法計算出的約200萬個值。我使用集合框架中的HashMap<Integer, Double>或者Trove庫中的TIntDoubleHashMap，由boolean useTrove變量控制，如下面的代碼所示。使用標準Java HashMap（與Trove THashMap相比）導致非HashMap代碼運行速度更慢
我不指望特羅韋庫要快，因爲它比500ms左右的HashMap<>避免自動裝箱等。而實際上，put()和get()通話大約需要300毫秒運行（總量）爲THashMap。
現在，使用THashMap時，我的整體程序運行時間大約爲2.8秒，使用HashMap<>時爲6.7秒。單獨調用put()和get()調用的運行時間增加不能解釋這種差異。
我懷疑這跟
HashMap<>大大增加運行時間的事實，這種實現是相當內存低效的，因爲 每個INT /雙需要被裝箱爲對象，這增加了驅動 內存使用會導致緩存在節目的其他部分錯過。 這個解釋是否有意義，我如何確認/拒絕這個 假設？一般來說，我該如何探索這些場景的算法優化？對算法進行剖析並不容易指出是罪魁禍首，至少如果單獨考慮CPU時間是 。這僅僅是一個事先知道的問題：內存使用需要優先考慮內存飢渴的程序嗎？
代碼如下。
import java.util.HashMap;
import gnu.trove.map.hash.TIntDoubleHashMap;
class RuntimeStopWatch {
long elapsedTime;
long startTime;
RuntimeStopWatch() { reset(); }
void reset() { elapsedTime = 0; }
void start() { startTime = System.nanoTime(); }
void stop() {
long endTime = System.nanoTime();
elapsedTime += (endTime - startTime);
startTime = endTime;
}
void printElapsedTime(String prefix) {
System.out.format(prefix + "%dms\n", elapsedTime/1000000);
}
}
public class HashMapBehaviour {
static RuntimeStopWatch programTime = new RuntimeStopWatch();
static RuntimeStopWatch hashMapTime = new RuntimeStopWatch();
static HashMap<Integer, Double> javaHashMapCache;
static TIntDoubleHashMap troveHashMapCache;
static boolean useTrove;
public static void main(String[] args) {
// useTrove = true;
useTrove = false;
javaHashMapCache = new HashMap<>();
troveHashMapCache = new TIntDoubleHashMap();
programTime.start();
recursiveFunction(29, 29, 178956970);
programTime.stop();
programTime.printElapsedTime("Program: ");
hashMapTime.printElapsedTime("Hashmap: ");
}
static double recursiveFunction(int n, int k, int bitString) {
if (k == 0) return 0.0;
if (useTrove) {
hashMapTime.start();
if (troveHashMapCache.containsKey(bitString | (1 << n))) return troveHashMapCache.get(bitString | (1 << n));
hashMapTime.stop();
} else {
hashMapTime.start();
if (javaHashMapCache.containsKey(bitString | (1 << n))) return javaHashMapCache.get(bitString | (1 << n));
hashMapTime.stop();
}
double result = 0.0;
for (int i = 0; i < (n >> 1); i++) {
double play1 = recursiveFunction(n - 1, k - 1, stripSingleBit(bitString, i));
double play2 = recursiveFunction(n - 1, k - 1, stripSingleBit(bitString, n - i - 1));
result += Math.max(play1, play2);
}
if (useTrove) {
hashMapTime.start();
troveHashMapCache.put(bitString | (1 << n), result);
hashMapTime.stop();
} else {
hashMapTime.start();
javaHashMapCache.put(bitString | (1 << n), result);
hashMapTime.stop();
}
return result;
}
static int stripSingleBit(int bitString, int bitIndex) {
return ((bitString >> (bitIndex + 1)) << bitIndex) | (bitString & ((1 << bitIndex) - 1));
}
}