Zu großes Array -> Absturz?

Hallo,
ich benötige ein großes Array um statische Daten anzulegen auf welche sehr oft zugegriffen werden muß.
Das Programm wirft jedoch jedes mal eine Exception wenn ich es starte. Das "böse" Array welches den Fehler verursacht:

short sevenPositions[13][13][13][13][13][13][13][1];

Dabei handelt es sich ja "nur" um gut 130MB.
In den Heap möchte ich die Daten nicht legen da uns in der Schule immer gesagt wurde das Arbeiten mit diesem sei um einiges langsamer als der Stack und die Zugriffszeiten sind in diesem Fall höchst kritisch.

Welche möglichkeiten gibt es um das ganze Array nun in den Stack zu bringen?

otze

stack und heap sind genauso schnell beim zugriff. das anlegen ist ein wenig teurer, aber das machst du nur einmal.

Krux

hast du es schonmal versucht alles in ein eindimensionales array zu packen? die Positionsberechnung kannst du ja in eine Klasse kapseln.

LordJaxom

Der Stack ist meist begrenzt und wird auch noch öfter gebraucht, den solltest Du nicht mit so einer Menge belasten. 130 MB auf dem Stack ist in der Tat utopisch, eleganter wäre hier eine Klasse (Objekt auf dem Stack), die einen Bereich auf dem Heap verwaltet und die n-dimensionalen Zugriffe kapselt.

Thomy

Aufm Stack kann man das vergessen!
Stell dir mal vor, jedes Programm hätte einen Stack von > 130 MB am Anfang! :p
Du musst es notgedrungen auf den Heap packen!

Krux schrieb:

hast du es schonmal versucht alles in ein eindimensionales array zu packen? die Positionsberechnung kannst du ja in eine Klasse kapseln.

Ich benutze extra soviele Dimensionen weil ich somit immer direkt auf das Jeweilige element ohne Berechnung zugreifen kann.
Das ganze wird mehrere Milliarden Zugriffe durchlaufen.

Thomy schrieb:

Stell dir mal vor, jedes Programm hätte einen Stack von > 130 MB am Anfang! :p

Ist es nicht so das der Stack den Anforderungen entsprechend wächst?

@all: Danke für die Antworten, wenn der Heap im Zugriff echt gleich schnell ist werde ich die Daten darauf Verstauen.

Badestrand

shamanu schrieb:

wenn der Heap im Zugriff echt gleich schnell ist werde ich die Daten darauf Verstauen.

Das hast du falsch verstanden Sowohl der Stack als auch "der Heap" liegen im Arbeitsspeicher und sind im Zugriff gleich schnell. Das Ding ist nur, dass der Stack zwar dynamisch wächst, aber dafür gedacht ist, kleinere Datenmengen zu beinhalten, jedenfalls deutlich kleiner als 100 MB. Normalerweise werden ja nur kleine lokale Variablen und Rücksprungadressen im Stack abgelegt, da kommt meist nicht sooo viel zusammen.

thordk

ich würd noch ein wenig zeit investieren, um die dimensionen drastisch zu reduzieren. mag kaum glauben, dass es notwenig ist, für irgendein problem außerhalb von massiver (!) simulation mit über 60 mio. werten zu hantieren.

thordk schrieb:

ich würd noch ein wenig zeit investieren, um die dimensionen drastisch zu reduzieren. mag kaum glauben, dass es notwenig ist, für irgendein problem außerhalb von massiver (!) simulation mit über 60 mio. werten zu hantieren.

Leichter gesagt als getan. Ich habe die dimension bereits drastisch reduziert damit sie überhaupt in den Speicher passt. Selbst mit den 130MB muß ich noch tricksen damit ich die Berechnungen hinbekomme.

Ich brauche nun noch etwas Hilfe wegen der Verwaltung.
Das Mehrdimensionale Array ist vielleicht doch nicht so gut.

