Datentypen Map effizient mit eigenem Key

Dragonfire

Bekanntes Mitglied
Hallo,
ich habe folgende Problemstellung:

Ich benötige Daten aus einer Datenbank und dies sogar mehrfach schnell hintereinander,
da es keinen Sinn macht alles vorher im Speicher zu laden habe ich mir ein kleinen Cache geschrieben.
Dieser speichert in einer
Code:
HashMap<DKey, DValue>
einmal abgefragte Werte (wir gehen davon aus, dass der Speicher dafür ausreicht, bzw von Zeit zu Zeit die HashMap aufgeräumt wird(*) und die Werte in der Datenbank sich nicht ändern, bzw den Cache benachrichtigen).
DValue und DKey sind eigene Klassen. DValue repräsentiert die Daten aus der Datenbank.
DKey beinhaltet den Schlüssel die den Datensatz eindeutig identifizieren.

Es funktioniert auch alles wunderbar,
ich sehe nur ein Problem, was mich ein wenig stört.

Jedes mal, wenn ich die "get" Methode meines Cache aufrufe, muss ich ein neues DKey Objekt erzeugen,
sei es nur
Code:
new  DIntKey(1)
oder
Code:
new DSpecialKey(1, "ich mag Stings nicht", 1.0f)
.

Diese Schlüssel wieder in einem Pool zu speichern (um die Erzeugen zu umgehen) führt zu dem ursprünglichen Problem, dass man für einen zusammengesetzten Schlüssel wieder einen neuen String (wieder ein neues Objekt) erzeugen muss und er Aufwand Teilinformationen aus dem Schlüssel zu erhalten ziemlich groß ist (split auf einem String ist ja nicht gerade zeitsparend).

Gibt es ein schönes Pattern dafür, oder eine Datenstruktur die ich nicht kenne?

###
*zum aufräumen: Auf Wunsch kann man den Schlüssel einen timestamp mitgeben, der bei
Code:
equals(Object o)
und
Code:
hashcode()
nicht berücksichtigt wird, über dem man anschließend "alte" Werte entfernen kann (da muss ich auch noch mal schauen welcher lock Mechanismus der schnellste ist, da HashMap ja nicht synchronized ist)
 

tuttle64

Bekanntes Mitglied
Jedes mal, wenn ich die "get" Methode meines Cache aufrufe, muss ich ein neues DKey Objekt erzeugen,
sei es nur
Code:
new  DIntKey(1)
oder
Code:
new DSpecialKey(1, "ich mag Stings nicht", 1.0f)
./QUOTE]

Die Key-Klasse muss zwingend die Methoden equals() und hashCode() überschreiben, ansonsten werden zwei eigene new Objekte derselben Klasse nie gleich sein! Seien zwei Objekte x und y gegeben, dann muss die Implementierung von equals() und hashCode() folgende Regeln befolgen:

1. falls x.equals(y) == true, dann muss auch x.hashCode() == y.hashCode() true liefern.
2. aber falls x.hashCode() == y.hashCode() true liefern, dann muss x.equals(y) nicht true liefern
3. falls x.equals(y) == false, keine hashCode()-Regel
4. falls x.hashCode() != y.hashCode(), dann muss x.equals(y) == false

Es sieht nach viel aus, aber im Prinzip erfüllt bereits ein return 42 obige Regeln, was allerdings eine sehr ineffiziente Streuung der Objekte in Map zur Folge hat. Egal, sind equals() und hashCode() überschrieben, braucht man für die Suche nur ein Objekt, der z.B. über eine setKey() verfügt. Danach kann man den zu suchenden Key über setKey() setzen und immer das gleiche Objekt zur Suche verwenden.
 
Zuletzt bearbeitet:

Dragonfire

Bekanntes Mitglied
Natürlich überschreiben die DKey die Methoden
Code:
equals(Object o)
und
Code:
hashCode
...

Der triviale Ansatz über ein SuchKey über setter ist natürlich genial^^

Deine vier Fälle sind logisch,
aber das ist doch die Definition von hashcode und equals, oder?

So sieht das z.b. bei mir für ein (int,int) Key aus aus:

Java:
		@Override
		public int hashCode() {
			return 31 * (31 + inta) + intb;
		}

		@Override
		public boolean equals(Object obj) {
			try {
				return this.inta == ((DIntIntKey) obj).inta
						&& this.intb == ((DIntIntKey) obj).intb;
			} catch (Exception e) {
				e.printStackTrace();
			}
			return false;
		}


Sollte ich dich richtig verstanden habe,
habe ich in der Klasse einen SuchKey,
wo ich bei jedem get die setter Aufrufe ...
Solle ich nichts im Cache finden muss ich dann aber einen neuen DKey erzeugen,
vielleicht durch einen eigene klon Methode,
sonst würde ich ja immer den Key im Cache ändern.

Dann muss ich mir nur noch Gedanken um die Synchronisation machen, da der SuchKey ja geteilt wird.
 

bERt0r

Top Contributor
So wie ich das jetzt verstanden habe, hat der TO kein Problem mit seiner Hashmap,
Es funktioniert auch alles wunderbar
aber das new DKey stört ihn.
Hast du denn für jeden Table in deiner DB eine eigene Key Klasse für deine HashMap?

Ich verstehe leider deinen Anwendungsfall nicht so ganz, wenn du sehr schnell viele DB abfragen hast, kannst du die gar nicht effizient cachen. Eventuell liegt das Problem bei deinenen Abfragen, sprich im SQL.
 

Dragonfire

Bekanntes Mitglied
So wie ich das jetzt verstanden habe, hat der TO kein Problem mit seiner Hashmap, aber das new DKey stört ihn.
Hast du denn für jeden Table in deiner DB eine eigene Key Klasse für deine HashMap?

Ich verstehe leider deinen Anwendungsfall nicht so ganz, wenn du sehr schnell viele DB abfragen hast, kannst du die gar nicht effizient cachen. Eventuell liegt das Problem bei deinenen Abfragen, sprich im SQL.

An deinem Argument ist was dran, dass eine Datenbank ziemlich effektiv ist ...
aber stell Dir mal vor, du willst aus einer großen Mengen nur einen Wert haben und den brauchst du immer wieder, dann speicherst du ihn zwischen (so sollte es eine DB auch machen).

Das selbe mache ich auch.
Meine benötigten Daten liegen in einer Datenbank, oder einer Datei, oder ganz woanders und Ladeoperationen sind teuer, Speicherplatz aber nicht (in meinem Szenario).
Aus diesem Grund habe ich mich für die Speicherung einer HashMap entschieden.

Ein get-Aufruf kann mehrere Male pro Sekunden aufgerufen werden und da würden einzelne Ladeoperationen die Performance verschlechtern.

Ich tue mich schwer mit dem Gedanken, dass bei jedem get ein neues DKey Objekt erzeugt wird,
klar hätte ich den Speicher, aber bei so vielen Aufrufen weiß ich nicht wie der GC das macht^^
Wenn man dies irgendwie vermeiden könnte wäre das glaubig besser.

Ich denke ich werde dann einen KeyPool machen, mit einer maximale Anzahl an Keys und jeder get Aufruf schnappt sich einen vorhandenen Key und ruft die setter auf, wenn nicht muss der get-Aufruf halt warten, dann muss man halt Speicher, bzw. die Anzahl der Keys erhöhen.
 

