0
\$\begingroup\$

I was trying to write a function that would get a random card from a dictionary of cards in a players deck weighted by the number of cards of each type you have. I don't know if the solution I came up with is the fates way of doing something like this and this is something I'm going to be doing a lot per turn because of certain mechanics in the games design. Please let me know if there is something i missed that could help the performance of this code.

For some contexts _deck._card is a dictionary with the key being a string and the value being a int. Dictionary<string, int> _cards

Also Nez.Random is a singleton of my random class for the project. Random.nextInt(int max) takes in a int for the max value of the random number.

static public int nextInt( int max )
{
    return random.Next( max );
}

Code:

public string GetRandomCard()
{
    string result = "";
    var totalWeight = 0;

    foreach (var cardNumber in _deck._cards)
        totalWeight += cardNumber.Value;

    var randNumber = Nez.Random.nextInt(totalWeight);

    foreach (var cardNumber in _deck._cards)
    {
        var value = cardNumber.Value;

        if (randNumber >= value)
        {
            randNumber -= value;
        }
        else
        {
            result = cardNumber.Key;
            break;
        }
    }
    return result;
}

Time complexity O(N^2) I dont think there is a way to decrease the time complexity but there might be other ways to optimize this code.

\$\endgroup\$
11
  • \$\begingroup\$ The time complexity of this code in currently O(N^2) My question is if there is a way to get this down to O(N). Or if there is just some small improvements in speed I can do. Like I don't know if creating a int is faster using the var keyword or the int keyword, or if there is even a difference in speed (I think the compiler takes care of this so there wont be a difference but I don't know for sure) \$\endgroup\$ Mar 11, 2019 at 15:17
  • \$\begingroup\$ What do you need numCardTypes for when you're not using it? \$\endgroup\$
    – t3chb0t
    Mar 11, 2019 at 16:01
  • \$\begingroup\$ @t3chb0t Oh wow I completely missed that I left that in from my first attempt at this function. I also noticed that I misspelled result. These changes have been corrected in the code now \$\endgroup\$ Mar 11, 2019 at 17:02
  • \$\begingroup\$ I dont know if I should edit my post with these changes or keep it. Anyone know what is common practice here? \$\endgroup\$ Mar 11, 2019 at 17:12
  • \$\begingroup\$ You can edit the code as long as there are no answers. After that, you should no longer do it. It would be great if you corrected it. \$\endgroup\$
    – t3chb0t
    Mar 11, 2019 at 17:14

3 Answers 3

1
\$\begingroup\$

After all this good discussion It looks like this function is as optimize as its going to get for its intended purpose. I want to note that I was incorrect in its time complexity. The time complexity is actually O(N) not O(N^2) luckily.

Considering this algorithm can perform 1,000 random selections in 0.00194s on a mid range workstation It shouldn't have any performance impact if used many times.

Here are the results of the unit test:

Running random 100 times: 0.0013367s
Key: 30%, Value: 35
Key: 60%, Value: 60
Key: 10%, Value: 5

Running random 1000 times: 0.0019477s
Key: 30%, Value: 378
Key: 60%, Value: 618
Key: 10%, Value: 104

Running random 10000 times: 0.0202942s
Key: 30%, Value: 3391
Key: 60%, Value: 6635
Key: 10%, Value: 1074

Running random 100000 times: 0.191678s
Key: 30%, Value: 33669
Key: 60%, Value: 66427
Key: 10%, Value: 11004

Running random 1000000 times: 1.77491s
Key: 30%, Value: 334075
Key: 60%, Value: 666087
Key: 10%, Value: 110938

Running random 10000000 times: 18.43691s
Key: 30%, Value: 3332173
Key: 60%, Value: 6667785
Key: 10%, Value: 1111142
\$\endgroup\$
6
  • \$\begingroup\$ I love it. So often the answer to "How do I optimize this" is "You probably don't need to." Since you took the extra step to actually measure, this time the answer is definite. Plus, you confirmed that the probability distribution is working as you intended. Nicely done. \$\endgroup\$
    – benj2240
    Mar 12, 2019 at 15:48
  • \$\begingroup\$ I'm confused by your results... The sum of your Values doesn't add up to the number of times except for the first case (100). E.g. 1,000 -> 1,100, 10,000 -> 11,000, 100,000 -> 111,100 etc. Do you have a bug in your test or have I misunderstood? \$\endgroup\$
    – RobH
    Mar 12, 2019 at 16:41
  • \$\begingroup\$ @RobH Wow I didn't even notice that. Thank you for pointing that out! Im unable to check the code and test again because it is on my work computer but I will look into once im back at work in 4 days. \$\endgroup\$ Mar 12, 2019 at 16:50
  • \$\begingroup\$ These are exactly the results we would expect if the counters were cumulative across the test runs. \$\endgroup\$
    – benj2240
    Mar 12, 2019 at 16:51
  • \$\begingroup\$ @benj2240 Thats most likely it. I don't remember if I reset the results dic ever time I did the test (I doubt I did). If it is then it would not effect the test in any way, \$\endgroup\$ Mar 12, 2019 at 16:55
1
\$\begingroup\$

You've covered the performance and correctness of your code, so all I can comment on is style.

Linq: When possible, I prefer a declarative style of programming over an imperative style. That is, saying what you want instead of how to calculate it. Linq makes this easy in the case of totalWeight, which could be declared like this:

var totalWeight = _deck._cards.Sum(cardNumber => cardNumber.Value);

