Java Zwei Zahlen in einer Speichern, sowie Fragen zur Performance bei Arrays

klausschreiber

Well-known member
ID: 162475
L
6 Mai 2006
247
8
Hallo,

die erste Frage ist jetzt nicht unbedingt javaspezifisch, aber ich stelle sie trotzdem mal hier dazu. Ich habe zwei Zahlen, die jeweils bis 1,7 Mio groß werden können, also jeweils bis zu 21 Bits benötigen. Einen Datentyp mit 21 Bit gibt es ja nicht, sondern der nächstgrößere Datentyp wäre Int mit 32 Bit. Ich könnte die beiden Zahlen natürlich zusammengefasst als ein Int und ein Short speichern, sodass nur 46 Bit, anstatt 64 Bit benötigt würden (oder in einem Int, einem Byte und zwei Booleans :ugly:), aber ich denke mal, das ist performancemäßig mit den ganzen nötigen Bitshifts und Konjunktionen auch nicht wirklich so der Hit, oder?

Ich glaube zwar kaum, aber es gibt nicht zufällig einen Trick, zwei 1,7 Mio große Zahlen so zusammen zu fassen, dass sie in 32 Bit reinpassen, oder?

Bevor die Frage kommt: Bei kleinen Datenmengen ist der Speicherplatz natürlich irrelevant, aber das soll ein Array werden, wo 32bit zu 64bit mehrere Megabyte ausmachen und das Array soll im Arbeitsspeicher eines Handys vorgehalten werden, sodass ich es schon gerne so klein wie möglich hätte. Die Performance spielt aber auch eine Rolle, weil durchaus in einem Durchlauf tausende bis womöglich hunderttausende Lookups stattfinden können.


Dann noch meine zweite Frage:
Wenn ich in Java einen Wert in einem zweidimensionalem Array abrufe, z.B. wert[5][3], ist das dann ein Lookup oder muss Java da erstmal nach dem 5. Eintrag schauen und dann als nächstes erst nach der 3?


Danke und Gruß,
Klaus
 
aber ich denke mal, das ist performancemäßig mit den ganzen nötigen Bitshifts und Konjunktionen auch nicht wirklich so der Hit, oder?
erfasst, die Laufzeit wäre grottig, immerhin müsstest du für jede Operation die Daten erst wieder Shiften.

Ich glaube zwar kaum, aber es gibt nicht zufällig einen Trick, zwei 1,7 Mio große Zahlen so zusammen zu fassen, dass sie in 32 Bit reinpassen, oder?
nein, da jede der Zahlen schon mindestens 20 Bit benötigt.

das soll ein Array werden, wo 32bit zu 64bit mehrere Megabyte ausmachen und das Array soll im Arbeitsspeicher eines Handys vorgehalten werden
na dann läuft in deinem Konzept eh schon einiges schief, mehrere Megabyte? Im Ram eins Handys? Bedenke, dass der der Ram nicht dir alleine gehört, da laufen noch viele weitere "Prozese" oder Apps.

Dann noch meine zweite Frage:
Wenn ich in Java einen Wert in einem zweidimensionalem Array abrufe, z.B. wert[5][3], ist das dann ein Lookup oder muss Java da erstmal nach dem 5. Eintrag schauen und dann als nächstes erst nach der 3?
korrekt erst ein Lookup nach 5, was wieder zu einem Array wird und dann nach der 3, dies wird benötigt damit Java zur Laufzeit den ArrayIndexOutOfBounds-Check machen kann.
 
Danke für deine Antwort
na dann läuft in deinem Konzept eh schon einiges schief, mehrere Megabyte? Im Ram eins Handys? Bedenke, dass der der Ram nicht dir alleine gehört, da laufen noch viele weitere "Prozese" oder Apps.
Naja, das Programm ist schon für neuere Smartphones gedacht. Da haben die Besseren ja 512 MB Ram und etwas abgespeckte, wie das HTC Wildfire, haben auch noch über 300 MB. Ich denke mal, die meisten neueren Android Handys (darauf soll es laufen), kommen damit klar.