bERt0r

Top Contributor
Das ist das was ich nicht verstehe: wenn du den einen Wert zwischenspeichern willst, wieso machst du das in der Hashmap und wieso mit einem solch komplizierten Key?
 

Dragonfire

Bekanntes Mitglied
Das ist das was ich nicht verstehe: wenn du den einen Wert zwischenspeichern willst, wieso machst du das in der Hashmap und wieso mit einem solch komplizierten Key?

Wenn du eine bessere Lösung hast immer her damit,
vergiss nur nicht das es mehrere Werte sind welche gecacht werden sollen
und es sind nicht nur int,int Werte sondern auch noch viele andere Kombinationen.

ich habe z.b stark vereinfacht (ohne KeyPool):

Java:
public int getIntInt(int a, int b) {
     return get(new DIntIntKey(a,b)).getInt();
}

public DIntValue get(DKey k) {
    DValue v = myHash.get(k);
    if(v == null) {
        v = loadFromDB(k);
        myHash.put(k, v);
    }
    return (DIntValue) v;    
}

natürlich könnte ich auch sowas hier machen:

Java:
public int getIntInt(int a, int b) {
     return get(a + "." + b).getInt();
}

public DIntValue get(String k) {
    DValue v = myHash.get(k);
    if(v == null) {
        v = loadFromDB(k);
        myHash.put(k, v);
    }
    return (DIntValue) v;    
}

Aber String's ist nicht gerade performant und wenn man anschließend mit
Code:
keySet()
über die HashMap iteriert hat man durch den zusätzlich split viel Zeitverlust.

Deswegen fragte ich ja auch anfangs,
ob es ein Pattern gibt Daten mit zusammengesetzten Schlüssel
effizient in JAVA (ohne DB oder sonstiges) zu speichern.
Für einfache Schlüssel ist die HashMap wunderbar^^
(wobei man für primitive Datentypen auch wieder neue Wrapper Objekte, z.b. Integer für int erzeugen muss)

Ps.: Das Problem zu lösen ist ja kein Problem,
aber ich hätte es halt gerne elegant^^
 
Zuletzt bearbeitet:

bERt0r

Top Contributor
Nochmal: Ich verstehe das WIESO nicht. Du musst doch irgendeinen Grund dafür haben, dass du ein Caching benötigst. Wenn du einfach so einen Datensatz rausliest und weist, dass du die Daten dann noch 10 mal brauchst, kannst du ihn dir ja als Objektvariable genauso speichern. Wenn es mehrere Datensätze sind, packst du sie in eine Collection.
Aber wieso du die DB Struktur nochmal in einer Hashmap abbilden musst verstehe ich nicht.
 

bERt0r

Top Contributor
Ich kenne deinen Anwendungsfall nicht. Du meinst, dass die gleichen Datensätze mehrmals hintereinander abgefragt werden, weist das aber zur Laufzeit nicht? Das heisst, wenn Datensatz x aus der DB gelesen wird, hast du eine hohe Wahrscheinlichkeit dass er gleich danach nochmal gelesen wird?
Grundsätzlich sind Datenbanken ziemlich performant und haben selber schon einen Cache. Wenn du willkürliche Zugriffe auf deine Daten hast, wirst du das nicht anders machen können, also mit deinen Hashtables die DB nochmal Abbilden. Ob das dann aber den großen Peformance Schub bringt sei dahingestellt.
 

Dragonfire

Bekanntes Mitglied
Ich kenne deinen Anwendungsfall nicht. Du meinst, dass die gleichen Datensätze mehrmals hintereinander abgefragt werden, weist das aber zur Laufzeit nicht? Das heisst, wenn Datensatz x aus der DB gelesen wird, hast du eine hohe Wahrscheinlichkeit dass er gleich danach nochmal gelesen wird?
Grundsätzlich sind Datenbanken ziemlich performant und haben selber schon einen Cache. Wenn du willkürliche Zugriffe auf deine Daten hast, wirst du das nicht anders machen können, also mit deinen Hashtables die DB nochmal Abbilden. Ob das dann aber den großen Peformance Schub bringt sei dahingestellt.

Der Performance Schub ist bei einer Datenbank welche lokal liegt eventuell nicht so groß,
müsste man mal testen, es entfällt ja nur der Aufbau der Verbindung.
Diese Daten können aber auch von externen Datenbanken, oder Dateien stammen und dann sollte es wesentlich schneller sein.
 
S

Spacerat

Gast
Kann es sein, dass eine HashMap hier schon gar nicht mehr ausreicht und man vllt. besser den gesamten SQL-Befehl bis zum Semikolon als String-Key in einer TreeMap verwendet?
BTW.: Ich bin inzwischen der Ansicht, dass HashSonstwas völlig überbewertet und nur dann performant ist, wenn man korrekt implementiert.
Java:
String key = "SELECT * FROM blablasuelz";
Object value;
if((value = cache.get(key)) == null) {
  value = dbZugriff(key);
  cache.put(key, value);
}
Soviel zur Übersicht. Natürlich verwendet man heutzutage prepared Statements aber mir sind die für solche Vorführzwecke viel zu umständlich.
[edit]Im übrigen: Strings sind sehr wohl performant, solange sie als das angenommen werden, was sie sein sollen... IMMUTABLE[/edit]
 
Zuletzt bearbeitet von einem Moderator:

Dragonfire

Bekanntes Mitglied
Kann es sein, dass eine HashMap hier schon gar nicht mehr ausreicht und man vllt. besser den gesamten SQL-Befehl bis zum Semikolon als String-Key in einer TreeMap verwendet?
BTW.: Ich bin inzwischen der Ansicht, dass HashSonstwas völlig überbewertet und nur dann performant ist, wenn man korrekt implementiert.
Java:
String key = "SELECT * FROM blablasuelz";
Object value;
if((value = cache.get(key)) == null) {
  value = dbZugriff(key);
  cache.put(key, value);
}
Soviel zur Übersicht. Natürlich verwendet man heutzutage prepared Statements aber mir sind die für solche Vorführzwecke viel zu umständlich.

Mein Key Objekt managt das alles ;)
die Keys unterscheiden sich ja wie gesagt nur in ein paar Werten.
Außerdem lese ich ja nicht nur von einer Datenbank ein, sondern es kann alles mögliche sein^^

Was würde denn eine TreeMap bringen?
Der Zugriff wäre doch langsamer und eine Sortierung brauche ich eigentlich nicht ...

PS.: Wie hast du den coolen Nachtrag hinbekommen oO
 
S

Spacerat

Gast
Also solange du sicherstellen kannst, dass deine Schlüssel ausreichend verschiedene Hashcodes liefern ist 'ne HashMap schneller. Spätestens, wenn die Implementation deiner hashCode-Methode öfters gleiche Werte liefert, geht das Gesuche per equals los. Sprich: Eine HashMap ist nur so Leistungsfähig wie die Implementation der hashCode-Methode ihrer Schlüssel.
Eine TreeMap dagegen ist zwar zunächst langsamer aber dafür ist sie gleichmässig performant und eigentlich kostet nur das Einfügen Zeit. Aus einem Cache aber will man ja hauptsächlich lesen, deswegen cached man ja. Mach deinen DKey einfach Comparable und probier's aus.
Zum letzten [EDIT]http://www.java-forum.org/plauderecke/79231-verbesserungsvorschlaege-91.html#post832191 ;)[/EDIT]
 

