sort_stable und pointer

[codecow]

Naja um ehrlich zu sein hab ich mir die Frage nach C oder C++ gar nicht gestellt. Aber Standard C wär mir im Prinzip auch recht. Das ganze soll auch keinen größeren Umfang mehr kriegen und ist mehr aus der Not heraus geboren weil der Code in Ruby (was keine Überraschung ist) eine absolut miserable Performance hat. Daher war das meiner Meinung nach sinnvollste die performance-lastigen Funktionen auszulagern und dann per SWIG/Inline oder als .dll einzubinden. Nun sind C/C++ und ich uns nicht wirklich grün wie man an dem Code wohl auch erkennen kann. Also hoff ich eigentlich nur dass ich das zum laufen krieg dann hab ich fürs erste wieder Ruhe.

Wenns dafuer keine vernünftige Lösung ohne ojektorientierung gibt würd ich es natürlich auch so versuchen. "Whatever works".

Und ob man jetzt groeßtenteils C konformen Code als C++ kompiliert oder nen komplett C++ freien Ansatz waehlt macht ja eigentlich kein Unterschied oder?

[padreigh]

egal

[SeppJ]

Also ein einfacher, auch C konformer, Anfang wäre es, alle zusammengehörigen Werte mal in ein struct zu packen. Dann funktioniert das auch mit dem Sortieren so wie du es dir vorstellst, egal ob mit stable_sort oder dem C-Äquivalent qsort ( Welches aber nicht stabil sortiert!). Dazu wäre eine Menge umschreiben nötig.

Eine Alternative bei der du bei deinem bisherigen Ansatz bleiben kannst (wobei ich bezweifle, ob der überhaupt richtig ist), wäre eine eigene Sortierfunktion, die dann entsprechend kompliziertere Vertauschungsoperationen durchführt.

[Michael E.]

Wie sieht denn der Ruby-Code aus? Und welche Version benutzt du?

[codecow]

Ok vielen dank erstmal ich werd es dann mal mit einem struct versuchen.

Der Ruby Code sieht wie folgt aus. Der Unterschied ist das ich hier beliebige Ausgangssituationen hab von den bekannten Karten her. Das hab ich mir bei der C/C++ Version bis auf die gemeinsamen Karten gespart. Und ich benutze Ruby 1.9.2.

require "HandLookup.rb"

class MonteCarlo
  def initialize
    @ary_nbr_hand_types = [0, 1277, 4137, 4995, 5853, 5863, 7140, 7296, 7452, 7462]
    @hand_eval = HandLookup.new
  end

  def get_odds(players, nbr_loops, ary_com_cards, hsh_player_cards)
    #make array of random numbs to pick a card from
    ary_random_cards = (1..52).to_a
    #delete already used cards from the array of..
    #..community cards
    ary_com_cards.each do |card|
      ary_random_cards.delete(card)
    end
    #..players cards
    hsh_player_cards.each_value do |ary_cards|
      ary_cards.each do |card|
        ary_random_cards.delete(card)
      end
    end
    #create array for the odds
    ary_odds = []
    players.times do
      ary_odds << 0
    end
    nbr_loops.times do |loops_done|
      #clone card arrays for temp use
      ary_com_cards_temp = Array.new(ary_com_cards)
      hsh_player_cards_temp = Hash.new(hsh_player_cards)
      @ary_random_cards_temp = Array.new(ary_random_cards)
      #pick random cards for the simulation..
      #..community cards
      while ary_com_cards_temp.length < 5
        ary_com_cards_temp << pick_random_card
      end
      #..player cards
      players.times do |i|
        i += 1
        if hsh_player_cards_temp.has_key?(i) == true
          while hsh_player_cards_temp[i].length < 2
            hsh_player_cards_temp[i] << pick_random_card
          end
        else
          hsh_player_cards_temp[i] = [pick_random_card, pick_random_card]
        end
      end
      #create temp hand rank hash
      hsh_hand_ranks = {}
      #evaluate hand ranks
      hsh_player_cards_temp.each_pair do |nbr_player, ary_cards|
        hand_value = @hand_eval.eval_hand_7(ary_com_cards_temp + ary_cards)
        hsh_hand_ranks[nbr_player] = @ary_nbr_hand_types[(hand_value >> 12)-1] + (hand_value & 0x00000FFF)
      end
      #sort hand ranks
      ary_sorted_hand_ranks = hsh_hand_ranks.sort {|a,b| b[1]<=>a[1]}
      #add a win to the winning player
      ary_odds[ary_sorted_hand_ranks[0][0]-1] += 1
      #add more wins to other players in case of a tie
      for i in 1..(players-1) do
        if ary_sorted_hand_ranks[i][1] == ary_sorted_hand_ranks[i-1][1]
          ary_odds[ary_sorted_hand_ranks[i][0]-1] += 1  
        end
      end
    end
    #calc percentage
    ary_odds.each_index do |i|
      ary_odds[i] = ary_odds[i].to_f / nbr_loops * 100
    end
    #return the odds
    return ary_odds
  end

  def pick_random_card
    random_card = @ary_random_cards_temp[rand(@ary_random_cards_temp.length)]
    @ary_random_cards_temp.delete(random_card)
    return random_card
  end