Ich programmiere einen Pokerodds Rechner und möchte die Headsupergebnisse in einer Lookup Table speichern, weil diese wohl am häufigsten benötigt werden und mehrere Millionen bis 100 Millionen Berechnungen auf einem Handy wohl auch nicht das Wahre sind.

Wenn ich das Ganze in zwei Integer Arrays speichere, brauche ich insgesamt 6,7 MB. Theoretisch kann ich den User ja auch wählen lassen, ob er eine Lookup Table nutzen will.

korrekt erst ein Lookup nach 5, was wieder zu einem Array wird und dann nach der 3, dies wird benötigt damit Java zur Laufzeit den ArrayIndexOutOfBounds-Check machen kann.
schade. Dann sind wohl zwei Arrays besser (bei zwei Ints), als ein Zweidimensionales, oder?
Also
Code:
int1[3785];
int2[3785];
sollte schneller sein als
Code:
int[1][3785];
int[2][3785];
oder?

Alternativ kann man die beiden Zahlen in einem Long (64bit) Array speichern und dann einmal Shiften und eine logische Konjunktion machen. Aber ich denke, ein zusätzlicher Table Lookup ist schneller als ein Bitshift und eine Konjunktion?


Gruß,
Klaus
 
Ich programmiere einen Pokerodds Rechner und möchte die Headsupergebnisse in einer Lookup Table speichern, weil diese wohl am häufigsten benötigt werden und mehrere Millionen bis 100 Millionen Berechnungen auf einem Handy wohl auch nicht das Wahre sind.
Mein letztes Pokerspiel is schon ne Weile her... Heads-up sind die Wahrscheinlichkeiten, wie viel Chance du auf einen Gewinn hast, wenn du zu Beginn nur deine zwei Hole Cards hast, oder? Diese Tabelle könnte man doch vorberechnen lassen. Also nicht live berechnen. Immerhin is das nur Funktion
f: {{kreuz, herz, pik, karo} × {2, 3, 4, 5, 6, 7, 8, 9, 10, b, d, k, a}}[sup]2[/sup] × {2, ...} -> [0...1] abbildet.

Endlich viele Farben (4), endlich viele Zahlen/Buchstaben (13), genau zwei Hole Cards, endlich viele Spieler (sagen wir mal 9, also maximal 10 Spieler am Tisch), macht 24.336 Möglichkeiten.
Sind also mit nem Float grade mal 95 kB, was du Speicher brauchst.
 
Danke für deine Antwort.

HeadsUp bedeutet erstmal nur, dass nur noch zwei Spieler im Spiel sind. Aber ja, ich möchte mithilfe dieser Tabelle die Gewinnwahrscheinlichkeiten errechnen, wenn zwei Spieler nur ihre beiden Karten haben.

Wie du auf die Zahlen kommst, ist mir aber nicht ganz klar. Es gibt 4 Farben und 13 Zahlen, also insgesamt 52 Pokerkarten. Eine Starthand besteht immer aus 2 Karten. Es ist also ein Ziehen ohne Zurücklegen ohne Reihenfolge. Das ergibt 1326 mögliche Starthände. Bei zwei Spielern sind das dann 878.475 verschiedene Kombinationen. Diese mit 8 Byte multipliziert ergeben etwa 6,7 MB.

Einfach die Wahrscheinlichkeit, zu Gewinnen, in einen float zu speichern, reicht nicht, da ich auch die Verlustwahrscheinlichkeit und die Wahrscheinlichkeit für ein Unentschieden brauche (wobei ich einen von den 3 Werten aus dem anderen beiden berechnen kann).
Zudem brauch ich auch die genauen Zahlen, wie oft die Hand gewinnt, da das Programm nicht nur z.B. AhKs gegen TsTd rechnen können soll, sondern auch mit Ranges also z.B. AK gegen {TT, 99, 88, T8} und so Sachen wie "Mit welchen Karten bin ich gegen die Range {TT, 99, T8} besser als 40%". Wegem letzteren ist das Ganze auch zeitkritisch, da da doch ein paar mehr Lookups anfallen können.