Dragonfire

Bekanntes Mitglied
Also solange du sicherstellen kannst, dass deine Schlüssel ausreichend verschiedene Hashcodes liefern ist 'ne HashMap schneller. Spätestens, wenn die Implementation deiner hashCode-Methode öfters gleiche Werte liefert, geht das Gesuche per equals los. Sprich: Eine HashMap ist nur so Leistungsfähig wie die Implementation der hashCode-Methode ihrer Schlüssel.
Eine TreeMap dagegen ist zwar zunächst langsamer aber dafür ist sie gleichmässig performant und eigentlich kostet nur das Einfügen Zeit. Aus einem Cache aber will man ja hauptsächlich lesen, deswegen cached man ja. Mach deinen DKey einfach Comparable und probier's aus.
Zum letzten [EDIT]http://www.java-forum.org/plauderecke/79231-verbesserungsvorschlaege-91.html#post832191 ;)[/EDIT]

Was meinst du mit Compareable, in welchem Zusammenhang?
Die hashFunktion lasse ich mit eclipse berechnen, equals mache ich immer selber, da mag ich die eclipse Version nicht^^ (kannst ja auch mal oben im Thread schauen ...
http://www.java-forum.org/allgemeine-java-themen/128224-map-effizient-eigenem-key.html#post835066)


Hättest du Interesse an diesem Thema?
Dann würde ich extra ein eclipse Projekt aufsetzen und das mal alles testen,
was besser ist xD

ABER SCHONMAL EIN GROSSES DANKESCHÖN !!!

Die Idee mit dem KeyPool gefällt mir richtig^^
 
Zuletzt bearbeitet:
S

Spacerat

Gast
Comparable (ohne "e" ;)) ist das Interface, welches für Keys einer SortedMap benötigt wird - im Prinzip wie hashCode für eine HashMap. die zu implementierende Methode des Interfaces heisst "compareTo", kann per Generic-Parameter auf einen Konkreten Objekttypen - in deinem Fall DKey - eingestellt werden und führt, wenn man so will, hashCode und equals zusammen aus (bitte nicht allzu wörtlich nehmen). Die Methode vergleicht also this mit einem anderen Objekt und liefert < 0 für kleiner als, 0 für gleich und > 0 für grösser als. Eine equals-Methode könnte dann auch so aussehen:
Java:
public boolean equals(Object obj) {
  if(this == obj) {
    return true;
  }
  if(obj instanceof ThisClass) {
    return compareTo((ThisClass) obj)) == 0;
  }
  return false;
}
Die Hash-Methode von Eclipse mag zwar performant sein, aber ist sie auch immer effizient, also liefert sie stets so gute Werte, dass die Werte selbst als Suchindex dienen können, ohne auch nur einmal auf equals ausweichen zu müssen? Mehr effizientere Hashalgos sind afaik gleichbedeutend mit weniger Performance - z.B. eine CRC32-Implementation.
 

Dragonfire

Bekanntes Mitglied
Comparable (ohne "e" ;)) ist das Interface, welches für Keys einer SortedMap benötigt wird

Ach das böse "e", Comparable kenn ich aber^^
Nur das du es für eine SortedMap, also der TreeMap benutzen wolltest war mir nicht bewusst ...

Die Hash-Methode von Eclipse mag zwar performant sein, aber ist sie auch immer effizient, also liefert sie stets so gute Werte, dass die Werte selbst als Suchindex dienen können, ohne auch nur einmal auf equals ausweichen zu müssen? Mehr effizientere Hashalgos sind afaik gleichbedeutend mit weniger Performance - z.B. eine CRC32-Implementation.

Wird morgen gleich mal getestet ...
Ich denke ich werde eine Test-Umgebung erstellen ...

Hast du einen lokalen MySQL Server?
 

Dit_

Bekanntes Mitglied
Nur so am Rande...

Wenn man DB "updatet" dann muss man auch dafür sorgen, dass dein Cache auch aktualisiert wird. Die Frage ist, ob das wirklich so eine gute Idee ist, die Daten zu cachen. Vielleicht sollte man lieber überlegen wieso muss ich so oft die gleichen Daten aus der DB rauslesen? Ich meine du machst das nicht, weil die Daten sich geändert haben, sonst wäre cache sinnlos, sondern weil du die Daten noch mal irgendwo anders verwenden. Wenn die einen Datensatz rausliest, dann übergeben diesen an alle Objekte die es benötigen bzw. benötigen könnten... Hier könnte man zB sowas wie ZuständigkeitsKette-Pattern verwenden.

Ach ja... soweit ich weiss die Datenbanken haben auch so, solche Caches. zumindest liegen die bekannten Key-Value-Verweise im RAM so dass es ziemlich schnell gehen soll. Also es könnte sein dass du deinen Kode unnötig verkomplizierst und Geschwindigkeitsvorteil könnte sehr gering sein...

Wenn du es mit Patterns lösen willst, versuche mal mit Dekorierer. Sowas wie CacheDekorierer wäre doch ziemlich nett. Irgendwo habe ich schon ein Beispiel gesehen...


Wie gesagt, wollte die Sache nur von einer anderen Seite betrachten... hatte mal so ein ähnliches Problem... schließlich lag der Fehler am GesamtDesign der Anwendung :oops:
 

Dragonfire

Bekanntes Mitglied
Nur so am Rande...

Wenn man DB "updatet" dann muss man auch dafür sorgen, dass dein Cache auch aktualisiert wird. Die Frage ist, ob das wirklich so eine gute Idee ist, die Daten zu cachen. Vielleicht sollte man lieber überlegen wieso muss ich so oft die gleichen Daten aus der DB rauslesen? Ich meine du machst das nicht, weil die Daten sich geändert haben, sonst wäre cache sinnlos, sondern weil du die Daten noch mal irgendwo anders verwenden. Wenn die einen Datensatz rausliest, dann übergeben diesen an alle Objekte die es benötigen bzw. benötigen könnten... Hier könnte man zB sowas wie ZuständigkeitsKette-Pattern verwenden.

Ach ja... soweit ich weiss die Datenbanken haben auch so, solche Caches. zumindest liegen die bekannten Key-Value-Verweise im RAM so dass es ziemlich schnell gehen soll. Also es könnte sein dass du deinen Kode unnötig verkomplizierst und Geschwindigkeitsvorteil könnte sehr gering sein...

Wenn du es mit Patterns lösen willst, versuche mal mit Dekorierer. Sowas wie CacheDekorierer wäre doch ziemlich nett. Irgendwo habe ich schon ein Beispiel gesehen...


Wie gesagt, wollte die Sache nur von einer anderen Seite betrachten... hatte mal so ein ähnliches Problem... schließlich lag der Fehler am GesamtDesign der Anwendung :oops:

Die Pattern hören sich interessant an und ich denke ich habe sie sogar schon benutzt ;)
Konnte jetzt nur einen groben Blick darauf werfen ...
VIELEN DANK^^

Hier jetzt mal ein Testprojekt und meine Theorie bestätigt sich ...
Vieles ist noch nicht fertig, oder jetzt Quick und Dirt ;)

Bei 10 gleichzeitigen Aufrufen,
habe ich mit Cache:

ca. 578ms (relativ konstant sogar xD)

ohne:

ca. 900-1000ms

Dies ist natürlich nur grob, geht aber in die von mir erwartete Richtung.