Die Daten welche ich ablegen will sind jewiels 10 Bit groß. Das Problem ist nun das die siebenstellige nummer bei welcher jede stelle von 1-13 gehen kann der index ist an welchem ich die jeweiligen Daten ablegen will. Wie kann ich dies so einrichten das über den Index immer direkt auf die entsprechende Speicherstelle gesprungen wird?
Also ohne das zuerst mit dem Startpointer groß herumgerechnet werden muß oder ähnliches.

hustbaer

Wenn du nicht gross rechnen willst nimm doch einfach so ein Array.
Pack es in eine Struktur, und erzeuge die dann dynamisch:

struct foo
{
short a[13][13][13][13][13][13][13]; // das [1] hinten brauchst du nicht
};

void bar()
{
    std::auto_ptr<foo> f(new foo);
    f->a[1][2][3][4][5][6][7] = 123;
}

Ist nicht ohne Vorteile, da du so die Optimierung der Indexberechnung ganz dem Compiler überlassen kannst.
Und mach dich schonmal auf einige Stunden bis Tage Laufzeit gefasst wenn du da ein paar Milliarden mal zugreifen willst, zumindest wenn die Zugriffe grösstenteils nicht linear (fortlaufend) erfolgen

hustbaer schrieb:

Ist nicht ohne Vorteile, da du so die Optimierung der Indexberechnung ganz dem Compiler überlassen kannst.

meinst du der bekommt das so gut hin?

Kannst du mal verraten, wofür das gebraucht wird? Vielleicht gibts dafür ja ne bessere struktur.

tastenstreichler schrieb:

Kannst du mal verraten, wofür das gebraucht wird? Vielleicht gibts dafür ja ne bessere struktur.

Ja, ich versuche für das Poker spiel Texas Holdem bei zwei vorgegebenen Starthänden die exakte Wahrscheinlichkeit zu berechnen mit der man gewinnt wenn jeder bis zum ende dabei bleibt.
Jeder Mitspieler hat hierbei immer seine zwei eigenen Karten und die fünf Gemeinschaftskarten um das beste Blatt zu bilden.
Aus dem grund nehme ich ein Array welches sieben Dimensionen hat, was die sieben Karten für jeden Spieler darstellen aus denen er sein Blatt bilden kann.

Die Idee wäre nun das ich für alle siebener Kombinationen einen Wert gespeichert habe welcher um so höher ist je besser das Blatt.
Ansonsten müßte ich nämlich bei jedem Blatt immer auf paare, drillinge, straßen usw. überprüfen.

Wie gesagt ist durch die Kombinationsvielfallt die Geschwindigkeit das größte Problem.

pumuckl

Dazu brauchst du aber doch nicht alle Kombinationen zu speichern! Ich wuerds folgendermassen angehn (mehr oder weniger brute force):

- Codiere die Karten mit den Zahlen 1-52
- verteile dein Startblatt
- Ueberlege dir, wie man in einer einfachen Schleife alle Kombinationen von 5 Karten durchlaufen kann. Dabei koennen die 5 Karten geordnet bleiben, das macht die Schleife kleiner und du bearbeitest nicht mehrfach die gleiche kombi.
- ueberpruefe fuer jeden Schleifendurchlauf, ob in der 5er-Kombi die du grade untersuchst eine Karte aus dem Startblatt enthalten ist (wenn ja, ist die kombi nicht moeglich udn wird uebersprungen)
- ueberpruefe, wer die hoechste Hand hat und gib ihm einen "Gewinnpunkt"

wenn du die Schleife einmal komplett durch hast sagt dir die Verteilung der Gewinnpunkte wie die Gewinnchancen fuer die einzelnen Spieler stehen.

An Speicherplatz brauchst du dafuer also
- nSpieler * 2 byte fuer die Starthand
- 5 byte fuer die Schleifenvariablen
- ein paar byte fuer die punkte etc,

aber 130mb soeicher brauchst du nie und nimmer