Bei mehr als zwei Spielern komme ich nicht drum herum, alle Möglichkeiten durchzulaufen und halt mindestens eine Millionen Möglichkeiten zu betrachten. Allerdings werden zur Handerkennung (ob Paar, Straße usw.) auch LookUp Tables zu Hilfe genommen (auch wenn man leider aus Platzgründen nicht einfach direkt die Hand für die 7 Karten speichern kann:(), sodass mein Computer ohne Aufteilung auf mehrere Threads etwa 25 Mio Durchläufe pro Sekunde schafft. Da sollte ein modernes Handy mit 1GHz auch ein paar Millionen schaffen. Und wenn die Fragestellung so kompliziert ist, dass die Anzahl der Durchläufe in die Milliarden geht, muss man halt auf Monte-Carlo zurückgreifen, was der User frei wählen können wird.

Ui, jetzt ist es doch wieder viel zu viel Text geworden^^.

Gruß,
Klaus
 
HeadsUp bedeutet erstmal nur, dass nur noch zwei Spieler im Spiel sind.
Ah ok, dann lag ich falsch.
Es ist also ein Ziehen ohne Zurücklegen ohne Reihenfolge. Das ergibt 1326 mögliche Starthände. Bei zwei Spielern sind das dann 878.475 verschiedene Kombinationen. Diese mit 8 Byte multipliziert ergeben etwa 6,7 MB.
Mein Vorschlag is ja, dass du nicht die Möglichkeiten speicherst, sondern die Gewinnwahrscheinlichkeiten. (Außer, du willst die Möglichkeiten explizit auflisten, dann geht meine Idee natürlich nicht.)

Ich würde beim Heads-up auf folgendes kommen (Texas Hold'em-Variante, mit den anderen kenn ich mich ned aus):
f: [({kreuz, herz, pik, karo} × {2, 3, 4, 5, 6, 7, 8, 9, 10, b, d, k, a})[sup]2[/sup]][sup]2[/sup] × ({null, ({kreuz, herz, pik, karo} × {2, 3, 4, 5, 6, 7, 8, 9, 10, b, d, k, a})})[sup]5[/sup] -> [0...1]
Jeder Spieler hat 2 Karten (52[sup]2[/sup]) und es liegen zwischen 0 und 5 Karten auf dem Tisch (oben hab ich angenommen, die Reihenfolge der Community Cards wäre wichtig, is sie aber nicht, ggf. kan man da sparen), sind aber leider viiiel zu viele Möglichkeiten: 3.057.684.857.746.688 8O

Also is in dem Fall live berechnen einfacher. Muss ich aber sagen, Poker-Mathematik hab ich ned drauf. FOLD ;)

Zu dieser Aussage:
[...]sodass mein Computer ohne Aufteilung auf mehrere Threads etwa 25 Mio Durchläufe pro Sekunde schafft. Da sollte ein modernes Handy mit 1GHz auch ein paar Millionen schaffen.
Eine CPU mit 2 GHz is nicht doppelt so schnell, wie eine mit 1 GHz! Das is die Laienannahme, die aber nicht stimmt.

Es kommt drauf an, welche Operationen die CPU anbietet und wie schnell diese implementiert sind (hardwareseitig!). Ein DSP wird wohl wesentlich schneller rechnen können, als ein µC, auch wenn er vielleicht nicht so hoch getaktet is, wenn er nur MAC-Operationen kriegt.


Ein vereinfachtes Bsp - falls du mit Hardware nicht so viel am Hut hast -:
CPU 1 läuft auf 2 GHz und hat nur einen ADD-Befehl, der einen Takt braucht, um zwei 64bit-Zahlen zu addieren.
CPU 2 läuft auf 1 GHz und hat nur einen MULT-Befehl, der 10 Takte braucht, um zwei 64bit-Zahlen zu multiplizieren.

Aufgabe: Berechne 49!.

CPU 1 fängt an:
2*1 = 1 + 1 = 2 (1 Takt)
3*2 = 2 + 2 + 2 = 6 (2 Takt)
4*6 = 6 + 6 + 6 + 6 = 24 (3 Takte)
5*24 = 24 + 24 + 24 + 24 + 24 = 120 (4 Takte)
6*120 = ... = 720 (5 Takte)
7*720 = ... = 5040 (6 Takte)
...
49* ... = ... = 49! (48 Takte)
Gesamt: [sub]i=1...48[/sub] i = 1176 Takte
1176 Takte bei 2 GHz = 588ns

CPU 2 fängt an:
2*1 = 2 (10 Takte)
3*2 = 6 (10 Takte)
4*6 = 24 (10 Takte)
...
49* ... = ... = 49! (10 Takte)
Gesamt: 48*10 = 480 Takte
480 Takte bei 1 GHz = 480ns

CPU 2 is "schneller". Du findest jetzt aber sicherlich auch eine passende Aufgabe, wo CPU 1 schneller fertig is. Spiel die Aufgabe mal mit 3! durch ;)

