3

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

  • 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? – svick Dec 18 '13 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. – Macin Dec 18 '13 at 21:55
9

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.

4

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.

  • 1
    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()). – svick Dec 18 '13 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.