implementiert ist die main-Methode in "storage.IntIntCache"

erbt die Klasse von DHashStore hat man den Cache,
DStore fragt immer von der Datenbank ab ;) (Zeile 14 in IntIntCache).

Datenbank-Einstellungen bitte in "datamanager.DMySQLManager" vornehmen.

Da dank SQL-Treiber das Archiv zu groß für das Forum ist, findet man es hier:
Zippyshare.com - Storage_20111204.zip
 
Zuletzt bearbeitet:

Marco13

Top Contributor
So ganz hab' ich nicht kapiert, worum es hier geht (habe aber, zugegeben, den abschweifenden(?) Teil nur überlogen und deswegen vielleicht was übersehen).

Kann man das nochmal kurz zusammenfassen? Du erstellst eine Map<Key,Value>, und es stört dich, dass du immer die Key-Objekte erzeugen musst? Woraus kann ein Key denn bestehen?
 

Dragonfire

Bekanntes Mitglied
So ganz hab' ich nicht kapiert, worum es hier geht (habe aber, zugegeben, den abschweifenden(?) Teil nur überlogen und deswegen vielleicht was übersehen).

Kann man das nochmal kurz zusammenfassen? Du erstellst eine Map<Key,Value>, und es stört dich, dass du immer die Key-Objekte erzeugen musst? Woraus kann ein Key denn bestehen?

Am besten schaust du Dir das einmal an:

Zippyshare.com - Storage_20111204.zip

Es wird eine HashMap<DKey, DValue> genutzt,
Ein DKey kann alles mögliche sein,
im Projektbeispiel besteht er aus zwei int-Werten.

Genauso gut kann es aber auch einen int,String Key geben,
oder einen String,String key,
oder String,int,int key ...
 

tuttle64

Bekanntes Mitglied
Am besten schaust du Dir das einmal an:

Zippyshare.com - Storage_20111204.zip

Es wird eine HashMap<DKey, DValue> genutzt,
Ein DKey kann alles mögliche sein,
im Projektbeispiel besteht er aus zwei int-Werten./QUOTE]

Im Beispiel werden auch diese zwei int-Werte verwendet, um equals() und hashCode() zu überschreiben.

Genauso gut kann es aber auch einen int,String Key geben,
oder einen String,String key,
oder String,int,int key ... /QUOTE]

Auch nur, wenn diverse Methoden und Klassen angepasst werden! Im Storage.zip ist der Key in der Klasse DIntIntKey hart kodiert!

Zur Performance: Für kleinere Tabellen wie in createData() mit MAX_DATA = 16 mag das Cachen eine gute Sache sein, wird die Tabelle aber gross, geht die Performance alleine bei der Dateiübertragung in den Keller.

Ich habe ein kleines Beispiel erstellt, wo immer mit den gleichen Objekt in einer HashMap gesucht werden kann. Nachdem ich mir aber den ganzen Strang durchgelesen habe, weiss ich gar nicht mehr, was Dein Problem ist.
 
Zuletzt bearbeitet:
S

Spacerat

Gast
@Tuttle64: Dateiübertragung... Da sagst du was... ;)
Ok... lassen wir die Datanbank mal selber cachen, das kann sie tun, sie selbst kann dann schneller auf Anfragen reagieren. Die Resultate dieser Anfragen und zwar einer jeden, werden zwar dann aus dem DB-Cache geholt, müssen aber dennoch einzeln zu den Requestern durch das Netzwerk gedrückt werden, möglicherweise auch per Multicast... egal.
Ein Cache wie ihn aber DragonFire vor hat soll DB-Serveranfragen verringern und das macht genau dann Sinn, wenn die Anwendung selber extrem viele identische Abfragen zu bewältigen hat (z.B. eine JSP- JSF- und/oder Servlet-Anwendung), weil dann nicht alle Resultate der Anfragen einzeln durch das Netzwerk gesaugt werden müssen.
Für die Demo hab' ich zusätzlich (auch mal eben Q&D) einen SortedCache gebaut. Bis zu 160*160 Abfragen unterscheiden sich aber die beiden Caches schon mal gar nicht, sind also gleich schnell. Wenn man bedenkt, dass die HashMap bei steigender Anzahl an Daten langsamer wird, kann man durchaus einen sortierten Cache empfehlen.
 

Dragonfire

Bekanntes Mitglied
Auch nur, wenn diverse Methoden und Klassen angepasst werden! Im Storage.zip ist der Key in der Klasse DIntIntKey hart kodiert!

Zur Performance: Für kleinere Tabellen wie in createData() mit MAX_DATA = 16 mag das Cachen eine gute Sache sein, wird die Tabelle aber gross, geht die Performance alleine bei der Dateiübertragung in den Keller.

Ich habe ein kleines Beispiel erstellt, wo immer mit den gleichen Objekt in einer HashMap gesucht werden kann. Nachdem ich mir aber den ganzen Strang durchgelesen habe, weiss ich gar nicht mehr, was Dein Problem ist.

Was meinst du mit hard kodiert?

Tabellengröße ist übrigens 16^2 ... alles andere hat mir jetzt zu lange gedauert xD
Und genau aus dem Grund der Datenübertragung cache ich ja ...

Kannst du dein Beispiel hochladen?

Was mir halt noch nicht gefällt ist die Erzeugung von neuen DIntIIntKeys bei jedem get Aufruf ...
Aber für die Implementierung des Keypools hatte ich noch keine Zeit^^

@Tuttle64: Dateiübertragung... Da sagst du was... ;)
Ok... lassen wir die Datanbank mal selber cachen, das kann sie tun, sie selbst kann dann schneller auf Anfragen reagieren. Die Resultate dieser Anfragen und zwar einer jeden, werden zwar dann aus dem DB-Cache geholt, müssen aber dennoch einzeln zu den Requestern durch das Netzwerk gedrückt werden, möglicherweise auch per Multicast... egal.
Ein Cache wie ihn aber DragonFire vor hat soll DB-Serveranfragen verringern und das macht genau dann Sinn, wenn die Anwendung selber extrem viele identische Abfragen zu bewältigen hat (z.B. eine JSP- JSF- und/oder Servlet-Anwendung), weil dann nicht alle Resultate der Anfragen einzeln durch das Netzwerk gesaugt werden müssen.
Für die Demo hab' ich zusätzlich (auch mal eben Q&D) einen SortedCache gebaut. Bis zu 160*160 Abfragen unterscheiden sich aber die beiden Caches schon mal gar nicht, sind also gleich schnell. Wenn man bedenkt, dass die HashMap bei steigender Anzahl an Daten langsamer wird, kann man durchaus einen sortierten Cache empfehlen.

Müsste man mal größere Tests laufen lassen, ich kenn mich mit SortedCaches nicht aus ...
Kannst du deine Klasse hochladen?

Können ja daraus ein Wettbewerb machen ;)

Müssten dann nur ein Interface schreiben und ein wenig aufräumen ...
 

tuttle64

Bekanntes Mitglied
Was meinst du mit hard kodiert?.

Die zwei ints sind in der Klasse DIntIntKey hart kodiert d.h. wenn Du als Schlüssel int, String oder drei ints verwendest muss Du entweder die Klasse anpassen oder Du schreibst eine neue Klasse.

