Need help finding an efficient way to group the keys in a dictionary into buckets defined by the values in the dictionary?

Question

I have a dictionary in the form of Dictionary<int, List<int>>

The problem is that I need to group the keys together into buckets defined by the value (List<int>). It is easier to explain with an example.

Consider the dictionary:

{
    1: [5,4]
    2: [4]
    3: [10]
}

Out of this, I need the dictionary:

{
    5: [1]
    4: [2, 1]
    10: [3]
}

The approach I took for this is to basically flatten the input dictionary, producing many key value pairs

 1: 5
 1: 4
 2: 4
 3: 10

And then grouping on the value (getting the correct result.)

The problem with this approach is that it takes a long time, and I cannot parallelize it.

The LINQ query I wrote for this is:

Dictionary<int, List<int>> test = <Some init data set>;
test.SelectMany(x => x.Value.Select(y => Tuple.Create(x.Key, y)))
 .GroupBy(x=>x.Item2).ToDictionary(x=>x.Key, x=>x.ToList());

Is there a better / more efficient way to do this? My concern is that by flattening the list in the value operand, I am creating a lot of records, and therefore this algorithm will probably not scale very well?

Thanks!

EDIT:

More information:

Here is some background information about the problem as a whole.

The dictionary is actually a def-use chain; where the key is a reference to a statement that define some data, and the value is a list of references to statements use the data produced by the statement from this definition. Since the code that this optimizer works with is obfuscated, the def-use chain is unusually large (ie, not consistent with what a def-use chain would be on code that someone would normally write.) Therefore, there are an unusual amount of definitions in the def-use chain.

I am trying to build a graph so I can ask: I need this statement here, so what other statements do I also need to carry along with me to keep that statement valid (FWIW, the code is in Static Single Assignment form.)

So to build this graph, I create a Node for each statement in the application. Then I:

1. Flatten the def-use chain (list of, for each statement that produces data, where is that data used)
2. group by uses (For each use of produced data, what are the required definitions)
3. For each use, connect to its respective required definition

Now we essentially have the graph, I can forward traverse at any node to find all statements I need to keep for that node to remain "valid". I used some tricks to make building and traversing the graph very cheap, but #2 is by far the bottle-neck here.

The code that I am working with (ie, statements etc) are purposely crafted to make computations like this not cheap. Ie, this is not normal code written by a person.

Also, this application has a lot of resources to its disposal (many cores 30+, 30GB+ memory.) So really, I am looking for an algorithm that can scale (ie, with a even larger def-use chain.)

Answer 1

I can't provide a real explanation for what is going on, but in my rough tests, the only method I can find which parallelises well is one based on a parallel sort. A (fairly simple) version with a concurrent dictionary doesn't perform poorly, but it's not as good. The trick seems to be to simply minimise the number of dictionary lookups, because while we might assume its O(1), it's not perfect and it will be jumping all over the memory and messing with the caching. The sort, on the other hand, will be either QuickSort or MergeSort, both of which spend most of their time looking at things that are near one-another (I hope). The methods that don't parallelise well also don't run well in parallel as separate instances: this suggests it is not any locking/data contention that is slowing them down, but rather they are simply limited by the rate at which my computer can supply them with numbers from widely distributed locations in memory.

The parallel-sorting method is to stuff all the pairs in a list, perform a parallel sort, and then efficiently load that list into a dictionary by scanning through the list: this means that the number of lookups ceases to depend upon the number elements per record, only the number of records.