pumuckl schrieb:

- ueberpruefe fuer jeden Schleifendurchlauf, ob in der 5er-Kombi die du grade untersuchst eine Karte aus dem Startblatt enthalten ist (wenn ja, ist die kombi nicht moeglich udn wird uebersprungen)

Ich bin mir jetzt nicht ganz sicher ob ich das ganze richtig verstanden habe.
Was ich berechnen will ist folgende Situation:
In meinen Händen sind zb Ass-Pik und Ass-Herz. Aus dieser Startsituation, ohne irgend etwas anderes zu kenne, möchte ich nun meine gewinn Chancen berechnen wenn alle bis zum Ende durchspielen. Somit muß ich auch die Karten der Gegner durch alle Möglichkeiten laufen lassen.

pumuckl schrieb:

- ueberpruefe, wer die hoechste Hand hat und gib ihm einen "Gewinnpunkt"

Genau hierfür benötige ich die 130MB "Datenbank" im Speicher. Diese Überprüfung ist nämlich nicht gerade Trivial und erfolgt zb bei 3 Mitspielern pro Kartenvariation viermal. (Die 130 Millionen variationen im speicher stehen in diesem Fall gegen 37 Milliarden Karten variationen welche überprüft werden)

pumuckl

hmm. ok hatte das so verstanden dass du die Karten der anderen auch kennst. dafuer hab ich n kleines Programm geschrieben, wo allerdings noch Kleinigkeiten fehlen:

typedef unsigned char Karte;
typedef unsigned char uchar;

class StartHand
{
  uchar nSp;
  Karte* karten;
public:
  StartHand (uchar nSpieler) : nSp(nspieler), karten(new Karten[2*nSpieler]) {}
  ~StartHand () {delete[] karten;}
  Karte* operator[] (uchar n) {return &karten[2*n];}
  bool Enthaelt(Karte k) const {
    for(uchar i=0; i < 2*nSp; ++i) if(karten[i] == k) return true;
    return false;
  }
  //setze die Karten fuer Spieler (Nr 0 bis nSp-1)
  void Setze(uchar spielerNr, Karte karte1, Karte karte2) { 
    karten[2*spielerNr] = karte1;
    karten[2*spielerNr+1] = karte2;
  }
  uchar NSpieler() const  {return nSp;}
private:
  StartHand& operator=(const StartHand& sh);
};

uchar Spielerzahl() {
  /* z.B. von Konsole einlesen */
}

void Belegestarthand(StartHand& shand) {
  /* z.B ueber Konsole mit shand.setze() */
}

int Bewertekarten(Karte k1, Karte k2, Karte k3, Karte k4, Karte k5, Karte k6, Karte k7) {
  /* gib eine Wertung ab => bessere Karten bessere Wertung */
}

int main() {
  StartHand starthand(Spielerzahl());
  Belegestarthand(starthand);

  Karte karte1, karte2, karte3, karte4, karte5; //5 karten fuer flop, turn und river
  unsigned int punkte[11] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; //laut wikipedia max 11 Spieler
  int bewertung[11] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

  //jetzt alle kombinationen durchgehn:
  //bei geordneten Karten ist die hoechste kombination 48, 49, 50, 51, 52
  for (karte1 = 1; karte1 < 49; ++karte1) {
    if (starthand.Enthaelt(karte1)) continue; //test ob karte in Starthand vorhanden
    for (karte2 = karte1+1; karte2 < 50; ++karte2) {
      if (starthand.Enthaelt(karte2)) continue;
      for (karte3 = karte2+1; karte3 < 51; ++karte2) {
        if (starthand.Enthaelt(karte3)) continue;
        for (karte4 = karte3+1; karte4 < 52; ++karte4) {
          if (starthand.Enthaelt(karte4)) continue;
          for (karte5 = karte4+1; karte5 < 53; ++karte5) {
            if (starthand.Enthaelt(karte5)) continue;

            for (int i = 0; i < starthand.NSpieler(); ++i) {
              bewertung[i] = Bewertekarten(starthand[i][0], starthand[i][1], 
					   karte1, karte2, karte3, karte4, karte5);
            }
            /* gib dem Spieler der die beste Wertung hat einen Gewinnpunkt*/
          }
        }
      }
    }
  }

  // fuer n Spieler gibt es 
  // (52-2*n)!/[(47-2*n)!*5!] Kombinationen:
  // 2 Spieler: 1712304 Kombinationen
  // 3 Spieler: 1370754 Kombinationen
  // 4 Spieler: 1086008 Kombinationen
  // usw.
  // teile die Punkte durch die Zahl der Kombinationen um die chance herauszufinden

  double gewinnchance[11];
  for (int i = 0; i < starthand.NSpieler(); ++i) {
    gewinnchance[i] = 120.0; //5!
    gewinnchance[i] *= punkte[i];
    for (int j = 0; j <5; ++j) gewinnchance /= (52-j-2*starthand.NSpieler());
  }

  /* gewinnchancen ausgeben */
}

