Randomly pick key from dictionary weighted by the keys value

Question

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.

Answer 1

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

Answer 2

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;
}

Answer 3

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)