3. geschwindigkeitsproblem, std::vector<> schuld?

geschwindigkeitsproblem, std::vector<> schuld?

  • H

    Kleinigkeiten kann man viele finden.

    .
          if((x == 3 && y == 3) || 
             (x == 3 && y == 4) || 
             (x == 4 && y == 3) || 
             (x == 4 && y == 4))

    könnte man das nicht einfach als

    .
          if((x == 3 || x == 4) && (y == 3 || y == 4))

    schreiben?
    ...

    0
  • B

    Helium schrieb:

    Kleinigkeiten kann man viele finden.

    .
          if((x == 3 && y == 3) || 
             (x == 3 && y == 4) || 
             (x == 4 && y == 3) || 
             (x == 4 && y == 4))

    könnte man das nicht einfach als

    .
          if((x == 3 || x == 4) && (y == 3 || y == 4))

    schreiben?
    ...

    oh, da hast du wohl recht. 🤡
    wobei ich annehme das der compiler solche ausdrücke in konjunktive normalform bringt.

    0
  • J

    borg schrieb:

    wobei ich annehme das der compiler solche ausdrücke in konjunktive normalform bringt.

    Das glaube ich nicht. Warum sollte er auch.
    Zudem würde er sich damit die Auswertung ja viel schwerer machen. Er muß ja bei && (||) aufhören, sobald der erste operand falsch (wahr) ist.

    0
  • V

    borg schrieb:

    wobei ich annehme das der compiler solche ausdrücke in konjunktive normalform bringt.

    ganz bestimmt nicht. ok, er dürfte das zwar, aber was ist, wenn ich aus der datenlage her genau weiß, daß die bedingung zu 99.9% aller fälle bei (x == 3 && y == 3) bereits abbricht? ich hab mit absicht diese umformung gemacht und der compiler hackt es mir wieder kaputt?

    0
  • ?

    Kann das nicht auch die Semantik verändern, wie Jester evtl. andeuten wollte? Die Ausdrücke können ja vor allem auch Seiteneffekte haben, solche Umformungen könnten doch die Auswertungsreihenfolge ändern, oder?

    0
  • B

    das ist zwar ein bisschen OT aber in diesem thread ist wenigstens schon bekannt worum es geht.

    ich brauch ein hashwert von dem schachbrett. im momment mach ich es sehr naiv:

    int hash = 0;
  for(size_t x = 0; x < BOARD_LENGTH; ++x)
    for(size_t y = 0; y < BOARD_LENGTH; ++y)
      hash+=(x*y+y)*field[x][y];
  return hash;

    in field stehen die unterschiedlichen werte der figuren. nachdem das ganze dann 50x übergelaufen ist( 🤡 ) stehen in hash immer werte zwischen -40000 und -60000. und es kommt viiiiiel zu oft zu kollisionen. hat irgendwer eine idee wie ich ohne großen rechenaufwand an einen akzeptablen hashwert komme? (akzeptabel = in weniger als 0,1% der fälle eine kollision, bei 100 hashwerten)
    besonders sehr ähnliche felder sollten natürlich unterschiedliche hashwerte haben.

    ich brauche das um stellungswiederholungen zu bemerken, ich hab zuerst einfach bei jeder stellung das ganze feld gespeichert, alllerdings war der aufwand beim vergleichen der felder inakzeptabel.

    ps: ihr habt natürlich recht mit dem vereinfachen der ausdrücke 😮 .
    pps: das umstellen auf 1d-arrays hat keinen messbaren unterschied gebracht.

    0
  • V

    borg schrieb:

    ich brauch ein hashwert von dem schachbrett. im momment mach ich es sehr naiv:

    int hash = 0;
  for(size_t x = 0; x < BOARD_LENGTH; ++x)
    for(size_t y = 0; y < BOARD_LENGTH; ++y)
      hash+=(x*y+y)*field[x][y];
  return hash;

    in field[x][y] stehen zahlen von 0 bis 15?
    als verbietet sich

    hash+=field[x][y];

    aber das weißte ja schon selber. es würde nur das material zählen und gegen züge ohne schlagen resistenz sein.
    das (x*y+y) ist teuer. eine plutimikation hat viele takte.
    mir drängt sich sofort

    hash=hash*31+field[x][y];

    auf.
    31 kann der compiler extrem schnell. hash muss vom typ unsigned int sein.
    beim haschen von strings ist hash=hash    31+str[i]; extrem beliebt.
    der plutimikator muss ungerade sein, weil sonst alle alten bits nur herausgeschubst werden.

    nun zu deinem

    hash+=(x*y+y)*field[x][y];

    wir erkennen: wenn y gerade ist, dann ist (x*y+y) durch 4 teilbar. wenn field[x][y] wie ich annahm nur werte zwischen 0 und 15 haben kann, verfummelst du damit nur die bits 2 bis 17.
    wenn y gerade ist, verfummelst du nur diewerte 0 bis 15.
    also zusammen nur 0 bis 17. ist also nur 0 bis 131072.
    deckt sich mit deine angaben. offensichtlich nimmst du signed und -7 bis 7 als figuren.
    probier mal meinen hasher (und bleib bei signed).
    also

    hash=hash<<5-hash+field[x][y];

    und poste natürlich, ob es was bringt.
    ich habe das gefühl, daß mein hasher alle bits recht gut belegt. aber sicher ist man hei hash-funktionen nie. man kann da nur ausprobieren und messen.

    0
  • B

    volkard schrieb:

    in field[x][y] stehen zahlen von 0 bis 15?

    nein, es steht dort oft 0, oft 100 und -100, und manchmal 301, 302, 500, 900, 10000 + die negationen. also die figurenwerte in centipawn(hunderstelbauern).
    wenn ich die figuren durchnumeriere und reinschreibe brauch ich bei der figurenbewertung die doppelte anzahl an arrayzugriffen.

    volkard schrieb:

    probier mal meinen hasher (und bleib bei signed).
    also

    hash=hash<<5-hash+field[x][y];

    ok probier ich mal. wenns gut verteilt aber es trotzdem zuviele kollisionen gibt kann ich natürlich auch ein 64bit-datentyp nehmen, damit muss es dann aber gehen.

    0
  • B

    habs als erstes damit probiert:

    hash=hash*31+field[x][y];

    hab nen paar spiele durchrechnen lassen und es gab keine kollisionen.
    die zahlen sehen so aus:

    logfile schrieb:

    uci
    uciok
    isready
    readyok
    position startpos moves g1f3 b8c6 d2d4 d7d5 c1f4 g8f6 b1c3 e7e6 c3b5 f8d6 f4d6 c
    7d6 e2e3 e8g8 c2c4 d8b6 c4d5 b6a5 d1d2 a5d2 f3d2 c6b4 a2a3 b4c2 e1e2 c2a1 d2f3 a
    7a6 b5d6 f6g4 d5e6 f7e6 h2h3 g4f6 e3e4 f8d8 e4e5 f6d5 e2d2 a1b3 d2c2 b3a1 c2b1 a
    1b3 b1c2 b3a5 f3g5 b7b5 g5f7 d8d7 f7g5 b5b4 a3b4 d5b4 c2b1 a8b8 d6c8 d7d4 f1a6 b
    4d3 a6d3 d4d3 c8d6 b8b6 f2f4 d3d2 h1g1 b6b2
    -1234213860
    -1215141476
    -524258660
    1484196252
    890199830
    2127233174
    -608284906
    821574606
    2071283278
    1716901774
    1882200763
    976518534
    1387875902
    -1266444738
    932749118
    754251838
    -1752365038
    -414537574
    1231886626
    536449558
    885021110
    213097270
    -788034578
    -701771410
    -1099217522
    1755727262
    -79380862
    -2132948166
    -340472774
    740454842
    -1966767258
    -1939029830
    -1927136910
    1286902770
    745983034
    -287230918
    -581774606
    1505600654
    1248433294
    -1804810738
    -769083890
    -2010807154
    -290168722
    951554542
    -769083890
    -2044843122
    -403891698
    1704309006
    907893646
    -1653767946
    -857352586
    -1969959634
    -133439526
    1416995674
    -1157333190
    124078906
    -252157721
    1101772571
    547124537
    -328919083
    -2076556435
    1686588898
    -750335902
    5338466
    -256803230
    1881700858
    490876410
    726694550

    woran erkenne ich ob die gut verteilt sind?
    ich teste mal noch deinen anderen vorschlag.

    0
  • B

    dein zweiter vorschlag hat auche alle spiele ohne kollisionen bewältigt.

    edit: ohgott, das zweite ist ja genau das gleiche, ob ich nun x*32-x oder x*31 rechne.... und ich habs nicht gepeilt 😮

    0
Anmelden zum Antworten