The test data I am using is a dictionary of up to N records, where each entry has on average 1/µ elements (I tried µ=0.1 and µ=0.01). Note that sorting is O(nm log (nm), so in theory should scale worse than a dictionary based method (~O(nm) assuming a good hash), but for n >= 1M it is significantly faster than all other methods with my randomly generated test data.

All my test code and some (sparse) results can be found in this gist: https://gist.github.com/VisualMelon/0ac1a1fd6e2db1273fb1d49a32d234ce

The 'winning' method is as follows:

public static void Merge<T>(KeyValuePair<T, T>[] a, KeyValuePair<T, T>[] b, KeyValuePair<T, T>[] res) where T : IComparable<T>
{
    int i = 0;
    int j = 0;
    int k = 0;

    while (true)
    {
        var morea = i < a.Length;
        var moreb = j < b.Length;

        if (morea & moreb)
        {
            if (a[i].Key.CompareTo(b[j].Key) > 0)
            {
                res[k++] = b[j++];
            }
            else
            {
                res[k++] = a[i++];
            }
        }
        else if (morea)
        {
            while (i < a.Length)
                res[k++] = a[i++];
        }
        else if (moreb)
        {
            while (j < b.Length)
                res[k++] = b[j++];
        }
        else
        {
            break;
        }
    }
}

public static Dictionary<T, List<T>> ParallelSorts<T>(Dictionary<T, List<T>> data, int threadNumber) where T : IComparable<T>
{
    var kvs = new List<KeyValuePair<T, T>>();
    foreach (var kv in data)
    {
        var k = kv.Key;
        foreach (var v in kv.Value)
        {
            kvs.Add(new KeyValuePair<T, T>(v, k));
        }
    }

    if (kvs.Count == 0)
    {
        return new Dictionary<T, List<T>>();
    }

    int threads = 1 << threadNumber;

    int[] partitions = new int[threads + 1];
    for (int pi = 0; pi < threads; pi++)
    {
        partitions[pi] = (kvs.Count * pi) / threads;
    }
    partitions[threads] = kvs.Count;

    var subLists = new KeyValuePair<T, T>[threads][];

    var tasks = new Action[threads];
    for (int pi = 0; pi < threads; pi++)
    {
        var _pi = pi;
        var sl = subLists[pi] = new KeyValuePair<T, T>[partitions[_pi + 1] - partitions[_pi]];
        tasks[_pi] = () =>
        {
            kvs.CopyTo(partitions[_pi], sl, 0, sl.Length);
            Array.Sort(sl, (a, b) => a.Key.CompareTo(b.Key));
        };
    }
    Parallel.Invoke(tasks);

    for (int stride = 1; stride < threads; stride *= 2)
    {
        tasks = new Action[threads / (stride * 2)];
        for (int pi = 0; pi < threads; pi += stride * 2)
        {
            var a = subLists[pi];
            var b = subLists[pi + stride];
            var res = subLists[pi] = new KeyValuePair<T, T>[a.Length + b.Length];
            subLists[pi + stride] = null;
            tasks[pi / (stride * 2)] = () => Merge(a, b, res);
        }
        Parallel.Invoke(tasks);
    }

    var dictionary = new Dictionary<T, List<T>>();

    var kvs2 = subLists[0];
    var l = new List<T>();
    T lastKey = kvs2[0].Key;
    for (int i = 0; i < kvs2.Length; i++)
    {
        var next = kvs2[i];
        if (next.Key.CompareTo(lastKey) != 0)
        {
            dictionary.Add(lastKey, l);
            lastKey = next.Key;
            l = new List<T>() { next.Value };
        }
        else
        {
            l.Add(next.Value);
        }
    }
    dictionary.Add(lastKey, l);

    return dictionary;
}

No real effort was made to optimise this implementation. It could probably be improved by using a decent parallel sort. The parallel sort here involves sorting even partitions of the data with concurrent calls to Array.Sort, before merging them (partly in parallel for >= 4 threads).

Other methods in the gist include one based on @BionicCode's LINQ, 2 methods based on dictionary merges as described by @Kain0_0, and a 'naive' serial loop (which outperforms all the linq methods), and a couple of others. The only method I would personally consider using for large volumes (apart from the parallel sort) is the one based on a concurrent dictionary: it is really simple and seems to perform well when m is large.

Generally it seems that increasing n makes life worse than increasing m in proportion. This makes sense, because increasing n increases the size of the dictionaries, while increasing m just increases the sizes of the lists.

Of course, my numbers may not generalise to a machine with better RAM, a bigger cache, more cores, on 'real' data, with no other processes running, not on a weekday, even larger n etc. etc. but I thought the numbers were sufficiently interesting that I should write this up. Maybe someone can explain better what is going on (or point out some deficiencies in my tests).

Answer 2

You can slightly improve the LINQ performance by using Enumerable.ToLookup or Enumerable.GroupBy instead of Enumerable.ToDictionary.

When you plan to iterate over the grouped result, then using Enumerable.GroupBy offers the best performance, as it offers pure lazy evaluation:

Dictionary<int, List<int>> input = <Some init data set>;

IEnumerable<IGrouping<int, int>> lazyQuery = input
  .SelectMany(entry => entry.Value.Select(value => Tuple.Create(value, entry.Key)))
  .GroupBy(tuple => tuple.Item1, tuple => tuple.Item2);

foreach (IGrouping<int, int> group in lazyQuery)
{
  var key = group.Key;
  foreach (int value in group)
  {        
    // A Collection of e.g. 3,000,000 items is enumerated here for the first time, 
    // realizing each individual (per item) query result using the generator `yield return`.
    // This means calling break after the second iteration will only execute the LINQ for two items instead of 3,000,000.
  }
}

If you prefer to use the grouped collection as lookup table then use Enumerable.ToLookup:

Dictionary<int, List<int>> input = <Some init data set>;

// Query executes immediately, realizing all items
ILookup<int, int> lookupTable = input
  .SelectMany(entry => entry.Value.Select(value => Tuple.Create(value, entry.Key)))
  .ToLookup(tuple => tuple.Item1, tuple => tuple.Item2);

IEnumerable<int> valuesOfGroup = lookupTable[10];

foreach (int value in valuesOfGroup)
{        
}

LINQ generally uses deferred execution also called lazy evaluation. myItems.Select(item => item.X) will not immediately execute i.e. materialize. Only when explicitly enumerated by an Enumerator or when a realizer extension method is invoked. This lazy evaluation is implemented using the generator yield return. This generator allows big collection being enumerated in real-time by each query being applied item by item during each iteration.

Some realizer methods that immediately materialize the collection (execute the comoplete query). ToList(), ToDictionary(), Count()orToLookup()are some of them. Realizers are generallyEnumeratorconstructs likeforeach. Applying such a realizer on an IEnumerable` forces it to be evaluated by the compiler.

You did that twice in your query: first by calling ToList() and then by calling ToDictionary. This results in two complete iterations. One over the complete outer collection of IGrouping<int, int> items and the second to realize each individual group's items: ToDictionary(x=>x.Key, x=>x.ToList());

The improvement in the first solution is that the whole query (and sub queries) is deferred -> lazy evaluation. When iterating over the deferred query, the query is executed item by item, allowing to break after N realized items without wasting resources to materialize the complete collection.

The second solution query returns a ILookup<int, int>where ILookup implements IEnumerable. Compared to the original approach it eliminates the GroupBy, ToList and ToDictionary calls. Considering that ToLookup kind of wraps the combination of GroupBy and ToDictionary you still eliminated the extra iterations resulted by the call to ToList.

I appears that the data is generated, so that you can't control the data structure of the generated data. An improved data structure could improve/simplify data handling significantly, of course.
Your described scenario would perfectly benefit from having the data generator generating relational database tables instead of a simple (one way) lookup table. But it seems you are stuck to generate the reverse table yourself.

Answer 3

Divide and Conquor

Split the first set up into batches.

{
    1: [5,4] //<batch 1

    2: [4]   //<batch 2
    3: [10]  //<batch 2
}

Use an appropriate parallelisation technique (tasks, thread pool, etc...).

Each of the batches have the same sub problem. Apply a standard double for loop and construct the index.

// batch 1
{
    4: [1]
    5: [1] 
}

// batch 2
{
    4: [2]   
    10: [3]
}

Now catenate the dictionaries. Best done two at a time. If the key only exist in one dictionary then preserve the entry into the new dictionary. If it is in both merge their lists, and add to the new dictionary.

You can optimise this by not even bothering with having a new dictionary. The left hand dictionary simple has new keys inserted into it, or its key's values are appended to.

{
    4: [1, 2] //< append to list
    5: [1]    //< preexisting
    10: [3]   //< new key
}

This algorithm is still O(N), but if it can be perfectly executed in parallel can achieve a runtime of roughly O(logN). However caveats.

This presumes a dictionary data structures that has O(1) insert and O(N) merge qualities, as well as a List with O(1) catenation. If not blow out the runtime to O(N) or O(N^2).

The constant, and scaled overhead in parallelisation are large so this won't help much on small data sets, and is probably counter productive.