# Efficient solution for dictionary updates

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

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

• So, if I understand it correctly, U is small, X is large, X mostly consists of 0 values, but it's important to differentiate between 0 value and no value. Is that right? Dec 18, 2013 at 15:52
• @svick Actually, X is large and consists of zeros, except for the values of the keys that are present in U. The problem is to update X efficiently, knowing only what is new, remembering that changes made to X in the preceding update have to be reversed. Dec 18, 2013 at 21:55

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

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.

You can make this more efficient by developing a specialised data structure. Let X' be a pair (D,S) where D is a dictionary and S is a set. It corresponds to the dictionary X of your example by the following substitutions:

• there is no keys bound to 0 in D
• if a key is bound in D then X' behaves as if it were X and that binding were also in X
• if a key is not bound in D but in S then X' behaves as if it were X and that key were bound to 0 in X.

You can define the lookup and update operations as.

`````` lookup(key):
if key is bound in D then D[key] elseif key is in S then 0 else Not_found

update(U):
set D to U
add all keys bound in U to S
``````

If U is quite small, this will improve the performance: if your dictionary X is implemented with a hashtable and grows very large, you have many hash collisions and lookup time behaves as O(N). With X' key lookup is O(size(U)) + O(log N) which becomes O(log N) if the size of U is bounded.

• Common hash-table based dictionaries (I know `Dictionary<K, V>` in .Net certainly behaves this way) grow the hash table when it's too full. That way, the number of collisions is kept small, and lookup is still O(1) (assuming good `GetHashCode()`). Dec 18, 2013 at 15:57