Tabellengröße ist übrigens 16^2 ... alles andere hat mir jetzt zu lange gedauert xD Und genau aus dem Grund der Datenübertragung cache ich ja ...

Das ist auch nicht gerade viel.

Kannst du dein Beispiel hochladen?

Code:
import java.util.HashMap;
import java.util.Map;

public class KeyExample {
	public static void main(String[] args) {
		Map<KeyObj, ValObj> map = new HashMap<KeyObj, ValObj>();
		KeyObj k1 = new KeyObj(1, "eins");
		ValObj v1 = new ValObj("harry", 27);
		KeyObj k2 = new KeyObj(5, "fuenf");
		ValObj v2 = new ValObj("johnny", 45);
		map.put(k1, v1);
		map.put(k2, v2);
		
		System.out.println(map.get(k1).toString());
		KeyObj suchKey = new KeyObj(1, "eins");
		System.out.println(map.containsKey(suchKey));
		suchKey.setKeyObj(5, "fuenf");
		System.out.println(map.containsKey(suchKey));
	}
}

Die obige HashMap speichert als Value Personen mit den Fields Name und Alter. Als Key wird ein Objekt mit den Fields int, String verwendet. Als Beispiel werden die Personen harry und johnny in die HashMap gespeichert, danach wird ein suckKey generiert und nach dieser gesucht und true wird geliefert, da (1, "eins") die Person harry findet. Für die nächste Suche wird kein neues Objekt erzeugt, sondern über setKey ein neuer Schlüssel gesetzt und auch dieser wird ebenfalls gefunden, in der Person von johnny. Das sollte das Problem lösen, welches Du in Deinem ersten Post geschrieben hast.
 

Dragonfire

Bekanntes Mitglied
Die zwei ints sind in der Klasse DIntIntKey hart kodiert d.h. wenn Du als Schlüssel int, String oder drei ints verwendest muss Du entweder die Klasse anpassen oder Du schreibst eine neue Klasse.
Korrekt,
für einen String,Int Key brauche ich eine neue Klasse, was ich aber verkraften kann ;)



Die obige HashMap speichert als Value Personen mit den Fields Name und Alter. Als Key wird ein Objekt mit den Fields int, String verwendet. Als Beispiel werden die Personen harry und johnny in die HashMap gespeichert, danach wird ein suckKey generiert und nach dieser gesucht und true wird geliefert, da (1, "eins") die Person harry findet. Für die nächste Suche wird kein neues Objekt erzeugt, sondern über setKey ein neuer Schlüssel gesetzt und auch dieser wird ebenfalls gefunden, in der Person von johnny. Das sollte das Problem lösen, welches Du in Deinem ersten Post geschrieben hast.
Es hat ja wer schon die Idee mit dem SuchKey vorgeschlagen ...
man müsste halt nur einen Pool, oder so machen,
da die setter nicht synchronisiert sind, bzw. die get Methode und ich von mehreren Threads dafrauf zugreife ...
 

Dragonfire

Bekanntes Mitglied
Abgesehen von Synchronize, was ist, wenn die Tabelle auf der DB geändert wird?

Dies ist nicht vorgesehen ;)
Selbst wenn wäre es kein Problem ...

Entweder resetet man komplett den Cache wenn man dies irgendwie mitbekommt,
oder muss halt nur den einen Schlüssel aktualisieren (kommt darauf an wie man von dem UPDATE informiert wird).

Die Daten in der Datenbank ändern sich aber gar nicht bis selten, von daher ist dies nicht relevant.
 

schalentier

Gesperrter Benutzer
Ich glaube, du betrachtest das Problem irgendwie falsch:

1. Man sollte immer trennen zwischen einem fachlichen und einem technischen Primaerschlussel (in der DB).

2. der technische Schluessel ist am einfachsten ein int und auf jeden Fall eineindeutig (z.B. sequenzielle ID). Damit kannst du Integer.MAX_VALUE viele Saetze pro Tabelle speichern. Wenn das nicht reicht, nimm ein long.

3. Ein Datensatzcache kann manchmal sinnvoll sein, im allgemeinen bringt der nicht viel. Wenn dann solltest du fuer jede Tabelle eine HashMap<Integer, PersistentObject> oder sowas verwenden. Beim direkten Zugriff ueber den technischen Schluessel, kannste dann in der HashMap nachguggen.

4. Was du mit einen DKeys versuchst, ist nichts anderes als ein Datenbank-Index ueber mehrere Spalten einer Tabelle. Allerdings sollte man das einfach die DB machen lassen - dort stecken viele Personenjahre an Entwicklungszeit drin. Schneller wirst du das niemals hinbekommen.

5. In einer normalen Anwendungsarchitektur ist eine dicke, und physikalisch kurze Leitung zwischen Application- und Datenbank Server. Wenn die Zeit, die eine Antwort auf dieser Strecke braucht, zu viel ist, ist wohl irgendwas anderes defekt.
 

Dragonfire

Bekanntes Mitglied
Ich glaube, du betrachtest das Problem irgendwie falsch:

1. Man sollte immer trennen zwischen einem fachlichen und einem technischen Primaerschlussel (in der DB).

2. der technische Schluessel ist am einfachsten ein int und auf jeden Fall eineindeutig (z.B. sequenzielle ID). Damit kannst du Integer.MAX_VALUE viele Saetze pro Tabelle speichern. Wenn das nicht reicht, nimm ein long.

3. Ein Datensatzcache kann manchmal sinnvoll sein, im allgemeinen bringt der nicht viel. Wenn dann solltest du fuer jede Tabelle eine HashMap<Integer, PersistentObject> oder sowas verwenden. Beim direkten Zugriff ueber den technischen Schluessel, kannste dann in der HashMap nachguggen.

4. Was du mit einen DKeys versuchst, ist nichts anderes als ein Datenbank-Index ueber mehrere Spalten einer Tabelle. Allerdings sollte man das einfach die DB machen lassen - dort stecken viele Personenjahre an Entwicklungszeit drin. Schneller wirst du das niemals hinbekommen.

5. In einer normalen Anwendungsarchitektur ist eine dicke, und physikalisch kurze Leitung zwischen Application- und Datenbank Server. Wenn die Zeit, die eine Antwort auf dieser Strecke braucht, zu viel ist, ist wohl irgendwas anderes defekt.

1. Hast du da irgendwas zum nachlesen, was bedeutet hier fachlich/technisch?

2. Wie macht man es denn mit zusammengesetzen Schlüsseln?

