Problem:Jak mogę ocenić implementację tablicy mieszającej? (Przy użyciu HashMap jako odniesienie)
muszę porównać 2 implementacje tabeli mieszania (dobrze zasadzie
HashMapz innym) i dokonać rozsądnego wniosku.Nie jestem zainteresowany w 100% dokładnością, ale po prostu we właściwym kierunku, w mojej ocenie.
Jestem zainteresowany tą różnicą, nie tylko za działania, ale przede wszystkim na hashtable jako „całość”.
nie mam ścisłe wymagania na szybkość więc jeżeli druga realizacja jest rozsądnie wolniej mogę to zaakceptować, ale zrobić oczekiwać/wymagać, aby być lepiej zużycie pamięci (ponieważ jeden z hashtables jest wspierane przez prymitywny stół).
co zrobiłem do tej pory:
Pierwotnie tworzę własne niestandardowe „benchmark” z pętli i wiele połączeń do zrozumienia dla GC, aby uzyskać poczucie różnicy ale czytam w internecie, że używanie standardowego narzędzia jest bardziej niezawodne/odpowiednie.
Przykład mojego podejścia (MapInterface tylko wrapper więc mogę przełączać się między implementacjami.):
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
}
(Chcę przetestować put, get, contains oraz wykorzystanie pamięci)
Czy mogę mieć pewność, przez używając mojego podejścia, że mogę uzyskać rozsądne pomiary?
Jeśli nie, jakie byłoby najbardziej odpowiednie narzędzie do użycia i jak?
Aktualizacja:
- Ja też przetestować liczb losowych z (także ~ 10M liczb losowych) z wykorzystaniem SecureRandom.
- Gdy tabeli mieszania zmienia rozmiar drukować logiczny rozmiar tabeli hash/wielkość rzeczywistej tabeli, aby uzyskać współczynnik obciążenia
Aktualizacja:
Na moim konkretnym przypadku, w którym jestem zainteresowany również w całkowitych jakie mogą być pułapki z moim podejściem?
UPDATE po @ dimo414 komentuje:
Dobrze przynajmniej hashtable jako "całość" nie ma sensu
Znaczy jak hashtable zachowuje się pod różnymi obciążeniami zarówno na środowisko uruchomieniowe i zużycie pamięci.
Każda struktura danych jest kompromis różnych metod
zgadzam.Moja kompromis jest do przyjęcia kary dostęp do poprawy pamięci
Należy określić, jakie funkcje jesteś zainteresowany weryfikacji
1) wprowadzenie (klucz, wartość);
2) get (klucz, wartość);
3) zawieraKey (klucz);
4) wszystkie powyższe, gdy wiele wpisów w tabeli mieszania
Jedną z rzeczy, którą można zrobić, byłoby użycie System.nanoTime() zamiast System.currentTimeMillis(). Jest lepiej przystosowany do tego typu testów porównawczych. – bhspencer
Ufam, że widziałeś http://stackoverflow.com/q/504103/113632? – dimo414
@ dimo414: Mam. 1) Zaleca stosowanie dodatkowych opcji JVM, więc domyślam się, że moje podejście do opcji JVM można połączyć, aby uzyskać większą pewność. 2) Sprawdziłem frameworki w ostatniej regule. 'Bill i Paul's etc' ma prawie takie samo jak to, co robię. Caliper jest dla mnie, który jest pierwszym użytkownikiem i niezbyt doświadczonym w testowaniu czarnej skrzynki z niezbyt pomocną dokumentacją i daje najwyraźniej mikro-ławki na operację. Nie mam pojęcia, jak będzie testowany stół mieszający. JHM szczerze mówiąc Muszę przeczytać, czy może mi pomóc, czy nie – Cratylus