Technically the second foreach could also be transformed into a Linq statement, using .Aggregate() and .First()... But I don't recommend it, as in that case I believe it would actually be less readable.


Immediate returns: Between the following two functions, I prefer the latter:

int Foo1(Bar bar)
{
    var answer = 0;

    if (bar != null)
    {
        answer = bar.Baz;
    }

    return answer;
}
int Foo2(Bar bar)
{
    if (bar == null)
    {
        return 0;
    }

    return bar.Baz;
}

In Foo2, I don't have to mentally track the state of the answer variable as I read. Another benefit is that Foo2 scratches that itch I get when I see a bad variable name... "answer" is only a tiny bit more informative than "x", as variable names go.

So I would refactor your code to remove the result variable completely. On the line where you set it, just return cardNumber.Key.


Defaults vs Exceptions: I would also change the line where you return result. Instead, just throw an Exception. You seem to have tested your code pretty well, so you can be confident that the exception will never be thrown... Until the code is refactored, or the card weights are changed to Floats, or who-knows-what.

If that ever happens, an exception saying "The weighted card drawing function failed to select a card" will be easier to debug than an exception saying "Player cannot summon '': invalid unit type."

As a side note, yes I would prefer a third version of my function above. If you're going to fail, fail fast!

int Foo3(Bar bar)
{
    if (bar == null) throw new ArgumentNullException(nameof(bar));

    return bar.Baz;
}
\$\endgroup\$
1
  • \$\begingroup\$ I completely forgot Sum() was a function in dictionary's! As for the Immediate returns I personally prefer the former because returning 0 is a expected response to this call. There are decks that at time will have no cards in them at all (_cards will still be a dictionary just with 0 keys). This point also falls into why this function doesn't need a exception because there is no unexpected result that is still a number. \$\endgroup\$ Mar 12, 2019 at 17:08
0
\$\begingroup\$

Since the original question was about efficiency, here's how you achieve the same thing enumerating the dictionary once...

using System;
using System.Collections.Generic;

namespace CodeReviewFun
{
  static class Program
  {
    private static Random _random = new Random();
    private static Dictionary<string, int> _dict;
    private static Dictionary<string, int> _hits;
    private static int _nCardTypes;
    private static int _nCatds;

    static Program()
    {
      _dict = new Dictionary<string, int>();
      _hits = new Dictionary<string, int>();
      _dict.Add("WarLord", 8);
      _dict.Add("Mage", 3);
      _dict.Add("Dragon", 4);
      _nCardTypes = _dict.Count;
      _nCatds = 0;
      foreach (var cardTypeKey in _dict.Keys)
      {
        _hits.Add(cardTypeKey, 0);
        _nCatds += _dict[cardTypeKey];
      }
    }

    //  The idea is that Value * randomNumber is already weighted
    //  so just remember the key for the most heavily weighted value and the corresponding key
    //  and return that
    public static string GetRandomCard()
    {
      string pick_Key = "";
      int pick_Value = -1;
      foreach (var entry in _dict)
      {
        int pick = _random.Next(_nCardTypes);
        int thisValue = pick * entry.Value;
        if (thisValue > pick_Value)
        {
          pick_Key = entry.Key;
          pick_Value = thisValue;
        }
      }
      return pick_Key;
    }

    static void Main(string[] args)
    {
      const int nSamples = 10000000;
      for (int i = 0; i < nSamples; i++)
      {
        var hitKey = GetRandomCard();
        _hits[hitKey]++;
      }
      foreach (var entry in _hits)
      {
        Console.WriteLine($"{entry.Key, -10}: {entry.Value} ({(double)entry.Value * _nCatds / _nCardTypes})");
      }
      Console.ReadKey();
    }
  }
}

Sample run:

WarLord   : 7037889 (35189445)
Mage      : 1112616 (5563080)
Dragon    : 1849495 (9247475)  
\$\endgroup\$
5
  • \$\begingroup\$ I original had this idea put unfortunately decks are gaining and losing card all the time (It can be up to 100 times per micro turn in some very extreme but possible cases (a micro turn is just a subsection of a turn)) so the weight needs to be calculate every time \$\endgroup\$ Mar 12, 2019 at 17:39
  • \$\begingroup\$ @TylerGregorcyk how large are the decks? how many different types of card are there? \$\endgroup\$ Mar 12, 2019 at 18:00
  • \$\begingroup\$ Then you're heading for trouble. If the totalWeight calculated in the 1st enumeration exceeds the total of the values encountered in the 2nd enumeration pass, then you can generate a random number that exceeds the new total and return a result of "". If this possibility breaks your logic, you should (a) minimise the number of enumeration passes and (b) consider making judicious use of lock(s) to protect the bits of code that update the values. Otherwise you're just setting up a target that you know won't stand still while you're shooting at it. \$\endgroup\$
    – AlanK
    Mar 12, 2019 at 18:12
  • \$\begingroup\$ @VisualMelon These decks very in size from 0-500. This is because the object deck is used for anything that needs cards and needs to be able to move cards around from its self to other decks and vice versa. So for example the players hand is just a deck object and the players playing deck is also a deck object. As to how many cards, as of right now there are planned to be 150 different types of cards but this can be expanded as needed (And most likely will be) \$\endgroup\$ Mar 12, 2019 at 18:13
  • \$\begingroup\$ @AlanK This should not be a issue because all request to move or edit a deck is through a command system and all commands make sure they are on the same thread as the data they are manipulating. \$\endgroup\$ Mar 12, 2019 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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