Random Access by Position of Key/Value Pairs in .NET (C#)

Question

I am currently developing a program that uses C#'s Dictionary container (specifically, SortedDictionary). This container works very well for my purposes except for one specific case because I want random access. Specifically, I am generating a random position using a pseudorandom number generator and I need to be able to access that value in the SortedDictionary. At the point that this happens, I do not have a key value.

I could potentially switch to a List which would solve this problem, but would create problems in the rest of the algorithm where SortedDictionary works quite well. Any suggestions/solutions would be much appreciated.

I am currently developing Visual Studio 2005.

Thank you.

Answer 1

Will pulling a random key work?

var randValue = myDictionary.Values.ToList()[myRandomInt];

Edit:

Seems the keys collection and values collection are both IEnumerables so you can't use [] operators. This is the best it gets it seems.

Edit:

Without Linq... Perhaps expensive, but you could copyto array and then pull a value at an index

System.Collections.Generic.KeyValuePair<string, int>[] dictCopy = new System.Collections.Generic.KeyValuePair<string, int>[myDictionary.Count];
myDictionary.CopyTo(dictCopy, 0);
var randValue = dictCopy[myRandomInt].Value;

Answer 2

You can use a SortedList and it has a Values collection which you may access through an integer index.

Answer 3

Linq could do this for you:

int n = GetRandomIndex();
object item = dictionary.ElementAt(n).Value;

Answer 4

    public TValue GetRandomElement<TKey, TValue>(SortedDictionary<TKey, TValue> dict)
    {
        Random randGen = new Random();
        int randIndex = randGen.Next(dict.Values.Count);
        int i = 0;
        foreach (TValue value in dict.Values)
        {
            if (i++ == randIndex)
                return value;
        }

        // this shouldn't happen unless I have a bug above or you are accessing the dictionary from multiple threads
        return default(TValue);
    }

Blindly enumerating the ValueCollection is not the most efficient thing in the world. But it gets the job done. If this is a frequent operation in your scenario, you should consider a hybrid data structure that has the performance characteristics needed for both dictionary lookup and random access.

Answer 5

You don't provide enough information to come up with a solution. How many elements, how often are you going to do this, do you have memory/speed constraints? BTree, SortedList, inserting special nodes in the SortedDictionary could all be useful