3. Dann muss ich ja wieder ein ein neues Integer-Objekt erzeugen :-(

4. Ich orientiere mich nur am Modell der Datenbank .. theoretisch soll man auch von anderen Quellen lesen können.

5. Ich merke glaubig ich habe mich im Forum vertan xD Wie schonmal erkannt handelt es sich um einen Serverapplikation, mit viel Speicher und vielen Threads^^


Naja, es gibt den schönen Spruch, hatte auch irgendwer mal in der Signatur,
der grob sagt, hör auf in JAVA zu optimieren xD
 

schalentier

Gesperrter Benutzer
1. Hast du da irgendwas zum nachlesen, was bedeutet hier fachlich/technisch?

2. Wie macht man es denn mit zusammengesetzen Schlüsseln?

3. Dann muss ich ja wieder ein ein neues Integer-Objekt erzeugen :-(

4. Ich orientiere mich nur am Modell der Datenbank .. theoretisch soll man auch von anderen Quellen lesen können.

5. Ich merke glaubig ich habe mich im Forum vertan xD Wie schonmal erkannt handelt es sich um einen Serverapplikation, mit viel Speicher und vielen Threads^^

1. Mit technischer Id mein ich eine extra Spalte in der Tabelle, die nichts mit der Fachlichkeit zu tun hat. Die gehoert in jede Tabelle, ausser in M:N Zwischentabellen. Der Name ist im Idealfall immer gleich, z.B. object_id oder einfach id. Diese Spalte ist gleichzeitig der Primaerschluessel der Tabelle.

2. Zusammengesetzte Schluessel werden immer als Indexe in der Tabelle hinterlegt. Die Datenbank macht dann aus diesen Indexen Hashwerte und Suchen in der DB per SQL nutzt diese, sofern alle Spalten zu einem Index im WHERE Teil vorhanden sind.

3. Willkommen in der Java Welt. Es gibt noch rein auf primitiven Datentypen basierende Implementationen von HashMaps. Find der Link aber grad nicht mehr.

4. Man koennte die anderen Quellen einfach in eine DB umkopieren. Oder du willst eine Datenbank nachprogrammieren, dann lohnt sich vielleicht ein Blick auf Hypersonic, H2, Derby oder wie sie alle heissen (alles inmemory SQL Datenbanken).

5. Noe, bist hier schon richtig, aber Datenbanken sind halt genau dafuer gemacht ;-).
 

Dragonfire

Bekanntes Mitglied
5. Noe, bist hier schon richtig, aber Datenbanken sind halt genau dafuer gemacht ;-).

Für diesen Fall bin ich mir halt nicht sicher,
weil bei einem Server zu viele Anfragen mit vor allem große Daten schon ein wenig die Performance drücken ...

Für normale Anwendungsprogramm stimme ich Dir voll zu^^

Des Weiteren wird die DB noch für andere Dinge genutzt und ich habe ein wenig Angst,
dass diese dann leicht überlastet ist, was sich dann dank des guten Systems in einer etwas höheren Anfragezeit äußert und damit längere benötige Zeit beim Server zur Folge hätte.

Wie gesagt diskutieren wir hier, wie ich es so oft hier machen,
über Entwurf^^
Andere Meinungen sind mir wichtig und so lernt man viel ;)

Ich Schaue mir jetzt erstmal:
"Hypersonic, H2, Derby"
an, vielleicht haben diese neue Konzepte^^

Sollte es nicht all zu spät sein, versuch teste ich mal direkte Anfragen an der DB (ohne DKey) und auch noch mal das mit dem Suchkey ...
 
S

Spacerat

Gast
Langsam habe ich das Gefühl, als würden Dragonfire und ich an den Datenbankexperten vorbei reden. Man kann Anfragen wie gesagt, auf zwei Seiten cachen, einmal in der Anwendung und einmal auf dem Datenbankserver.
Nehmen wir z.B. einen Multicontent-Server, auf welchem 10 verschiedene Inhalte durch ein und dieselbe Anwendung (z.B. ein Forum) realisiert sind. Ein weiterer Server, meinetwegen sogar localhost, stellt dafür 10 verschiedene Datenbanken zur Verfügung. Der Weg aller DB-Anfragen ist für jede der 10 Anwendungen gleich: Anwendung, Netzwerk, Datenbank und zurück. Nun sind alle 10 Anwendungen mit sagen wir 100 Seitenaufrufen im Durchschnitt gleichzeitig besucht, pro Seitenaufruf mit ca. 5 von 10 identischen DB-Anfragen. 10 Seiten * 100 Aufrufe * 10 Anfragen entsprächen also 10000 Datenbankanfragen, die alle gleichzeitig durchs Netzwerk zur Datenbank und zurück müssen. Herrlich, wenn die Datenbank nun cached, die schnell gefundenen Daten müssen trotzdem noch zu ihren Anwendungen zurück und zwar durch den Flaschenhals Netwerk.
Natürlich macht es in diesem Szenario Sinn, wenn die Anwendungen die DB-Anfragen zusätzlich selbst cachen.
Hab' hier mal die Klassen für einen sortierten Cache angehängt (zusätzlichen Quelltexte einfach in's Beispielprojekt übernehmen).
Bei MAX_DATA = 16 ist die HashMap wohl doch schneller. Bei MAX_DATA = 160 aber erlebt man schon mal eine Überraschung und für MAX_DATA = 1600 muß bereits eine performantere Lösung der Datensatzerzeugung her.
 

schalentier

Gesperrter Benutzer
Der Cache gehoert zwischen Client und AppServer. Einmal generierte Seiten (HTML) werden zeitweise zwischengespeichert und direkt vom schnellen Apachen davor ausgeliefert.

Ich hab noch nie von einem Datenbankabfragencache in der Application gehoert. Eventuell sollte man das transparent in einem eignen JDBC Treiber realisieren? Dennoch kommt mir all das eher ungewoehnlich vor. Zumal das Beispiel etwas hinkt: Warum sollte man fuer zehn stark frequentierte Apps (100 Zugriffe gleichzeitig im Durchschnitt) nur einen AppServer und einen DBServer nutzen?
 

Dragonfire

Bekanntes Mitglied
Langsam habe ich das Gefühl, als würden Dragonfire und ich an den Datenbankexperten vorbei reden. Man kann Anfragen wie gesagt, auf zwei Seiten cachen, einmal in der Anwendung und einmal auf dem Datenbankserver.
Nehmen wir z.B. einen Multicontent-Server, auf welchem 10 verschiedene Inhalte durch ein und dieselbe Anwendung (z.B. ein Forum) realisiert sind. Ein weiterer Server, meinetwegen sogar localhost, stellt dafür 10 verschiedene Datenbanken zur Verfügung. Der Weg aller DB-Anfragen ist für jede der 10 Anwendungen gleich: Anwendung, Netzwerk, Datenbank und zurück. Nun sind alle 10 Anwendungen mit sagen wir 100 Seitenaufrufen im Durchschnitt gleichzeitig besucht, pro Seitenaufruf mit ca. 5 von 10 identischen DB-Anfragen. 10 Seiten * 100 Aufrufe * 10 Anfragen entsprächen also 10000 Datenbankanfragen, die alle gleichzeitig durchs Netzwerk zur Datenbank und zurück müssen. Herrlich, wenn die Datenbank nun cached, die schnell gefundenen Daten müssen trotzdem noch zu ihren Anwendungen zurück und zwar durch den Flaschenhals Netwerk.
Natürlich macht es in diesem Szenario Sinn, wenn die Anwendungen die DB-Anfragen zusätzlich selbst cachen.
Hab' hier mal die Klassen für einen sortierten Cache angehängt (zusätzlichen Quelltexte einfach in's Beispielprojekt übernehmen).
Bei MAX_DATA = 16 ist die HashMap wohl doch schneller. Bei MAX_DATA = 160 aber erlebt man schon mal eine Überraschung und für MAX_DATA = 1600 muß bereits eine performantere Lösung der Datensatzerzeugung her.

Du triffst den Nagel auf den Kopf^
Wie lange hat bei dir denn die Erzeugung von MAX_DATA 1600 gedauert oO
Hätte ich nicht gedacht, dann müsste ich mal schauen was ich für meinen Fall brauche ...
Nur zur Kontrolle:
Die HashMap ist langsamer, weil sie immer ein rehash machen muss und eventuell equals aufrufen muss,
das balanciere des Baums in der TreeMap is schneller, oder woran liegt der Performancegewinn bei hohen Daten.