Mein PDA, was 10 Jahre alt is, hat 533 MHz unter der Haube, würde aber wohl sicher gegen meinen 200 MHz-Computer voll verlieren.

Fazit: Computer und Handy vergleichen würd ich vorsichtig sein, weil ich nicht sicher bin, was die CPUs in den Handys so drauf haben.
 
jo, alle Gewinnwahrscheinlichkeiten zu speichern, wäre etwas viel;).

Danke für die ausführliche Erklärung. Dass die Art des Prozessors so viel ausmacht, war mit in der Tat nicht bewusst.

Bei mir läuft es so, dass wenn die zwei Startkarten vorliegen, mit Hilfe eines Array und Konjunktionen die 5 Boardkarten hinzugefügt werden, sodass die Karten dann als 52 Bit Wert vorliegen (für jede Karte ein Bit und 7 von den 52 Bits sind dann halt auf 1). Danach wird dann ebenfalls nur mit bitweisen Operatoren und Verschiebungen, sowie Lookup-Tables und ein paar wenigen Integervergleichen die Hand ermittelt. Dies wird dann halt für alle möglichen Boardkombinationen gemacht. Ich denke (hoffe) mal, dass die bitweisen Operationen bei jedem Prozessor relativ flott ablaufen?


Gruß,
Klaus
 
Ich denke (hoffe) mal, dass die bitweisen Operationen bei jedem Prozessor relativ flott ablaufen?
Sollten sie schon, ja. Ein Bit-Shift is ja effektiv nix weiter, als dass da ne Leitung liegt, die Bit n mit Bit n+1 verbindet. Und AND/OR/XOR/NOT sind ja auch geschenkt.

Du musst auch beachten, dass mein Beispiel und die Überlegung sehr hardwarenah is. Effektiv arbeitest du ja nicht direkt auf der CPU, sondern da isn Betriebssystem dazwischen, - du verwendest Java - da is die JVM dazwischen, etc. etc.

Am einfachsten probierst du halt mal aus. Wenn du Zugang zu ein paar verschiedenen Handys hast, schreib dir n Benchmark-Programm, was die Operationen, die du vorhast, en masse zu machen, verwendet und miss die Zeit.

Ich könnt mir vorstellen, dass das aber mehr eine Frage des "Schafft es das Handy überhaupt oder schafft es es nicht?" und weniger des "Kann ich so performant programmieren, dass es das Handy schafft?" is.