end

[Michael E.]

Ich setz mich heut mal irgendwann dran und versuch, das ein wenig zu optimieren. Kannst du mir ein kompilierbares Beispiel (d. h. mit HandLookup.rb) geben? Um welchen Faktor ist das Programm denn zu langsam? Wie oft wird der Code durchlaufen?

Was mir auf den ersten Blick auffällt, sind Sachen wie:

irb(main):001:0> VERSION
=> "1.8.7"
irb(main):002:0> a = (1..10).to_a.map{|i|(rand*51).to_i + 1}
=> [9, 5, 48, 49, 8, 6, 5, 24, 40, 32]
irb(main):003:0> b = (1..50).to_a
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
irb(main):004:0> require "benchmark"
=> true
irb(main):005:0> puts Benchmark.measure { 100000.times{ c=b; c-a } }
  0.655000   0.016000   0.671000 (  0.669038)
=> nil
irb(main):006:0> puts Benchmark.measure { 100000.times { c=b; a.each { |i| c.delete i } } }
  4.961000   0.000000   4.961000 (  4.973284)
=> nil

oder

irb(main):016:0> a = Array.new
=> []
irb(main):017:0> puts Benchmark.measure { 10000000.times { a << 0 } }
  2.980000   0.062000   3.042000 (  3.062176)
=> nil
irb(main):018:0> puts Benchmark.measure { a = [0] * 10000000 }
  0.125000   0.016000   0.141000 (  0.148009)
=> nil

d. h. Stellen, an denen du n Funktionsaufrufe machst, wo ein großer reichen würde.

[Michael E.]

Insbesondere deine Wahl der Parameter wäre wichtig.

[codecow]

Hm sehr nett das du dir die Mühe machen willst. Und ich liebe Ruby zwar aber das gibt die Sprache glaub ich einfach nicht her. Zu langsam ist es etwa um den Faktor 15000. Das heißt ich kann im worst-case ca. 66 Simulationen/Sekunde machen und so ab 1000000 (1 mil) wärs praktikabel. Das ist natürlich kaum machbar. Und die Stärken von Ruby liegen ja in einem ganz andere Bereich. Und so praktisch wie Ruby ist müssen die Funktionen halt teilweise mit einem beträchtlichen Overhead erkauft werden. Den Deal geh ich in den meisten Fällen sehr gerne ein nur hier hab ich mir gedacht warum soll ich jetzt noch stundenlang rumoptimieren und hinterher höchstwahrscheinlich immer noch weit hinter dem Performanceziel hängen wenn man doch hervorragend C/C++ einbinden kann. Genau für solche Fälle sind all diese Schnittstellen ja gedacht.
Ehrlich gesagt bin ich mir nicht mal sicher ob ich das Ziel mit einer nativen Implementierung erreiche. In dem Fall würd ich es dann mit OpenCL versuchen.
Naja aber lass dich nicht entmutigen. Wenn du da einen Weg siehst praktikable Performance in Ruby zu erreichen wär das natürlich noch besser.

Hier ist die HandLookup class:

class HandLookup
  def initialize
    @rank_table = File.new(Dir.pwd + "/HANDRANKS.DAT", "rb")
    @rank_table.binmode()
  end

  def eval_hand_7(ary_cards)
    p = 53
    ary_cards.each do |pc|
      @rank_table.pos = (pc + p) * 4
      p = @rank_table.read(4).unpack("l").first
    end
    return p
  end
end

Mein Testscript.

$: << Dir.pwd

require "MonteCarlo.rb"

@hsh_cards = {
"2s" => 1, "2h" => 2, "2d" => 3, "2c" => 4, "3s" => 5, "3h" => 6, "3d" => 7, "3c" => 8, "4s" => 9,
"4h" => 10, "4d" => 11, "4c" => 12, "5s" => 13, "5h" => 14, "5d" => 15, "5c" => 16, "6s" => 17,
"6h" => 18, "6d" => 19, "6c" => 20, "7s" => 21, "7h" => 22, "7d" => 23, "7c" => 24, "8s" => 25,
"8h" => 26, "8d" => 27, "8c" => 28, "9s" => 29, "9h" => 30, "9d" => 31, "9c" => 32, "Ts" => 33,
"Th" => 34, "Td" => 35, "Tc" => 36, "Js" => 37, "Jh" => 38, "Jd" => 39, "Jc" => 40, "Qs" => 41,
"Qh" => 42, "Qd" => 43, "Qc" => 44, "Ks" => 45, "Kh" => 46, "Kd" => 47, "Kc" => 48, "As" => 49,
"Ah" => 50, "Ad" => 51, "Ac" => 52
}

def convert_cards(*cards)
  ary_cards_converted = []
  cards.each do |card|
    ary_cards_converted << @hsh_cards[card]
  end
  return ary_cards_converted
end

simulator = MonteCarlo.new
t1 = Time.now.to_f
ary_odds = simulator.get_odds(9, 10000, [], {})#convert_cards("Ah", "Ad", "8s"), {"1" => convert_cards("Ac", "Th")})
t2 = Time.now.to_f
puts t2-t1
puts "\n", ary_odds

Und hier das Programm das die HandRanks.dat erzeugt. Brauch ein paar Minuten. Die Datei landet im Ordner von dem aus das Programm aufgerufen wird nicht dort wo es gespeichert ist.

http://www.megaupload.com/?d=JEQHBE3N

Ich könnte auch den Source-Code posten falls du misstrauisch bist aber so ist es glaub ich am einfachsten.

[Michael E.]

codecow schrieb:

Ich könnte auch den Source-Code posten falls du misstrauisch bist aber so ist es glaub ich am einfachsten.

... wenn du -static-libgcc benutzt

Aber Faktor 15000 ist schon ne Hausnummer. Hab zwar schon durch ein paar simple Änderungen gute Ergebnisse erzielt, aber natürlich nichts, was für dich zufriedenstellend wäre.

Edit: Wie groß ist HandRanks.dat? Du solltest zumindest Teile cachen und nicht für jeden Aufruf einen neuen Lesevorgang starten. Wenn die Datei nicht zu groß ist (für dich zum Upload, mir ist das egal ), kannst du sie ja mal online stellen.

[padreigh]

Poker scheint ja recht interessant zu sein. Du gehst von einem 52 Blatt aus zum Simulieren. Laut Wikipedia sind aber eher 6*52 Karten Sledge zum Spielen üblich ... da können in einer Runde also durchaus 8 Asse vertreten sein ... was deine ermittelten Werte (im Sinne einer optimalen Spielstrategie) dann wohl über den Haufen wirft?

Der HandValue von 7/10 Paarungen ist unabhängig von der Kartenfarbe, die ist nur für Flush, Straight Flush und Royal Flush wichtig ... das streicht fast 5/6 oder mehr deiner Riesendbewertungsdatei zusammen ...

Die Datei hat so um die 31MB wenn ich den Code richtig sehe.

[SeppJ]

padreigh schrieb:

Poker scheint ja recht interessant zu sein. Du gehst von einem 52 Blatt aus zum Simulieren. Laut Wikipedia sind aber eher 6*52 Karten Sledge zum Spielen üblich ... da können in einer Runde also durchaus 8 Asse vertreten sein ... was deine ermittelten Werte (im Sinne einer optimalen Spielstrategie) dann wohl über den Haufen wirft?

Das hat jetzt nichts mit dem Thema zu tun: Das hast du falsch verstanden. Es sind zwar 6 Kartenspiele, aber von denen wird immer nur genau eines verwendet. (edit: Das hat einfache physikalische Gründe: Man kann dann im Hintergrund kräftig mischen, während im Vordergrund mit einem frisch gemischten Deck gespielt wird.)

[Michael E.]

Meinst du mit 66 Simulationen/Sekunde den zweiten Parameter der Methode, der bei dir auf 10000 steht? Wenn ja, ist der ständige Zugriff auf HandRanks.dat definitiv der Flaschenhals. Ich schaff im Moment ca. 250000 Durchläufe pro Sekunde bei nem Dummy-eval_hand_7. Dann wärs ja doch noch machbar mit Ruby.

[codecow]

Der HandEvaluator nicht meine Arbeit und basiert auf Graphen. Hier ist der Ansatz gut erklärt: http://www.pst.ifi.lmu.de/~hammer/poker/handeval.html
Und hier ist er hauptsächlich entstanden:
http://archives1.twoplustwo.com/showflat.php?Cat=0&Number=8513906&page=0&fpart=1&vc=1
Falls sich jemand dafür interessiert.

Jedenfalls funktoniert er sehr gut und ist absolut optimiert. Mir gehts eigentlich nur um die Simulation.

250k/sek ist schonmal sehr gut. Ich dachte irgendwie ich hätte die Datei schon gecached aber wenn man sich die CPU-Auslastung anguckt ist natürlich alles klar. Werd meine Ruby Version auch mal dementsprechen bearbeiten. Was noch interessant wär hast du 250k Hände oder Simulationen geschafft? Weil man für eine Simulation ja mindestens durch die Anzahl der Spieler rechnen muss.

http://www.megaupload.com/?d=ID3ATVST
Hier hab ich die Datei mal geuploadet. Aber megaupload weigert sich gerade irgendwie sie rauszurücken. Vielleicht gehts nachher.
Aber das einfachste ist wirklich sie sich generieren.

Der Versuch die Datei in einen String zu lesen ist daran gescheitert das String.slice keine Bignum als Parameter akzeptiert und und Fixnum mit 31-Bit nicht in der Lage ist die gesamte Datei zu indexieren. Werd jetzt mal versuchen die Werte als fertige Integer in ein Array zu lesen.

[codecow]

Hm Arrays nehmen auch nur Fixnum Indizes. Wie hast du dass den gelöst?

[Michael E.]

Oje, ich seh grad, dass ich mich um eine Größenordnung vertan hab Es sind nur ca. 25000 Aufrufe pro Sekunde.

Ich hab HandLookup verkrüppelt zu

class HandLookup
  def eval_hand_7(ary_cards)
    rand(100).to_i
  end
end

MonteCarlo hab ich unverändert gelassen. Meine Version sieht im Moment so aus:

class MonteCarlo2
  def initialize
    @ary_nbr_hand_types = [0, 1277, 4137, 4995, 5853, 5863, 7140, 7296, 7452, 7462]
    @hand_eval = HandLookup.new
  end

  def get_odds(player_count, runs, community_cards_init, player_cards_param)
    random_cards_pool = (1..52).to_a
    random_cards_pool -= community_cards_init
    player_cards_param.each_value do |cards|
      random_cards_pool -= cards
    end

    player_cards_init = Array.new(2 * player_count)
    player_cards_param.each do |key, value|
      unless value.nil? or value.empty?
        player_cards_init[2*key] = value[0]
        player_cards_init[2*key + 1] = value[1] unless value.size < 2
      end
    end

    odds = [0] * player_count

    runs.times do
      community_cards = Array.new(community_cards_init)
      player_cards = Array.new(player_cards_init)
      set_random_card_set(random_cards_pool)

      missing = 5 - community_cards.length
      community_cards += pick_n_random_cards(missing) if missing > 0

      player_cards.map! { |card| card.nil? ? pick_random_card : card }

      ranks = Hash.new

      for i in (0...player_count)
        hand_value = @hand_eval.eval_hand_7([player_cards[2*i], player_cards[2*i+1]] + community_cards)  #TODO: karten einzeln übergeben
        ranks[i] = @ary_nbr_hand_types[(hand_value >> 12)-1] + (hand_value & 0x00000FFF)
      end

      sorted_ranks = ranks.sort { |lhs, rhs| rhs[1] <=> lhs[1] }
      i = 0
      win_score = sorted_ranks[0][1]
      while i < player_count and sorted_ranks[i][1] == win_score do
        odds[sorted_ranks[i][0]] += 1
        i += 1
      end
    end

    puts odds.map { |i| i.to_f / runs * 100 }.inspect
    odds.map { |i| i.to_f / runs * 100 }
  end

  def set_random_card_set(arr)
    @random_card_set = Array.new(arr).shuffle
  end

  def pick_random_card
    @random_card_set.pop
  end

  def pick_n_random_cards(n)
    @random_card_set.slice!(@random_card_set.size - n, n)
  end
end

Aufruf:

foo = MonteCarlo.new
bar = MonteCarlo2.new

Benchmark.bm do |x|
  x.report { foo.get_odds(9, 100000, [], {}) }
  x.report { bar.get_odds(9, 100000, [], {}) }
end

Ausgabe:

user     system      total        real
  4.898000   0.000000   4.898000 (  4.926282)
 14.306000   0.000000  14.306000 ( 14.314818)

Dabei ist ein CPU-Kern vollständig ausgelastet. Am meisten Performancegewinn hat die neue pick_random_card gebracht, weil es einfach deutlich performanter ist, Elemente vom Ende des Arrays wegzunehmen statt mittendrin zu löschen:

Benchmark.bm do |x|
  x.report("pop:    ") { n.times { a = (1..50).to_a; a.shuffle; 10.times { a.pop } } }
  x.report("delete: ") { n.times { a = (1..50).to_a; 10.times { x = a[rand(a.length)]; a.delete(x) } } }
end

Output:
      user     system      total        real
pop:      1.076000   0.000000   1.076000 (  1.087062)
delete:   5.055000   0.000000   5.055000 (  5.046288)

Wenn du das Sortieren in C++ schreibst (z. B. mittels RubyInline) à la

#include <iostream>
#include <algorithm>
using namespace std;

struct Tuple
{
	int first;
	int second;
};

bool pred(const Tuple& lhs, const Tuple& rhs)
{
	return lhs.second < rhs.second;
}

int main()
{
	for(int n = 0; n < 10000000; ++n)
	{
		Tuple foo[10];
		for(int i = 0; i < 10; ++i)
		{
			foo[i].first = i;
			foo[i].second = 1000 - 11 * i;
		}

		sort(foo, foo + 10, pred);
	}
}

sparst du nochmal etwa 0,7 Sekunden IIRC. Außerdem ist das hier ein perfektes Beispiel, bei dem du mehrere Prozesse starten solltest, weil sonst nur ein CPU-Kern ausgelastet wird. Dadurch vervierfacht sich die Geschwindigkeit nahezu bei vier Kernen.

[Michael E.]

codecow schrieb:

Der Versuch die Datei in einen String zu lesen ist daran gescheitert das String.slice keine Bignum als Parameter akzeptiert und und Fixnum mit 31-Bit nicht in der Lage ist die gesamte Datei zu indexieren.

Eigentlich schon, denn mit 31 Bit kann man 2 GB adressieren.

[Michael E.]

Deine evil_hand_7 ist fehlerhaft, weil du p ständig verwirfst und somit nur die letzte Karte zur Berechnung einbeziehst. Auch erscheinen mir die Zahlen zur Positionsberechnung viel zu klein für so eine große Datei. Aber ich weiß nicht, wie HandRanks aufgebaut ist, und überlasse das dir.

Hier ist ein Vorschlag für evil_hand_7:

class HandLookup
  def initialize
    @contents = open('d:\handranks.dat', "rb") {|io| io.read };
  end

  def eval_hand_7(ary_cards)
    p = 53
    pos = 0
    ary_cards.each do |pc|
      pos += (pc + p) * 4
    end
    @contents[pos..(pos+3)].unpack("l").first
  end
end

Damit schaff ich noch 60000 statt 100000 Durchläufe in 4,5 Sekunden.

[Michael E.]

Ne, doch lieber alles direkt in ein Array stopfen:

n = 10000000
pos = 1000
Benchmark.bm do |x|
  x.report { contents = open('d:\handranks.dat', "rb") {|io| io.read }; n.times { contents[pos..(pos+3)].unpack("l").first } }
  x.report { contents = open('d:\handranks.dat', "rb") {|io| io.read }; values = contents.unpack("l*"); n.times { values[pos] } }
end

Output:
      user     system      total        real
 13.572000   0.125000  13.697000 ( 13.724785)
  2.512000   0.202000   2.714000 (  2.890166)

Das ergäbe dann sowas wie

class HandLookup
  def initialize
    @contents = open('d:\handranks.dat', "rb") {|io| io.read };
    @contents = @contents[53..-1].unpack("l*")
  end

  def eval_hand_7(ary_cards)
    @contents[ary_cards.inject(:+)]
  end
end

Das macht dann 5 Sekunden für 100.000 Durchläufe, wenn man die Initialisierung weglässt

Wie funktioniert das eigentlich mit @ary_nbr_hand_types? So wie ich das sehe, kann handvalue deutlich größer sein als 2^12, also wird oft auf einen viel zu großen Index zugegriffen.

[codecow]

Nein die eval_hand_7 funktion ist nicht falsch. So funktionieren direkte, azyklische Graphen. Kann man aber nicht wissen.
http://en.wikipedia.org/wiki/Directed_acyclic_graph

Es wird sich also quasi ein Weg durch den Datensatz gesucht. An jeder Station steht eine neue Addresse wo es hingeht daher brauch man die davor nicht mehr bis am Ende der Handrank steht. Wenn du mehr dazu wissen willst guck dir die beiden Links an die ich vorhin gepostet hab.

Und nope handvalue << 12 kann nicht beliebig groß sein

Das format sieht bit-weise betrachtet so aus:
hhhhrrrrrrrrrrrr
hhhh = 1 high card -> 9 straight flush
r..r = rank within the categorie 1 to max of 2861

So ich hab den Datensatz jetzt auch in ein Array gepackt und krieg damit so 50000 Hände pro Sekunde hin. Das sind bei 9 Spielern aber leider immer noch nur ca. 5000 Simulationen die Sekunde. Wird wohl doch auf C/C++ rauslaufen.

Mein Code sieht übrigens jetzt so aus. Vorhin war es am fehlenden binmode fuer IO::read und der automatischen crlf Konvertierung gescheitert. Darum hatte ich schwachsinnige Werte die wiederum auf ne Stelle im String gezeigt haben die viel zu groß war. Und daher der bignum error.

class HandLookup
  def initialize
    file = File.new(Dir.pwd + "/HandRanks.dat", "rb")
    file.binmode()
    rank_table_string = file.read()
    file.close()
    @rank_table = rank_table_string.unpack("l*")
  end

  def eval_hand_7(ary_cards)
    p = 53
    ary_cards.each do |pc|
      p = pc + p
      p = @rank_table[p]
    end
    return p
  end
end

Die HandRanks.dat kann man jetzt übrigens downloaden. http://www.megaupload.com/?d=ID3ATVST

[interessant]

Hört sich ja alles echt interessant an, haltet uns mal auf dem laufenden