C# – Efficient solution for dictionary updates

cdictionary

Let's start with the problem:

There is a large dictionary X that contains {key, value} pairs, i.e.:

X = [{100, 10}, {101, 0}, {103, 0}, {106, 2}, {110, 1}]

Every t seconds, X has to be updated with values from sub dictionary U and 0 set to each value for a key that is not present in new updated U, but was in the previous update.

The most important requirements is, that an update has to be performed in such a way, that the minimum number of update operations of each {key, value} pair in dictionary X have been performed, ie.

X updated by U where

U = [{100, 10}, {102, 5}, {103, 0}, {105, 1}, {110, 0}]

would become:

X = [{100, 10}, {101, 0}, {102, 5}, {103, 0}, {105, 1}, {106, 2}, {110, 0}]

but only following pairs have been updated/added in X:

{102, 5}
{105, 1}
{110, 0}

To make things a bit more interesting, there are few constraints:

  • it is very costly to iterate over dictionary X. Assume X is very large.
  • it is very costly to make an update to {key, value} pair so the task is to minimize this cost.

So that was the problem stated. Here is my solution:

First idea I had was to save the dictionary U after updating X.
On the next update I take each key from Uprev and set it to 0 in X. 

foreach (var pair in Uprev)
{
    X[pair.Key] = 0;
}

After this has been done, I would do a loop to set new values for keys present in new dictionary U:

foreach (var pair in U)
{
    if (X.ContainsKey(pair.Key))
       X[pair.Key] = pair.Value;
    else
       X.Add(pair.Key, pair.Value);
}

So … the question: is there a better solution for the problem I described above? Is it possible to better manage the updates?
Any ideas are welcome, so feel free to post anything that comes to mind.

Thank you for contribution

Best Answer

Instead of 

foreach (var pair in U)
{
    if (X.ContainsKey(pair.Key))
       X[pair.Key] = pair.Value;
    else
       X.Add(pair.Key, pair.Value);
}

use

foreach (var pair in U)
{
     X[pair.Key] = pair.Value;
}

(the index operator [] works like Add when the key does not exist so far). This saves you from one unneccessary dictionary lookup. Beyond that, I would not expect big improvements, since it is obvious that you must visit each element of U once, and your algorithm does that just twice, not more.

Related Topic