Quick mass-updating a Dictionary

I have a Dictionary<int, int> and would like to update certain elements all at once based on their current values, e.g. changing all elements with value 10 to having value 14 or something.

I imagined this would be easy with some LINQ/lambda stuff but it doesn't appear to be as simple as I thought. My current approach is this:

List<KeyValuePair<int, int>> kvps = dictionary.Where(d => d.Value == oldValue).ToList();
foreach (KeyValuePair<int, int> kvp in kvps)
{
   dictionary[KeyValuePair.Key] = newValue;
开发者_Go百科}

The problem is that dictionary is pretty big (hundreds of thousands of elements) and I'm running this code in a loop thousands of times, so it's incredibly slow. There must be a better way...

---

This might be the wrong data structure. You are attempting to look up dictionary entries based on their values which is the reverse of the usual pattern. Maybe you could store Sets of keys that currently map to certain values. Then you could quickly move these sets around instead of updating each entry separately.

---

I would consider writing your own collection type to achieve this whereby keys with the same value actually share the same value instance such that changing it in one place changes it for all keys.

Something like the following (obviously, lots of code omitted here - just for illustrative purposes):

public class SharedValueDictionary : IDictionary<int, int>
{
   private List<MyValueObject> values;

   private Dictionary<int, MyValueObject> keys;

   // Now, when you add a new key/value pair, you actually
   // look in the values collection to see if that value already
   // exists. If it does, you add an entry to keys that points to that existing object
   // otherwise you create a new MyValueObject to wrap the value and add entries to
   // both collections.
}

This scenario would require multiple versions of Add and Remove to allow for changing all keys with the same value, changing only one key of a set to be a new value, removing all keys with the same value and removing just one key from a value set. It shouldn't be difficult to code for these scenarios as and when needed.

---

You need to generate a new dictionary:

d = d.ToDictionary(w => w.Key, w => w.Value == 10 ? 14 : w.Value)

---

I think the thing that everybody must be missing is that it is exceeeeedingly trivial:

List<int> keys = dictionary.Keys.Where(d => d == oldValue);

You are NOT looking up keys by value (as has been offered by others). Instead, keys.SingleOrDefault() will now by definition return the single key that equals oldValue if it exists in the dictionary. So the whole code should simplify to

if (dictionary.ContainsKey(oldValue))
   dictionary[key] = newValue;

That is quick. Now I'm a little concerned that this might indeed not be what the OP intended, but it is what he had written. So if the existing code does what he needs, he will now have a highly performant version of the same :)

---

After the edit, this seems an immediate improvement:

foreach (var kvp in dictionary.Where(d => d.Value == oldValue))
{
   kvp.Value = newValue;
}

I'm pretty sure you can update the kvp directly, as long as the key isn't changed