Apropo,
wenn du die compareTo Methode in SortedIntIntCache.IntIntKey überschreibst, sollte es noch schneller sein ;)

Der Cache gehoert zwischen Client und AppServer. Einmal generierte Seiten (HTML) werden zeitweise zwischengespeichert und direkt vom schnellen Apachen davor ausgeliefert.

Ich hab noch nie von einem Datenbankabfragencache in der Application gehoert. Eventuell sollte man das transparent in einem eignen JDBC Treiber realisieren? Dennoch kommt mir all das eher ungewoehnlich vor. Zumal das Beispiel etwas hinkt: Warum sollte man fuer zehn stark frequentierte Apps (100 Zugriffe gleichzeitig im Durchschnitt) nur einen AppServer und einen DBServer nutzen?

Es geht hier um einen Spezialfall, normalerweise würde man ja sonst die Last auf einzelne Server verteilen und nochmal ... es geht hier um einen Server und den Flaschenhals Netzwerk und das Beispiel vom Spacerat ist gut gewählt.
 

bERt0r

Top Contributor
Wenn das Netzwerk dein Flaschenhals ist, dann pack dir halt die ganze DB z.B als h2 DB lokal auf den Server. Das ist sicher performanter als früher oder später die ganze DB als Hashmap zu laden.
 

Dragonfire

Bekanntes Mitglied
Wenn das Netzwerk dein Flaschenhals ist, dann pack dir halt die ganze DB z.B als h2 DB lokal auf den Server. Das ist sicher performanter als früher oder später die ganze DB als Hashmap zu laden.

Das cool ist ja, dass man in meinem Fall eben nicht alles braucht und die HashMap, TreeMap, der Cache nach oben begrenzt ist ;)

Aber ein Wettbewerb finde ich echt cool xD
Wie lädt man am schnellsten was von einer Datenbank,
mit den von mir vorgegeben Bedingungen:

