Problema:Come posso valutare un'implementazione della tabella hash? (Utilizzo HashMap come riferimento)
devo confrontare 2 implementazioni tabella hash (ben sostanzialmente
HashMapcon un altro) e fare una conclusione ragionevole.Non mi interessa l'accuratezza al 100% ma sto solo nella giusta direzione nella mia stima.
Sono interessato alla differenza non solo per operazione ma principalmente sulla tabella come un "intero".
Non ho un requisito rigoroso sulla velocità quindi se l'altra implementazione è ragionevolmente più lento posso accettare, ma ho fare aspettarsi/richiedono che l'utilizzo della memoria sia migliore (in quanto uno dei hashtables è supportato dalla tabella primitiva).
quello che ho fatto finora:
Inizialmente ho creato il mio "punto di riferimento" personalizzato con loop e molte chiamate al suggerimento per gc per avere un'idea della differenza, ma io sto leggendo online che l'utilizzo di uno strumento standard è più affidabile/appropriato.
Esempio del mio approccio (MapInterface è solo un wrapper così posso passare tra le implementazioni.):
int[] keys = new int[10000000];
String[] values = new String[10000000];
for(int i = 0; i < keys.length; ++i) {
keys[i] = i;
values[i] = "" + i;
}
if(operation.equals("put", keys, values)) {
runPutOperation(map);
}
public static long[] runOperation(MapInterface map, Integer[] keys, String[] values) {
long min = Long.MAX_VALUE;
long max = Long.MIN_VALUE;
long run = 0;
for(int i = 0; i < 10; ++i) {
long start = System.currentTimeMillis();
for(int i = 0; i < keys.length; ++i) {
map.put(keys[i], values[i]);
}
long total = System.currentTimeMillis() - start;
System.out.println(total/1000d + " seconds");
if(total < min) {
min = time;
}
if(total > max) {
max = time;
}
run += time;
map = null;
map = createNewHashMap();
hintsToGC();
}
return new long[] {min, max, run};
}
public void hintsToGC() {
for(int i = 0; i < 20; ++i) {
System.out.print(". ");
System.gc();
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
private HashMapInterface<String> createNewHashMap() {
if(jdk) {
return new JDKHashMapWrapper<String>();
}
else {
return new AlternativeHashMapWrapper<String>();
}
}
public class JDKHashMapWrapper implements HashMapInterface<String> {
HashMap<Integer, String> hashMap;
JDKHashMapWrapper() {
hashMap = new HashMap<Integer, String>();
}
public String put(Integer key, String value) {
return hashMap.put(key, value);
}
//etc
}
(Voglio testare put, get, contains e l'utilizzo di memoria)
posso essere sicuro da usando il mio approccio che posso ottenere misurazioni ragionevoli?
Se no quale sarebbe lo strumento più appropriato da usare e come?
Aggiornamento:
- I test anche con numeri casuali (anche ~ 10M numeri casuali) utilizzando SecureRandom.
- Quando la tabella hash ridimensiona stampo la dimensione logica della tabella hash/dimensione della tabella effettiva per ottenere il fattore di carico
Aggiornamento:
Per il mio caso specifico, dove sono interessati anche a interi cosa possono esserci delle insidie con il mio approccio?
UPDATE dopo @ dimo414 commenta:
Bene al minimo la tabella hash come un "tutto" non è significativa
Voglio dire come la tabella hash si comporta sotto vari carichi sia a runtime e consumo di memoria.
Ogni struttura dati è un compromesso di diversi metodi
sono d'accordo.mio trade-off è una penalità di accesso accettabile per il miglioramento della memoria
è necessario identificare quali caratteristiche che ti interessa verificare
1) mettere (chiave, valore);
2) get (chiave, valore);
3) containsKey (chiave);
4) tutto quanto sopra quando si hanno molte voci nella tabella hash
Una cosa che potresti fare sarebbe usare System.nanoTime() piuttosto che System.currentTimeMillis(). È più adatto per questo tipo di benchmarking. – bhspencer
Credo che tu abbia visto http://stackoverflow.com/q/504103/113632? – dimo414
@ dimo414: ho. 1) Suggerisce alcune opzioni JVM extra da utilizzare, quindi suppongo che il mio approccio con le opzioni JVM possa essere combinato per avere più confidenza 2) Ho controllato i framework nell'ultima regola. 'Bill e Paul's etc' fa più o meno lo stesso di quello che faccio io. Caliper è per me che è un utente inesperto e non molto esperto nel benchmarking di una black-box con documentazione non molto utile e dà apparentemente un micro benching per operazione. Non ho idea di come sarebbe stata testata la tabella hash. JHM, devo essere sincero, ho bisogno di leggere se può aiutarmi o meno – Cratylus