Das programm muesste dann in deinem Fall noch so weit abgeaendert werden, dass du auch noch Schleifen ueber die Anfangskarten der anderen Spieler laufen laesst.

Genau hierfür benötige ich die 130MB "Datenbank" im Speicher. Diese Überprüfung ist nämlich nicht gerade Trivial und erfolgt zb bei 3 Mitspielern pro Kartenvariation viermal. (Die 130 Millionen variationen im speicher stehen in diesem Fall gegen 37 Milliarden Karten variationen welche überprüft werden)

nein, dafuer brauchst du keine riesige Datenbank. Du musst auch nicht alle moeglichen Kartenkombinationen abgespeichert haben. Vergib, wie oben angedeutet, einfach Punkte fuer ein Blatt aus 7 Karten, beispielsweise:

int Bewertekarten(/*karte 1-7*/) {
  int wertung = 0;
  if (werung = royal_flush(/*karten*/) return wertung;
  if wertung = street_flush(/*karten*/) return wertung;
  //...
  return high_card(/*karten*/);
}

int high_card(/*karten*/) {/* gib eine Wertung von 1-13 */}
int one_pair(/*karten*/) {/*wenn ein paar, dann Wertung von 14-26, sonst 0*/}
int two_pair(/*karten*/) {/*hier gibts mehr verschiedene Wertungen*/}
int royal_flush(/*karte 1-7*/) {/*die hoechste Wertung */}

Du reihst die Tests einfach aneinander und kodierst die Wertungen hart rein. Das braucht aber immernoch keine riesen Datenbank...

kleine Anmerkung: deine Datenbank wuerde zum Beispiel alle 4324 Royal-Flush Moeglichkeiten einzeln auflisten (die gibts ja in 4 farben mit hunderten Kombinationen fuer die Karten 6 udn 7), obwohl all diese Kombinationen voellig gleichwertig sind.

pumuckl schrieb:

//jetzt alle kombinationen durchgehn:
  //bei geordneten Karten ist die hoechste kombination 48, 49, 50, 51, 52
  for (karte1 = 1; karte1 < 49; ++karte1) {
    if (starthand.Enthaelt(karte1)) continue; //test ob karte in Starthand vorhanden
    for (karte2 = karte1+1; karte2 < 50; ++karte2) {
      if (starthand.Enthaelt(karte2)) continue;
      for (karte3 = karte2+1; karte3 < 51; ++karte2) {
        if (starthand.Enthaelt(karte3)) continue;
        for (karte4 = karte3+1; karte4 < 52; ++karte4) {
          if (starthand.Enthaelt(karte4)) continue;
          for (karte5 = karte4+1; karte5 < 53; ++karte5) {
            if (starthand.Enthaelt(karte5)) continue;

            for (int i = 0; i < starthand.NSpieler(); ++i) {
              bewertung[i] = Bewertekarten(starthand[i][0], starthand[i][1], 
					   karte1, karte2, karte3, karte4, karte5);
            }
            /* gib dem Spieler der die beste Wertung hat einen Gewinnpunkt*/
          }
        }
      }
    }
  }
  // fuer n Spieler gibt es 
  // (52-2*n)!/[(47-2*n)!*5!] Kombinationen:
  // 2 Spieler: 1712304 Kombinationen
  // 3 Spieler: 1370754 Kombinationen
  // 4 Spieler: 1086008 Kombinationen

Ja, wenn nur die Karten auf dem Tisch sich ändern wäre die Berechnung noch mehr oder minder gut realisierbar. Die for schleifen würde hier bis zur Bewertungs ebene gut 300 Millionen mal aufgerufen (52*51*50*49*48 - pro Spieler!).

pumuckl schrieb:

nein, dafuer brauchst du keine riesige Datenbank. Du musst auch nicht alle moeglichen Kartenkombinationen abgespeichert haben. Vergib, wie oben angedeutet, einfach Punkte fuer ein Blatt aus 7 Karten, beispielsweise:
int Bewertekarten(/*karte 1-7*/) {
  int wertung = 0;
  if (werung = royal_flush(/*karten*/) return wertung;
  if wertung = street_flush(/*karten*/) return wertung;
  //...
  return high_card(/*karten*/);
}

int high_card(/*karten*/) {/* gib eine Wertung von 1-13 */}
int one_pair(/*karten*/) {/*wenn ein paar, dann Wertung von 14-26, sonst 0*/}
int two_pair(/*karten*/) {/*hier gibts mehr verschiedene Wertungen*/}
int royal_flush(/*karte 1-7*/) {/*die hoechste Wertung */}

Ok, bleiben wir einmal bei deiner einfacheren Version. Wenn ich zehn Spieler nehme wären dies bereits 3 Milliarden aufrufe dieser Bewertungsfunktion. Das Hauptproblem weshalb ich aber noch immer glaube das die "Datenbank" notwendig ist:
Du übergibst 7 Karten, die Bewertung in Texas Holdem erfolgt aber nur nach den 5 besten(!) Karten. Das heißt ich bekomme eventuell ein royal flush als Bewertung zurück, obwohl meine 2 Karten die ich in den Händen halte garnicht im Royal Fulsh drin sind. (weil das Flush auf dem Tisch liegt)

pumuckl schrieb:

kleine Anmerkung: deine Datenbank wuerde zum Beispiel alle 4324 Royal-Flush Moeglichkeiten einzeln auflisten (die gibts ja in 4 farben mit hunderten Kombinationen fuer die Karten 6 udn 7), obwohl all diese Kombinationen voellig gleichwertig sind.

Grundlegend richtig, wie oben beschrieben hat dies jedoch mit der Performance zu tun und nach dem was ich bis jetzt gesehen habe scheint es die beste möglichkeit zu sein die mir momentan einfällt. (Die 4324 stimmen übringens nicht ganz. Ich vernachlässige die 4 Farben weil die Datenbank ansonsten astronomische ausmaße annehmen würde.)

pumuckl

shamanu schrieb:

Ja, wenn nur die Karten auf dem Tisch sich ändern wäre die Berechnung noch mehr oder minder gut realisierbar. Die for schleifen würde hier bis zur Bewertungs ebene gut 300 Millionen mal aufgerufen (52*51*50*49*48 - pro Spieler!).

nicht ganz, da die letzten 5 Karten immer geordnet uebergeben werden gibts dafuer maximal 1,7 Mio Aufrufe pro Spieler. Immernoch besser so oft eine Testfunktion aufzurufen als so oft durch deine ganze Datenbank zu krabbeln um die richtige Kombination zu finden.

Du übergibst 7 Karten, die Bewertung in Texas Holdem erfolgt aber nur nach den 5 besten(!) Karten. Das heißt ich bekomme eventuell ein royal flush als Bewertung zurück, obwohl meine 2 Karten die ich in den Händen halte garnicht im Royal Fulsh drin sind. (weil das Flush auf dem Tisch liegt)

Stimmt. aber wenn der Royal flush auf dem Tisch liegt, hat jeder Spieler einen Royal flush. Man muss seine Handkarten nicht einbringen, daher ist das vollkommen richtiges Verhalten.

(Die 4324 stimmen übringens nicht ganz. Ich vernachlässige die 4 Farben weil die Datenbank ansonsten astronomische ausmaße annehmen würde.)

hm. wenn du farben vernachlaessigst dann kannst du einen royal flush von einer normalen strasse nicht unterscheiden...

pumuckl schrieb:

nicht ganz, da die letzten 5 Karten immer geordnet uebergeben werden gibts dafuer maximal 1,7 Mio Aufrufe pro Spieler. Immernoch besser so oft eine Testfunktion aufzurufen als so oft durch deine ganze Datenbank zu krabbeln um die richtige Kombination zu finden.

Das mit den letzten 5 Karten ist mir nicht ganz klar, wie kommst du auf 1,7 Millionen Aufrufe?
Ich will die Datenbank nicht durchsuchen sondern immer gleich an die richtige Position springen.

Stimmt. aber wenn der Royal flush auf dem Tisch liegt, hat jeder Spieler einen Royal flush. Man muss seine Handkarten nicht einbringen, daher ist das vollkommen richtiges Verhalten.

Ok, auf dem Tisch liegt ein drilling. Woher erhalte ich die Information welcher den besten Kicker hat?

hm. wenn du farben vernachlaessigst dann kannst du einen royal flush von einer normalen strasse nicht unterscheiden...

Ja, ich kann generell keinen Flush erkennen. Die "kleinen" probleme kommen aber später...

pumuckl

shamanu schrieb:

Das mit den letzten 5 Karten ist mir nicht ganz klar, wie kommst du auf 1,7 Millionen Aufrufe?

48*47*46*45*44 / 1*2*3*4*5 = ca. 1.7 millionen (genaue Zahl steht in meinem code oben). Denn: dadurch dass fuer die zwei Spieler schon jeweils 2 karten auf der Hand haben kommen fuer den Tisch nichtmehr ganz so viele verschiedene Kombinationen in Frage. und da die Kombination 12345 und 52341 und 31245 usw. alle das selbe ergebnis liefern, habe ich das dadurch ausgeschlossen, dass karte2 groesser ist als karte1 usw. (sieht man auch im code der for-schleifen)
deshalb muss man die Zahl der moeglichen Kombinationen durch die Zahl der moeglichen Permutationen teilen und kommt schon einiges besser bei weg.

Ok, auf dem Tisch liegt ein drilling. Woher erhalte ich die Information welcher den besten Kicker hat?

Gutes Argument. Ich hatte ja angedeutet, dass man schon fuer zwei paare eine groessere Wertungs-range hat. vielleicht gibt man mit der Funktion einfach ein struct aus 3 oder 4 werten wieder. Der erste bezeichnet die Art der Hand (royal flush, full house etc), der zweite die relevante Kartenhoehe (obs jetzt n Koenigsdrilling oder n Damen drilling ist - Kicker beim Drilling brauchts naemlich nicht) und der dritte den kciker z.B. beim Paar. Fuer son ergebnisstruct n vergleichsoperator zu schreiben sollte recht fix gehn.

Ja, ich kann generell keinen Flush erkennen. Die "kleinen" probleme kommen aber später...

Hm. beweise dass das Problem nur ein kleines ist *g* vorher solltest dus nicht vernachlaessigen, sonst raufst du dir hinterher die Haare weil dus etwas gruendlicher nochmal machen musst

Zu großes Array -&gt; Absturz?

Zu großes Array -> Absturz?