+ bestimmte Tabellengröße (da bei vielen Daten TreeMap besser, sonst HashMap
+ mehrere fest Zugriffe (zurzeit haben wir ja 10 Threads, wenn ich mich nicht irre im Beispiel)
+ nur bestimme Daten werden benötigt, man weiß aber erst ja jedem Neustart des Servers was (die Begrenzung des Caches)

Dann sieht man eventuell auch den Gewinn^^
 
S

Spacerat

Gast
Der Cache gehoert zwischen Client und AppServer.
Wie bitte? Warum sollte man Thread-Seiten eines Forums z.B. cachen wollen? Weil man davon ausgeht, dass eh' keiner antwortet? Da hinkt jedenfalls die Logik.
Warum sollte man fuer zehn stark frequentierte Apps (100 Zugriffe gleichzeitig im Durchschnitt) nur einen AppServer und einen DBServer nutzen?
Weil es geht, wenn man nicht an der falschen Stelle spart und an der richtigen Stelle zwischenspeichert.
[edit]Logisch... der Abfragecache gehört natürlich in den DB-Treiber, welcher aber widerum teil der Anwendung ist und deswegen auch auf der Anwendungsseite des Netzwerk-Flaschenhalses zu finden ist.[/edit]
 
Zuletzt bearbeitet von einem Moderator:

schalentier

Gesperrter Benutzer
Wie bitte? Warum sollte man Thread-Seiten eines Forums z.B. cachen wollen?

Weil sich auf den Seiten 1 und 2 dieses Threads selten was aendern wird? Natuerlich gehoert zu einem Cache auch eine entsprechende Logik des Invalidierens. Dazu habt ihr bei eurem Hashmap Cache aber auch noch nicht viel gesagt.

So macht man das mit Rails (Punkt 1.1 Page Caching). Geht sicherlich ganz aehnlich mit Java Mitteln (JSF, o.ä.).

Im uebrigens musst in der Implementierung auch aufpassen, dass alles korrekt synchronisiert ist, wenn 10 Anwendungen auf den gleichen Hashmap Cache zugreifen.

Kennt ihr Memcached? Dafuer gibts auch ne Java API. Eventuell is das, was ihr sucht.

Edit: Zum "weil es geht": Rechne dir die Kosten aus, die ein Entwickler braucht, um eure Sache einigermassen stabil zum Laufen zu bekommen und rechne dann die Kosten fuer einen zweiten Postgres Server aus...
 

schalentier

Gesperrter Benutzer
Uebrigens ist zu einem aehnlichen Thema ein Artikel in der iX 12 (Dezember 2011) zu finden. Da gehts um stern.de mit 16 Mrd Anfragen pro Monat, also 10-30000 Requests pro Sekunde.

Um von theoretisch notwendigen 6000 auf 60 Server zu kommen, wird zwischen statischen und dynamischen Anfragen unterschieden. Durch weiteres Caching und automatisiertes Optimieren von PHP kann die Anzahl auf 6 gesenkt werden.

Der Einsatz von Memcached bringt dann nochmal 30% Ersparnis (noch 4 Server). Diese Zahlen haengen natuerlich von der konkreten Anwendung ab, aber die Groessenordnungen gelten vermutlich weitgehend analog auch fuer andere Anwendungsfaelle.
 
S

Spacerat

Gast
Wow... des sind schon mal Zahlen... so kenn' ich die auch. XD (Thema: An falscher Stelle sparen). Hier wurden anscheinend vorhandene APIs (von Entwicklern erstellt) korrekt genuzt bzw. implementiert. Naja... wenigstens kommen jetzt keine Fragen mehr, warum man 10 Foren auf einen Server bekommen will ;). MemCached kenne ich persönlich noch nicht, aber ich seh's mir mal an. Sicher kann man in Java noch viel besser optimieren als in PHP XD, andererseits... 6000 notwendige Server auf nur 4 reduzieren ist schon 'ne einzigartige Leistung.
 

Dragonfire

Bekanntes Mitglied
@Spacerat:
Ich würde nochmal kurz mich zitieren.


"Wie lange hat bei dir denn die Erzeugung von MAX_DATA 1600 gedauert oO
Hätte ich nicht gedacht, dann müsste ich mal schauen was ich für meinen Fall brauche ...
Nur zur Kontrolle:
Die HashMap ist langsamer, weil sie immer ein rehash machen muss und eventuell equals aufrufen muss,
das balanciere des Baums in der TreeMap is schneller, oder woran liegt der Performancegewinn bei hohen Daten."

Im Internet findet man nur, dass TreeMap sortiert und HashMap schneller sein soll ...
Dieser Test war interessant:
The Final Performance Testing Example
 
S

Spacerat

Gast
MAX_DATA=1600? Da funktionierte ja nicht einmal die Erstellung der Daten -> OutOfMemoryError.
Die Überraschung war aber bereits bei 160 deutlich. Während die HashMap bei MAX_DATA=16 knapp doppelt so schnell war als die TreeMap (ca. 700ms zu 1300ms) benötigen beide Maps bei MAX_DATA=160 in etwa die gleiche Zeit von knapp 4000ms.
Mal sehen, ob ich die Erklärung dafür so einigermassen zusammen bekomme. Die HashMap ist solange schneller, wie sie per "hashCode()" verschiedene Hashgruppen erstellen kann, worauf anschliessend eine Binärsuche angewendet werden kann, genau so wie bei der TreeMap, nur mit einem viel kürzeren "Schlüssel", der erstens eine feste Länge (4 Bytes) hat und 2. ein primitiver Datentyp (int) ist. Erst wenn die HashMap zu viele Elemente in eine Hashgruppe legen muss, weil "hashCode()" nicht effizient genug arbeitet, wird sie gegenüber der TreeMap um einiges langsamer, weil innerhalb einer solchen Gruppe nur noch iterrativ (per "equals()") gesucht werden kann.
Grad' fällt mir noch ein, dass ich gar nicht genau weis, wie beide Maps auf die Veränderung eines Schlüssels reagieren. Evtl. muß ein veränderter Schlüssel entnommen und erneut eingefügt werden, damit er an die richtige Stelle des Sets gelangt. Wenn dem so ist, dürfte das der Hauptgrund dafür sein, warum die Schlüssel einer Map möglichst Immutable sein sollten.
 

Dragonfire

Bekanntes Mitglied
Stimmt
Code:
hashCode()
ist ja beschränkt auf den Integer-Wertebereich von -2^31 .. 2^31 ...
aber ich denke ich sollte unter dieser Anzahl bleiben ...

Übrigens,
ist zurzeit HashMap genau so schnell wie Hashtable^^
Das ist ziemlich interessant ...
 
S

Spacerat

Gast
Stimmt
Code:
hashCode()
ist ja beschränkt auf den Integer-Wertebereich von -2^31 .. 2^31 ...
aber ich denke ich sollte unter dieser Anzahl bleiben ...
Was bleibt dir anderes übrig? Sämtliche Collections sind wegen der allgegenwärtigen "size()"-Methode auf eine Anzahl von MAX_INTEGER (2^31) beschränkt - ob in die Maps Elemente über dieses Limit hinaus passen bzw. passen dürfen, scheint jedoch nirgendwo klar definiert zu sein. Die Problematik bei der HashMap bleibt aber die Hashcodes so zu ermitteln, dass möglichst viele Hashgruppen entstehen und dadurch die Verwendung von "equals()" verringert wird. Bei steigender Schlüssellänge wird die Ermittlung effektiver Schlüssel jedoch immer schwieriger was zur Folge hat, dass "equals()" immer öfter benutzt werden muß. Fazit: Man kann sich aussuchen was man als effizienter erachtet - eine leistungsfähige Hashfunktion implementieren oder von vorne herein eine stete Binärsuche durch sortierte Collections ermöglichen.
 

bERt0r

Top Contributor
Ich hab mir mal deinen Code angeschaut:
DMySQLManager.INSTANCE
.quickInsert("INSERT INTO intinttable (a,b,v) VALUES ("
+ i + "," + j + "," + i + "." + j + ")");
Bei sowas ist es ja kein Wunder dass das ganze lahmt. Das ist aber nicht die schuld der datenbank, sondern deine Art SQL Strings zu erstellen. Nimm einen StringBuilder.
 

Dragonfire

Bekanntes Mitglied
Ich hab mir mal deinen Code angeschaut:

Bei sowas ist es ja kein Wunder dass das ganze lahmt. Das ist aber nicht die schuld der datenbank, sondern deine Art SQL Strings zu erstellen. Nimm einen StringBuilder.


In der Regel stimme ich dir zu,
deswegen habe ich es mal ausprobiert:

Java:
                StringBuilder buff = new StringBuilder();
		for (int i = 1; i < MAX_DATA; i++) {
			for (int j = 1; j < MAX_DATA; j++) {
				buff.delete(0, buff.length());
				buff.append("INSERT INTO intinttable (a,b,v) VALUES (");
				buff.append(i);
				buff.append(",");
				buff.append(j);
				buff.append(",");
				buff.append(i);
				buff.append(".");
				buff.append(j);
				buff.append(")");
				DMySQLManager.INSTANCE.quickInsert(buff.toString());
				// DMySQLManager.INSTANCE
				// .quickInsert("INSERT INTO intinttable (a,b,v) VALUES ("
				// + i + "," + j + "," + i + "." + j + ")");
			}
		}

Nach erste Test scheint es gleich schnell zu sein, wenn nicht ein wenig
langsamer zu sein ...
Komisch, entweder optimiert das der Compiler dies weg,
oder ich mache was falsch ...
(StringBuffer gleicher Effekt)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
F Große Datenmengen effizient programmieren Allgemeine Java-Themen 51
K Große JSON-Dateien schnell und effizient verarbeiten Allgemeine Java-Themen 16
T Daten effizient verwalten Allgemeine Java-Themen 4
H Sehr viele Threads effizient Verwalten Allgemeine Java-Themen 13
T [RXTX] GPS-Maus (Comport) effizient auslesen Allgemeine Java-Themen 6
B Daten effizient ein- und auslagern Allgemeine Java-Themen 7
S Algorithmus Problem. Rechtecke effizient auf Spielfeld anordnen. Allgemeine Java-Themen 7
Ark Arkussinus effizient berechnen Allgemeine Java-Themen 12
T WeakHashMap: Wie "null" effizient abfangen? Allgemeine Java-Themen 5
J Datei Inhalt vergleichen (schnell & effizient!) Allgemeine Java-Themen 10
Zrebna Zuverlässiges Automatisiertes Testen im eigenem Software-Unternehmen aufsetzen - How to? Allgemeine Java-Themen 12
C Frage zu eigenem TableCellRenderer Allgemeine Java-Themen 11
MiMa Log4j in Dateien mit eigenem Namen schreiben Allgemeine Java-Themen 3
D JAVA Basiertes Spiel aus dem Internet in eigenem Client laden Allgemeine Java-Themen 3
N ArrayList in eigenem Object nicht richtig serialisierbar Allgemeine Java-Themen 14
T AES-Verschlüsselung mit eigenem 256 Bit Schlüssel Allgemeine Java-Themen 12
M Über Liste verschiendene JComponents mit eigenem implementierten Interface ansprechen Allgemeine Java-Themen 7
K Programm startet nur auf eigenem Rechner??? Allgemeine Java-Themen 6
DStrohma Jede node in JTree mit eigenem Icon Allgemeine Java-Themen 7
M Eigenem Dateiformat Icon zuweisen Allgemeine Java-Themen 6
S Problem mit eigenem DatenTyp. HILFE!!! Allgemeine Java-Themen 4
M jdbc treiber (h2) mit eigenem ClassLoader laden Allgemeine Java-Themen 4
D Abstruse Probleme mit eigenem replace Algorithmus Allgemeine Java-Themen 11
R HashSet mit eigenem Objekt als Key Allgemeine Java-Themen 10
A jpeg Files mit eigenem Programm öffnen Allgemeine Java-Themen 4
F Probleme mit eigenem Plugin-System Allgemeine Java-Themen 3
H externe JARs in eigenem Programm-Jar einbinden. Allgemeine Java-Themen 5
F "source not found" in eigenem Projekt mit eigenen Allgemeine Java-Themen 2
W Externes Programm beenden mit eigenem Programm beenden Allgemeine Java-Themen 7
D Programm mit eigenem ClassLoader funktioniert nicht Allgemeine Java-Themen 12
K KeyEvent in eigenem Component geht nicht Allgemeine Java-Themen 3
R Problem beim speichern von eigenem objekt Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben