3
\$\begingroup\$

Poker is 52 cards - 4 suite and 13 rank:

  • Hand is exaclty 5 cards
  • Order of hands
  • Straight-flush - all same suite and in order
  • Quad four of same rank
  • Boat three of one rank and two of another rank
  • Straight e.g. 56789
    Ace 0 counts as both low and high 01234 and 9,10,11,12,0
  • Two pair
  • One pair
  • High card

This code gives the correct answers to Poker hand probability.

There are 2,598,960 distinct 5 card hands in a deck of 52. I am not interested in a random sampling (Monte Carlo).

Can it be made faster? Right now it runs in 4 seconds, and 2.5 of the 4 seconds is loading the Dictionary. The results of the Dictionary make tally of straight and same rank easy / fast. The raw loop with no hand evaluation is only 0.019 seconds. I know 4 seconds is fast but the next step is a situation where I need to do a very similar analysis millions of times.

//  all the counts are the output 
int counter = 0;
int counterFlush = 0;
int counterStraight = 0;
int counterStraightFlush = 0;
int counterQuad = 0;
int counterBoat = 0;
int counterTrips = 0;
int counterPairTwo = 0;
int counterPairOne = 0;
int counterHigh = 0;
//  end output 
Dictionary<int, int> rankCount = new Dictionary<int,int>(5);
int card1rank; 
int card1suit;
int card2rank;
int card2suit;
int card3rank;
int card3suit;
int card4rank;
int card4suit;
int card5rank;
int card5suit;
bool haveStraight;
bool haveFlush;
for(int i = 51; i >= 4; i--)
{         
    card1rank = i % 13;
    card1suit = i / 13;
    for (int j = i - 1; j >= 3; j--)
    {
        card2rank = j % 13;
        card2suit = j / 13;
        for (int k = j - 1; k >= 2; k--)
        {
            card3rank = k % 13;
            card3suit = k / 13;
            for (int l = k - 1; l >= 1; l--)
            {
                card4rank = l % 13;
                card4suit = l / 13;
                for (int m = l - 1; m >= 0; m--)
                {
                    counter++;
                    //if (rand.Next(4) != 0)
                    //     continue;
                    haveStraight = false;
                    haveFlush = false;
                    card5rank = m % 13;
                    card5suit = m / 13;

                    if (card1suit == card2suit && card1suit == card3suit && card1suit == card4suit && card1suit == card5suit)
                    {
                        haveFlush = true;
                    }

                    rankCount.Clear();
                    rankCount.Add(card1rank, 1);

                    if (rankCount.ContainsKey(card2rank))
                        rankCount[card2rank]++;
                    else
                        rankCount.Add(card2rank, 1);

                    if (rankCount.ContainsKey(card3rank))
                        rankCount[card3rank]++;
                    else
                        rankCount.Add(card3rank, 1);

                    if (rankCount.ContainsKey(card4rank))
                        rankCount[card4rank]++;
                    else
                        rankCount.Add(card4rank, 1);

                    if (rankCount.ContainsKey(card5rank))
                        rankCount[card5rank]++;
                    else
                        rankCount.Add(card5rank, 1);
                    //continue;

                    if (rankCount.Count == 5)
                    {   // can only have a straight if the count is 5
                        if (rankCount.Keys.Max() - rankCount.Keys.Min() == 4)
                        {
                            haveStraight = true;
                        }
                        else if (rankCount.Keys.Min() == 0 && rankCount.Keys.Max() == 12)
                        {   // possible ace high straight 
                            if (rankCount.Keys.OrderBy(x => x).FirstOrDefault(x => x > 0) == 9)
                            {
                                haveStraight = true;
                            }
                        }
                    }

                    if (haveStraight && haveFlush)
                        counterStraightFlush++;
                    else if (haveFlush)
                        counterFlush++;
                    else if (haveStraight)
                        counterStraight++;
                    else if (rankCount.Count == 5)
                        counterHigh++;  // cannot have and pairs if the count is 5
                    else
                    {                                    
                        bool quap = false;
                        bool trips = false;
                        int pair = 0;
                        foreach (KeyValuePair<int, int> kvp in rankCount.OrderByDescending(x => x.Value))
                        {
                            if (kvp.Value == 4)
                                quap = true;
                            else if (kvp.Value == 3)
                                trips = true;
                            else if (kvp.Value == 2)
                                pair++;
                        }
                        if (quap)
                            counterQuad++;
                        else if (trips)
                        {
                            if (pair > 0)
                                counterBoat++;
                            else
                                counterTrips++;
                        }
                        else if (pair == 2)
                            counterPairTwo++;
                        else if (pair == 1)
                            counterPairOne++;
                        else 
                            counterHigh++;  // should not actually get here
                    }                               
                }
            }
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Four seconds is an eternity. \$\endgroup\$ – RubberDuck Jul 23 '16 at 0:12
  • 1
    \$\begingroup\$ I am almost certain that you can actually do this by doing the math instead of brute forcing every possible combination. Brute forcing it will never be as efficient as simply doing the math. Besides, some context for the code would help: how are you calling it? \$\endgroup\$ – asibahi Jul 23 '16 at 5:12
  • 1
    \$\begingroup\$ Would you edit your question please so that the method is complete and add an example how to use it? \$\endgroup\$ – t3chb0t Jul 23 '16 at 9:32
  • 1
    \$\begingroup\$ ok, it runs... next question: which variables store the results? \$\endgroup\$ – t3chb0t Jul 23 '16 at 9:51
  • 2
    \$\begingroup\$ Trying to make it run faster without knowing where the results are and being able to verify them is kind of pointless ;-] \$\endgroup\$ – t3chb0t Jul 23 '16 at 10:03
6
\$\begingroup\$

Brute force approaches like this are usually processor bound. Looking at your code, you have a collection of counter information and a bunch of temporary stuff. A simple way to increase the speed is to parallelise the algorithm.

Start by defining a wrapper for your counter information:

public class Counters
{
    public int counter = 0;
    public int counterFlush = 0;
    public int counterStraight = 0;
    public int counterStraightFlush = 0;
    public int counterQuad = 0;
    public int counterBoat = 0;
    public int counterTrips = 0;
    public int counterPairTwo = 0;
    public int counterPairOne = 0;
    public int counterHigh = 0;
}

Then create a simple wrapper around the outermost loop of your code:

public static Counters CalculateHands()
{
    Stopwatch sw = new Stopwatch();  // Stopwatch code doesn't belong here...
    sw.Start();
    // Declare array to hold computed sums
    var results = new Counters[51 - 3];
    // Use Parallel.For (notice we're working upwards because that's the
    // way it likes it).  This replaces your outer for loop.  
    // The contents of the for loop have been pushed into the CalculateRound
    // method

    Parallel.For(4, 52, i =>
    {
        var result = CalculateRound(i);
        results[i - 4] = result;
    });

    // Merge the partials into a final result
    var counters = new Counters();

    foreach(var c in results)
    {
        counters.counter += c.counter;
        counters.counterBoat += c.counterBoat;
        counters.counterFlush += c.counterFlush;
        counters.counterHigh += c.counterHigh;
        counters.counterPairOne += c.counterPairOne;
        counters.counterPairTwo += c.counterPairTwo;
        counters.counterQuad += c.counterQuad;
        counters.counterStraight += c.counterStraight;
        counters.counterStraightFlush += c.counterStraightFlush;
        counters.counterTrips += c.counterTrips;
    }

    sw.Stop();

    // Output code omitted

    return counters;
}

The calculate counters method is simply a wrapper around the inner section of your for loop, along with the temporary variables it needs:

static Counters CalculateRound(int i)
{
    var counters = new Counters();
    Dictionary<int, int> rankCount = new Dictionary<int, int>(5);
    int card1rank;
    int card1suit;
    int card2rank;
    int card2suit;
    int card3rank;
    int card3suit;
    int card4rank;
    int card4suit;
    int card5rank;
    int card5suit;
    bool haveStraight;
    bool haveFlush;
    card1rank = i % 13;
    card1suit = i / 13;
    for (int j = i - 1; j >= 3; j--)
    {
        card2rank = j % 13;
        card2suit = j / 13;
        for (int k = j - 1; k >= 2; k--)
        {
            card3rank = k % 13;
            card3suit = k / 13;
            for (int l = k - 1; l >= 1; l--)
            {
                card4rank = l % 13;
                card4suit = l / 13;
                for (int m = l - 1; m >= 0; m--)
                {
                    counters.counter++;
                    //if (rand.Next(4) != 0)
                    //     continue;
                    haveStraight = false;
                    haveFlush = false;
                    card5rank = m % 13;
                    card5suit = m / 13;

                    if (card1suit == card2suit && card1suit == card3suit && card1suit == card4suit && card1suit == card5suit)
                    {
                        haveFlush = true;
                    }

                    rankCount.Clear();
                    rankCount.Add(card1rank, 1);

                    if (rankCount.ContainsKey(card2rank))
                        rankCount[card2rank]++;
                    else
                        rankCount.Add(card2rank, 1);

                    if (rankCount.ContainsKey(card3rank))
                        rankCount[card3rank]++;
                    else
                        rankCount.Add(card3rank, 1);

                    if (rankCount.ContainsKey(card4rank))
                        rankCount[card4rank]++;
                    else
                        rankCount.Add(card4rank, 1);

                    if (rankCount.ContainsKey(card5rank))
                        rankCount[card5rank]++;
                    else
                        rankCount.Add(card5rank, 1);
                    //continue;

                    if (rankCount.Count == 5)
                    {   // can only have a straight if the count is 5
                        if (rankCount.Keys.Max() - rankCount.Keys.Min() == 4)
                        {
                            haveStraight = true;
                        }
                        else if (rankCount.Keys.Min() == 0 && rankCount.Keys.Max() == 12)
                        {   // possible ace high straight 
                            if (rankCount.Keys.OrderBy(x => x).FirstOrDefault(x => x > 0) == 9)
                            {
                                haveStraight = true;
                            }
                        }
                    }

                    if (haveStraight && haveFlush)
                        counters.counterStraightFlush++;
                    else if (haveFlush)
                        counters.counterFlush++;
                    else if (haveStraight)
                        counters.counterStraight++;
                    else if (rankCount.Count == 5)
                        counters.counterHigh++;  // cannot have and pairs if the count is 5
                    else
                    {
                        bool quap = false;
                        bool trips = false;
                        int pair = 0;
                        foreach (KeyValuePair<int, int> kvp in rankCount.OrderByDescending(x => x.Value))
                        {
                            if (kvp.Value == 4)
                                quap = true;
                            else if (kvp.Value == 3)
                                trips = true;
                            else if (kvp.Value == 2)
                                pair++;
                        }
                        if (quap)
                            counters.counterQuad++;
                        else if (trips)
                        {
                            if (pair > 0)
                                counters.counterBoat++;
                            else
                                counters.counterTrips++;
                        }
                        else if (pair == 2)
                            counters.counterPairTwo++;
                        else if (pair == 1)
                            counters.counterPairOne++;
                        else
                            counters.counterHigh++;  // should not actually get here
                    }
                }
            }
        }
    }
    return counters;
}

Obviously, there's other optimisations that might work, as you've discussed in your own answer. However on my machine, using your output metrics, I go from:

hand count            2,598,960
stopwatch millisec    1,190
straightFlush counter 40        0.0015
quad count            624       0.0240
boat count            3,744     0.1441 0.0000
flush counter         5,108     0.1965
straight counter      10,200    0.3925
trips count           54,912    2.113
two pair count        123,552   4.754
one pair counter      1,098,240 42.26
high card counter     1,302,540 50.12 0.0000
sum                   2,598,960
stopwatch millisec    1,190

to:

hand count            2,598,960
stopwatch millisec    577
straightFlush counter 40        0.0015
quad count            624       0.0240
boat count            3,744     0.1441 0.0000
flush counter         5,108     0.1965
straight counter      10,200    0.3925
trips count           54,912    2.113
two pair count        123,552   4.754
one pair counter      1,098,240 42.26
high card counter     1,302,540 50.12 0.0000
sum                   2,598,960
stopwatch millisec    577

for very little effort/change in approach.

\$\endgroup\$
  • \$\begingroup\$ I put this parallel on my Array (not Dictionary) answer. I think parallel is the way to go. However it was actually slower as I am on a single CPU. But the typical user would be on a multi-core machine. Would it be OK if I put the Array based CalculateRound in your answer so I could go ahead and accept yours? \$\endgroup\$ – paparazzo Jul 23 '16 at 21:15
  • \$\begingroup\$ @Paparazzi you can do if you want, I actually found the array based solution slower when parallelized than the dictionary version, which is why I went ahead and based it on the original code. Was 650 or so for the array based version on my machine. \$\endgroup\$ – forsvarir Jul 23 '16 at 21:18
4
\$\begingroup\$

I don't know if this affects performance or not, but I have tried redoing the main logic without a Dictionary. I am a bit skittish about using a HashSet, performance-wise, but it is the most convenient way I know to remove duplicates. (Edit: apparently Distinct() is a thing.) I might have made some mistakes in the editing as I am not familiar with Poker, but I believe I didn't ruin any any of your conditionals.

Also I couldn't live with so many indents so I factored the inner logic (after forming the hand) into a separate method. It has so many refs it is scary but since it would be, supposedly, a private method this should have no affect on your API, if you're doing any.

The Card struct is just there to make the logic clearer. It is an internal struct, and therefore it is only visible to the methods inside the class, where I assume this code lives. Since it is a struct it is a value type and I don't think it has an adverse effect on performance. (I could be wrong.)

Edit: finally, I changed the variable names to Wikipedia friendly names

Without further ado:

struct Card
{
    public Card(int rank, int suit)
    {
        Rank = rank;
        Suit = suit;
    }

    public int Rank { get; private set; }
    public int Suit { get; private set; }
}

static void Evaluate()
{
    int counter = 0;
    int flushCount = 0;
    int straightCount = 0;
    int straightFlushCount = 0;
    int fourOfAKindCount = 0;
    int fullHouseCount = 0;
    int threeOfAKindCount = 0;
    int twoPairCount = 0;
    int onePairCount = 0;
    int highCardCount = 0;

    var hand = new Card[5];

    for(int i = 51; i >= 4; i--)
    {
        hand[0] = new Card(i % 13, i / 13);
        for(int j = i - 1; j >= 3; j--)
        {
            hand[1] = new Card(j % 13, j / 13);
            for(int k = j - 1; k >= 2; k--)
            {
                hand[2] = new Card(k % 13, k / 13);
                for(int l = k - 1; l >= 1; l--)
                {
                    hand[3] = new Card(l % 13, l / 13);
                    for(int m = l - 1; m >= 0; m--)
                    {
                        hand[4] = new Card(m % 13, m / 13);
                        counter++;

                        EavluateHandAux(
                            ref flushCount,
                            ref straightCount,
                            ref straightFlushCount,
                            ref fourOfAKindCount,
                            ref fullHouseCount,
                            ref threeOfAKindCount,
                            ref twoPairCount,
                            ref onePairCount,
                            ref highCardCount,
                            hand);
                    }
                }
            }
        }
    }
}

static void EavluateHandAux(
    ref int flushCount,
    ref int straightCount,
    ref int straightFlushCount,
    ref int fourOfAKindCount,
    ref int fullHouseCount,
    ref int threeOfAKindCount,
    ref int twoPairCount,
    ref int onePairCount,
    ref int highCardCount,
    Card[] hand)
{
    var ranks = hand.Select(c => c.Rank).Distinct();

    var isFlush = hand.GroupBy(c => c.Suit).Count() == 1;

    // can only have a straight if the count is 5
    var isStraight =
             ranks.Count() == 5
             && (ranks.Max() - ranks.Min() == 4
                 || (ranks.Min() == 0
                     && ranks.Max() == 12
                     && ranks.OrderBy(x => x).FirstOrDefault(x => x > 0) == 9
                     )
                 );

    if(isStraight && isFlush)
    {
        straightFlushCount++;
    }
    else if(isFlush)
    {
        flushCount++;
    }
    else if(isStraight)
    {
        straightCount++;
    }
    else if(ranks.Count() == 5)
    {
        highCardCount++;  // cannot have and pairs if the count is 5
    }
    else
    {
        var rankGroups = hand.GroupBy(c => c.Rank);

        var pair = rankGroups.Count(g => g.Count() == 2);

        if(rankGroups.Any(g => g.Count() == 4))
        {
            fourOfAKindCount++;
        }
        else if(rankGroups.Any(g => g.Count() == 3))
        {
            if(pair > 0)
            {
                fullHouseCount++;
            }
            else
            {
                threeOfAKindCount++;
            }
        }
        else if(pair == 2)
        {
            twoPairCount++;
        }
        else if(pair == 1)
        {
            onePairCount++;
        }
    }
}

PS. As I said in my comment, the most performant way is not by literally counting every combination, but by simply doing the math. You can cut your calculation time to microseconds if you used equations instead.

\$\endgroup\$
  • \$\begingroup\$ It is prettier cleaner code. Unfortunately the time goes from 3,759 to 18,530 milliseconds. A decline in performance of 4.88x. Still +1. Thanks \$\endgroup\$ – paparazzo Jul 23 '16 at 7:19
1
\$\begingroup\$

Hopefully I will get a better answer but this is what I have so far
Time is cut to 1/3
Short of a radical different approach that I am not aware of not sure can do much more
I got rid of Dictionary that I had identified as the bottleneck in the question

    public void Deals2()
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        //int[,] deck = new int[4, 13];
        //for(int i = 0; i < 52; i ++)
        //    Debug.WriteLine("Suit = " + (i / 13)  + " Rank = " + i % 13);
        int counter = 0;
        int counterFlush = 0;
        int counterStraight = 0;
        int counterStraightFlush = 0;
        int counterQuad = 0;
        int counterBoat = 0;
        int counterTrips = 0;
        int counterPairTwo = 0;
        int counterPairOne = 0;
        int counterHigh = 0;
        //Random rand = new Random();
        //Dictionary<int, int> rankCount = new Dictionary<int, int>(5);
        int card1rank;
        int card1suit;
        int card2rank;
        int card2suit;
        int card3rank;
        int card3suit;
        int card4rank;
        int card4suit;
        int card5rank;
        int card5suit;
        bool haveStraight;
        bool haveFlush;            
        int[] rankArray = new int[13];
        int rankArrayMax;
        int straightCount;
        bool quad;
        bool trips;
        int pairs;
        for (int i = 51; i >= 4; i--)
        {
            card1rank = i % 13;
            card1suit = i / 13;
            for (int j = i - 1; j >= 3; j--)
            {
                card2rank = j % 13;
                card2suit = j / 13;
                for (int k = j - 1; k >= 2; k--)
                {
                    card3rank = k % 13;
                    card3suit = k / 13;
                    for (int l = k - 1; l >= 1; l--)
                    {
                        card4rank = l % 13;
                        card4suit = l / 13;

                        for (int m = l - 1; m >= 0; m--)
                        {
                            counter++;
                            //if (rand.Next(4) != 0)
                            //     continue;
                            haveStraight = false;
                            haveFlush = false;
                            card5rank = m % 13;
                            card5suit = m / 13;

                            if (card1suit == card2suit && card1suit == card3suit && card1suit == card4suit && card1suit == card5suit)
                            {
                                haveFlush = true;
                            }

                            rankArray[0] = 0;
                            rankArray[1] = 0;
                            rankArray[2] = 0;
                            rankArray[3] = 0;
                            rankArray[4] = 0;
                            rankArray[5] = 0;
                            rankArray[6] = 0;
                            rankArray[7] = 0;
                            rankArray[8] = 0;
                            rankArray[9] = 0;
                            rankArray[10] = 0;
                            rankArray[11] = 0; 
                            rankArray[12] = 0;

                            rankArray[card1rank]++;
                            rankArray[card2rank]++;
                            rankArray[card3rank]++;
                            rankArray[card4rank]++;
                            rankArray[card5rank]++;

                            //Debug.WriteLine("rankArray");
                            //foreach (int r in rankArray)
                            //{
                            //    Debug.WriteLine(r);
                            //    if(r > 5)
                            //        Debug.WriteLine("r > 5");
                            //}
                            //Debug.WriteLine("rankArray");

                            //continue;

                            rankArrayMax = 1;
                            straightCount = 0;
                            for (int q = 0; q < 13; q++)
                            {
                                if (rankArray[q] > rankArrayMax)
                                    rankArrayMax = rankArray[q];
                                if (rankArrayMax > 1)
                                    break;  // cannot make a stright if there are any pairs
                                if (rankArray[q] == 1)
                                {
                                    straightCount++;
                                    if (straightCount == 5)
                                        break;
                                }
                                else
                                    straightCount = 0;
                            }
                            if (straightCount == 5 || (straightCount == 4 && rankArray[0] == 1))
                                haveStraight = true;

                            if (haveStraight && haveFlush)
                                counterStraightFlush++;
                            else if (haveFlush)
                                counterFlush++;
                            else if (haveStraight)
                                counterStraight++;
                            else if (rankArrayMax == 1)
                                counterHigh++;
                            else
                            {
                                //continue;
                                quad = false;
                                trips = false;
                                pairs = 0;
                                //foreach (int r in rankArray.OrderByDescending(x => x))  for some reason this was SLOW
                                for (int q = 0; q < 13; q++)
                                {
                                    if (rankArray[q] <= 1)
                                        continue;
                                    //Debug.WriteLine(r);
                                    if (rankArray[q] == 2)
                                        pairs++;
                                    else if (rankArray[q] == 3)
                                        trips = true;
                                    else
                                        quad = true;
                                }

                                if (trips)
                                {
                                    if (pairs > 0)
                                        counterBoat++;
                                    else
                                        counterTrips++;
                                }
                                else if (pairs == 1)
                                    counterPairOne++;
                                else if (pairs == 2)
                                    counterPairTwo++;
                                else
                                    counterQuad++;                                       
                            }
                        }
                    }
                }
            }
        }
        sw.Stop();
        Debug.WriteLine("hand count            " + counter.ToString("N0"));
        Debug.WriteLine("stopwatch millisec    " + sw.ElapsedMilliseconds.ToString("N0"));
        //MessageBox.Show(sw.ElapsedMilliseconds.ToString("N0"), "Deals2");
        //return;
        int sum = counterHigh + counterPairOne + counterPairTwo + counterTrips + counterStraight
                + counterFlush + counterBoat + counterQuad + counterStraightFlush;

        //Debug.WriteLine("supposed to be        " + ((int)2598960).ToString("N0"));
        Debug.WriteLine("straightFlush counter " + counterStraightFlush.ToString("N0") + "        " + (100m * counterStraightFlush / sum).ToString("N4"));
        //Debug.WriteLine("supposed to be        " + ((int)40).ToString("N0"));
        Debug.WriteLine("quad count            " + counterQuad.ToString("N0") + "       " + (100m * counterQuad / sum).ToString("N4"));
        Debug.WriteLine("boat count            " + counterBoat.ToString("N0") + "     " + (100m * counterBoat / sum).ToString("N4") + " " + (100m * ((100m * counterBoat / sum) - 0.144057623049m) / 0.144057623049m).ToString("N4"));
        Debug.WriteLine("flush counter         " + counterFlush.ToString("N0") + "     " + (100m * counterFlush / sum).ToString("N4"));
        //Debug.WriteLine("supposed to be        " + ((int)5148).ToString("N0"));
        Debug.WriteLine("straight counter      " + counterStraight.ToString("N0") + "    " + (100m * counterStraight / sum).ToString("N4"));
        //Debug.WriteLine("supposed to be        " + ((int)10240).ToString("N0")); 
        //Debug.WriteLine("counterStraightTop    " + counterStraightTop.ToString("N0"));
        //Debug.WriteLine("counterStraightTopNot " + counterStraightTopNot.ToString("N0"));
        //Debug.WriteLine("diff striaght         " + (counterStraight - 10240).ToString("N0"));
        Debug.WriteLine("trips count           " + counterTrips.ToString("N0") + "    " + (100m * counterTrips / sum).ToString("N3"));
        Debug.WriteLine("two pair count        " + counterPairTwo.ToString("N0") + "   " + (100m * counterPairTwo / sum).ToString("N3"));
        Debug.WriteLine("one pair counter      " + counterPairOne.ToString("N0") + " " + (100m * counterPairOne / sum).ToString("N2"));
        Debug.WriteLine("high card counter     " + counterHigh.ToString("N0") + " " + (100m * counterHigh / sum).ToString("N2") + " " + (100m * ((100m * counterHigh / sum) - 50.11773940m) / 50.11773940m).ToString("N4"));
        Debug.WriteLine("sum                   " + sum.ToString("N0"));
        sw.Stop();
        Debug.WriteLine("stopwatch millisec    " + sw.ElapsedMilliseconds.ToString("N0"));
        Debug.WriteLine("");
    }
\$\endgroup\$
  • \$\begingroup\$ Ha, I was just about to post a similar answer. It makes it less pretty but you need to get rid of the LINQ and stuff that comes with bloat/too much safety/checking, which might be very fast for most occasions but not if you're doing millions of iterations. Basically I got rid of the Dictionary Contains lookups (though not the Dictionaries themselves) and the Min/Max methods, which cut the time it took nearly in half as well. Getting rid of the rest of the LINQ and the Dictionaries completely as you did would undoubtedly help further. \$\endgroup\$ – 404 Jul 23 '16 at 19:33
  • \$\begingroup\$ @eurotrash Do you see anything in this code that I might be able to tweak? Next I have to optimize for taking the best 5 out of 7. \$\endgroup\$ – paparazzo Jul 23 '16 at 19:35
  • 2
    \$\begingroup\$ @Paparazzi foreach creates an object and calls multiple methods. Doing it with a vanilla for loop might be faster as it does not create an Enumerator. \$\endgroup\$ – asibahi Jul 23 '16 at 19:42
  • 2
    \$\begingroup\$ @Paparazzi Get rid of rankArray.Max() - find the max by comparing the numbers directly. It's much faster (and faster than Math.Max). One thing to experiment with is changing the foreach loops to for loops. foreach loops may compile to the same instructions as for loops, but otherwise can contain a lot more instructions. Try changing it and see if that has any effect. \$\endgroup\$ – 404 Jul 23 '16 at 19:45
  • \$\begingroup\$ @eurotrash OMG, that trimmed another 1/3 off. Posted fresh code. It is doing 1 per millisecond on a slow machine. \$\endgroup\$ – paparazzo Jul 23 '16 at 20:15
-1
\$\begingroup\$

Flushes and straights are pretty rare, so I'd only check for those after you realize you don't have pairs (or trips or boats, etc.).

Consider getting rid of "irregular" trips, quad, pair, etc. and use something like this:

int[] rankCount = new int[5];

rankCount[0] = 0;
rankCount[1] = 0;
rankCount[2] = 0;
rankCount[3] = 0;
rankCount[4] = 0;

// this is unrolled, but think about using a 
// for loop.
rankCount[rankArray[0]] ++;
rankCount[rankArray[1]] ++;
rankCount[rankArray[2]] ++;
rankCount[rankArray[3]] ++;
rankCount[rankArray[4]] ++;
rankCount[rankArray[5]] ++;
rankCount[rankArray[6]] ++;
rankCount[rankArray[7]] ++;
rankCount[rankArray[8]] ++;
rankCount[rankArray[9]] ++;
rankCount[rankArray[10]] ++;
rankCount[rankArray[11]] ++;
rankCount[rankArray[12]] ++;

And then use rankCount[4] == 1 for quad, rankCount[3] == 1 && rankCount[2] = 1 for "Boat", etc.

The theory would be that fewer if and for statements result in less pipeline stalls. Implicit bounds checks on array access might get in your way here, so this may not pay off unless you go with the unsafe/pointer changes.

Doing this before the check for the flush and/or straight would let you skip those checks unless rankCount[1] == 5.

Straights are really special. As soon as you know you have one card that's "out of place" you can stop considering it.

You often get better results if you "unroll" small loops, so I'd try just having 9 if statements.

bool haveStraight = false;
// 0 (ace) is special
if (rankArray[0] > 0)
{
    haveStraight = rankArray[0] == 1 && 
        ((rankArray[1] == 1 && 
        rankArray[2] == 1 && 
        rankArray[3] == 1 && 
        rankArray[4] == 1)
        ||
        (rankArray[9] == 1 && 
        rankArray[10] == 1 && 
        rankArray[11] == 1 && 
        rankArray[12] == 1));
}
// repeat this 8 times for 1,2,3,4,5,6,7,8
else if (rankArray[1] > 0)
{
    haveStraight = rankArray[1] == 1 && 
        rankArray[2] == 1 && 
        rankArray[3] == 1 && 
        rankArray[4] == 1 && 
        rankArray[5] == 1;
}

Obviously, the "repeat this 8 times" would work as a for loop. You'll have to check empirically if the loop overhead is worth the more compact code.

Consider using Array.Clear to clear arrays. My guess is that it will help a little if you're sticking with real arrays (rather than pointers).

Consider using byte (rather than int) for arrays where the count is > 256. I can imagine explicit "unrolled" rankCount[3] == 1 && rankCount[4] == 1 && ... && rankCount[7] == 1 being done by reading bytes 0-7 as a 64-bit int, masking away the all but the relevant bytes with an AND, and doing a 64-bit compare (3 x64 instructions). Also, the processor cache will be more efficient with fewer bytes to reason over.

You may need to use unsafe/pointer arithmetic to avoid array bounds testing overhead (obviously, this is "unsafe" so think twice about taking it to this level).rankArray (and the rankCount array I'm suggesting) could be byte* (or int*) that could be allocated with stackalloc.

Edit:

I tried this and it gave identical results with a significant time improvement.

On my box (using "Release"), Deals2 took 467ms; with all the changes but the ugly loop unroll, it was 305ms (65% of Deals2); with the loop unroll, it was 275ms (58%).

unsafe static public void Deals3()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    //int[,] deck = new int[4, 13];
    //for(int i = 0; i < 52; i ++)
    //    Debug.WriteLine("Suit = " + (i / 13)  + " Rank = " + i % 13);
    int counter = 0;
    int counterFlush = 0;
    int counterStraight = 0;
    int counterStraightFlush = 0;
    int counterQuad = 0;
    int counterBoat = 0;
    int counterTrips = 0;
    int counterPairTwo = 0;
    int counterPairOne = 0;
    int counterHigh = 0;
    //Random rand = new Random();
    //Dictionary<int, int> rankCount = new Dictionary<int, int>(5);
    int card1rank;
    int card1suit;
    int card2rank;
    int card2suit;
    int card3rank;
    int card3suit;
    int card4rank;
    int card4suit;
    int card5rank;
    int card5suit;
    bool haveStraight;
    bool haveFlush;
    byte* rankArray = stackalloc byte[13];
    byte* rankCount = stackalloc byte[5];
    for (int i = 51; i >= 4; i--)
    {
        card1rank = i % 13;
        card1suit = i / 13;
        for (int j = i - 1; j >= 3; j--)
        {
            card2rank = j % 13;
            card2suit = j / 13;
            for (int k = j - 1; k >= 2; k--)
            {
                card3rank = k % 13;
                card3suit = k / 13;
                for (int l = k - 1; l >= 1; l--)
                {
                    card4rank = l % 13;
                    card4suit = l / 13;

                    for (int m = l - 1; m >= 0; m--)
                    {
                        counter++;
                        //if (rand.Next(4) != 0)
                        //     continue;
                        haveStraight = false;
                        haveFlush = false;
                        card5rank = m % 13;
                        card5suit = m / 13;

                        rankArray[0] = 0;
                        rankArray[1] = 0;
                        rankArray[2] = 0;
                        rankArray[3] = 0;
                        rankArray[4] = 0;
                        rankArray[5] = 0;
                        rankArray[6] = 0;
                        rankArray[7] = 0;
                        rankArray[8] = 0;
                        rankArray[9] = 0;
                        rankArray[10] = 0;
                        rankArray[11] = 0;
                        rankArray[12] = 0;

                        rankArray[card1rank]++;
                        rankArray[card2rank]++;
                        rankArray[card3rank]++;
                        rankArray[card4rank]++;
                        rankArray[card5rank]++;

                        //Debug.WriteLine("rankArray");
                        //foreach (int r in rankArray)
                        //{
                        //    Debug.WriteLine(r);
                        //    if(r > 5)
                        //        Debug.WriteLine("r > 5");
                        //}
                        //Debug.WriteLine("rankArray");

                        //continue;

                        rankCount[0] = 0;
                        rankCount[1] = 0;
                        rankCount[2] = 0;
                        rankCount[3] = 0;
                        rankCount[4] = 0;

                        rankCount[rankArray[0]]++;
                        rankCount[rankArray[1]]++;
                        rankCount[rankArray[2]]++;
                        rankCount[rankArray[3]]++;
                        rankCount[rankArray[4]]++;
                        rankCount[rankArray[5]]++;
                        rankCount[rankArray[6]]++;
                        rankCount[rankArray[7]]++;
                        rankCount[rankArray[8]]++;
                        rankCount[rankArray[9]]++;
                        rankCount[rankArray[10]]++;
                        rankCount[rankArray[11]]++;
                        rankCount[rankArray[12]]++;

                        if (rankCount[1] == 5)
                        {
                            haveFlush = card1suit == card2suit &&
                                card1suit == card3suit &&
                                card1suit == card4suit &&
                                card1suit == card5suit;

                            if (rankArray[0] > 0)
                            {
                                haveStraight = rankArray[0] == 1 && (
                                            (rankArray[1] == 1 &&
                                            rankArray[2] == 1 &&
                                            rankArray[3] == 1 &&
                                            rankArray[4] == 1)
                                        ||
                                            (rankArray[9] == 1 &&
                                            rankArray[10] == 1 &&
                                            rankArray[11] == 1 &&
                                            rankArray[12] == 1)
                                        );
                            }
                            else if (rankArray[1] > 0)
                            {
                                haveStraight = rankArray[1] == 1 &&
                                    rankArray[2] == 1 &&
                                    rankArray[3] == 1 &&
                                    rankArray[4] == 1 &&
                                    rankArray[5] == 1;
                            }
                            else if (rankArray[2] > 0)
                            {
                                haveStraight = rankArray[2] == 1 &&
                                    rankArray[3] == 1 &&
                                    rankArray[4] == 1 &&
                                    rankArray[5] == 1 &&
                                    rankArray[6] == 1;
                            }
                            else if (rankArray[3] > 0)
                            {
                                haveStraight = rankArray[3] == 1 &&
                                    rankArray[4] == 1 &&
                                    rankArray[5] == 1 &&
                                    rankArray[6] == 1 &&
                                    rankArray[7] == 1;
                            }
                            else if (rankArray[4] > 0)
                            {
                                haveStraight =
                                    rankArray[4] == 1 &&
                                    rankArray[5] == 1 &&
                                    rankArray[6] == 1 &&
                                    rankArray[7] == 1 &&
                                    rankArray[8] == 1;
                            }
                            else if (rankArray[5] > 0)
                            {
                                haveStraight = rankArray[5] == 1 &&
                                    rankArray[6] == 1 &&
                                    rankArray[7] == 1 &&
                                    rankArray[8] == 1 &&
                                    rankArray[9] == 1;
                            }
                            else if (rankArray[6] > 0)
                            {
                                haveStraight = rankArray[6] == 1 && 
                                    rankArray[7] == 1 &&
                                    rankArray[8] == 1 &&
                                    rankArray[9] == 1 &&
                                    rankArray[10] == 1;
                            }
                            else if (rankArray[7] > 0)
                            {
                                haveStraight = rankArray[7] == 1 &&
                                    rankArray[8] == 1 &&
                                    rankArray[9] == 1 &&
                                    rankArray[10] == 1 &&
                                    rankArray[11] == 1;
                            }
                            else if (rankArray[8] > 0)
                            {
                                haveStraight = rankArray[8] == 1 &&
                                    rankArray[9] == 1 &&
                                    rankArray[10] == 1 &&
                                    rankArray[11] == 1 &&
                                    rankArray[12] == 1;
                            }

                            if (haveStraight && haveFlush)
                                counterStraightFlush++;
                            else if (haveFlush)
                                counterFlush++;
                            else if (haveStraight)
                                counterStraight++;
                            else
                                counterHigh++;
                        }
                        else
                        {
                            if (rankCount[3] == 1)
                            {
                                if (rankCount[2] > 0)
                                    counterBoat++;
                                else
                                    counterTrips++;
                            }
                            else if (rankCount[2] == 1)
                                counterPairOne++;
                            else if (rankCount[2] == 2)
                                counterPairTwo++;
                            else
                                counterQuad++;
                        }
                    }
                }
            }
        }
    }
    sw.Stop();
    Debug.WriteLine("hand count            " + counter.ToString("N0"));
    Debug.WriteLine("stopwatch millisec    " + sw.ElapsedMilliseconds.ToString("N0"));
    //MessageBox.Show(sw.ElapsedMilliseconds.ToString("N0"), "Deals2");
    //return;
    int sum = counterHigh + counterPairOne + counterPairTwo + counterTrips + counterStraight
            + counterFlush + counterBoat + counterQuad + counterStraightFlush;

    //Debug.WriteLine("supposed to be        " + ((int)2598960).ToString("N0"));
    Debug.WriteLine("straightFlush counter " + counterStraightFlush.ToString("N0") + "        " + (100m * counterStraightFlush / sum).ToString("N4"));
    //Debug.WriteLine("supposed to be        " + ((int)40).ToString("N0"));
    Debug.WriteLine("quad count            " + counterQuad.ToString("N0") + "       " + (100m * counterQuad / sum).ToString("N4"));
    Debug.WriteLine("boat count            " + counterBoat.ToString("N0") + "     " + (100m * counterBoat / sum).ToString("N4") + " " + (100m * ((100m * counterBoat / sum) - 0.144057623049m) / 0.144057623049m).ToString("N4"));
    Debug.WriteLine("flush counter         " + counterFlush.ToString("N0") + "     " + (100m * counterFlush / sum).ToString("N4"));
    //Debug.WriteLine("supposed to be        " + ((int)5148).ToString("N0"));
    Debug.WriteLine("straight counter      " + counterStraight.ToString("N0") + "    " + (100m * counterStraight / sum).ToString("N4"));
    //Debug.WriteLine("supposed to be        " + ((int)10240).ToString("N0")); 
    //Debug.WriteLine("counterStraightTop    " + counterStraightTop.ToString("N0"));
    //Debug.WriteLine("counterStraightTopNot " + counterStraightTopNot.ToString("N0"));
    //Debug.WriteLine("diff striaght         " + (counterStraight - 10240).ToString("N0"));
    Debug.WriteLine("trips count           " + counterTrips.ToString("N0") + "    " + (100m * counterTrips / sum).ToString("N3"));
    Debug.WriteLine("two pair count        " + counterPairTwo.ToString("N0") + "   " + (100m * counterPairTwo / sum).ToString("N3"));
    Debug.WriteLine("one pair counter      " + counterPairOne.ToString("N0") + " " + (100m * counterPairOne / sum).ToString("N2"));
    Debug.WriteLine("high card counter     " + counterHigh.ToString("N0") + " " + (100m * counterHigh / sum).ToString("N2") + " " + (100m * ((100m * counterHigh / sum) - 50.11773940m) / 50.11773940m).ToString("N4"));
    Debug.WriteLine("sum                   " + sum.ToString("N0"));
    sw.Stop();
    Debug.WriteLine("stopwatch millisec    " + sw.ElapsedMilliseconds.ToString("N0"));
    Debug.WriteLine("");
}
\$\endgroup\$
  • \$\begingroup\$ This is even worse then the OP's version. repeat this 8 times for 1,2,3,4,5,6,7,8 - we're trying to refactor such copy&paste design patterns here to something maintainable and not the other way round ;-P \$\endgroup\$ – t3chb0t Jul 24 '16 at 8:45
  • \$\begingroup\$ A straight flush beats everything so you have to check for it anyway. A flush is very very cheap check. rankCount[4] == 1 is not a quad. \$\endgroup\$ – paparazzo Jul 24 '16 at 9:10
  • \$\begingroup\$ Was curious how this turned out; cut the time in half. \$\endgroup\$ – Sean Jul 24 '16 at 9:17
  • \$\begingroup\$ Did you get the correct answers? If so please post entire code. \$\endgroup\$ – paparazzo Jul 24 '16 at 9:18
  • \$\begingroup\$ @t3chb0t -- Yeah, I totally hear you. In a perfect world, the optimizer would unroll appropriate loops and keep code pretty and clear. You really need to be sure it's a win before you do it. This is a classic place where it makes sense, though. \$\endgroup\$ – Sean Jul 24 '16 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.