Linq - convert an ILookup into another ILookup

Question

This should be simple, but I can't think of a good way to do it. How do you transform an ILookup into another ILookup? For example, how would you copy/clone an ILookup, producing another ILookup with the same keys and same groups?

Here's my lame attempt:

static ILookup<TKey, TValue> Copy<TKey, TValue>(ILookup<TKey, TValue> lookup)
{
    return lookup
        .ToDictionary(
            grouping => grouping.Key,
            grouping => grouping.ToArray())
        .SelectMany(pair =>
            pair
                .Value
                .Select(value =>
                    new KeyValuePair<TKey, TValue>(pair.Key, value)))
        .ToLookup(pair => pair.Key, pair => pair.Value);
}

Can anyone improve this?

-- Brian

score 4 · Answer 1 · answered Nov 07 '10 at 03:33

4

How about this:

return lookup
  .SelectMany (grp => grp, (grp, item) => new { grp.Key, item})
  .ToLookup (x => x.Key, x => x.item);

answered Nov 07 '10 at 03:33

Joe Albahari

30,118
7
80
91

Ah, nice. That works and it's certainly an improvement over mine, but it shares the same weakness - it instantiates an intermediate object for each element of the lookup. Is there some way to do it with pure enumeration? – Brian Berns Nov 07 '10 at 04:30
Yes - LINQ queries will often instantiate intermediate objects. The performance cost rarely works out to be a big deal, though. – Joe Albahari Nov 07 '10 at 08:23
Joe: You are right about the performance costs. In most situations you would need to have many, many millions of items in your `Lookup` before noticing the effect of the intermediate objects because they are so short-lived. – Gabe Nov 08 '10 at 04:41

Gabe · Accepted Answer · 2010-11-07T05:52:29.490

Does this do what you want?

static ILookup<TKey, TValue> Copy<TKey, TValue>(ILookup<TKey, TValue> lookup)
{
    return lookup.
           SelectMany(g => g,
                     (g, v) => new KeyValuePair<TKey, TValue>(g.Key, v)).
           ToLookup(kvp => kvp.Key, kvp => kvp.Value);
}

Of course, if you want to transform the values somehow, maybe you want something like this:

static ILookup<TKey, TValueOut> Transform<TKey, TValue, TValueOut>(
       ILookup<TKey, TValue> lookup,
       Func<TValue, TValueOut> selector)
{
    return lookup.
           SelectMany(g => g,
                      (g, v) => new KeyValuePair<TKey, TValueOut>(g.Key, selector(v))).
           ToLookup(kvp => kvp.Key, kvp => kvp.Value);
}

Note that this method holds intermediate values in a KeyValuePair which, being a value type, is stored on the stack and thus doesn't require any intermediate memory allocations. I profiled a test that creates a Lookup<int,int> with 100 keys, each having 10,000 items (for a total of 1,000,000).

Creating the Lookup does 1610 allocations.
Copying it with my method does 1712 allocations (all the allocations required to create it plus one for each delegate in the SelectMany call and one for the enumerator for each key).
Copying it with anonymous objects instead of KeyValuePair does 1,001,712 allocations (all the allocations required to copy plus one for each item).

CPU-wise, even with 100,000 elements per key in the Lookup performance between the two copying methods was identical. With 1,000,000 elements per key, the performance was different between the two methods:

5.1 sec to create
5.9 sec to copy with KeyValuePair
6.3 sec to copy with anonymous objects

Nope. That doesn't even compile. The problem is that x is an IGrouping, so you're building an ILookup>. — Brian Berns, Nov 07 '10 at 04:22
brianberns: You're right, it needs the `SelectMany` step. Note that I used `KeyValuePair` which is a value type, so it doesn't create a new object for every element in the `Lookup`. — Gabe, Nov 07 '10 at 04:38
Yep. You and Joe A. came up with (essentially) the same answer. But do you think there's a way to do it that doesn't require instantiating new objects? — Brian Berns, Nov 07 '10 at 04:42
brianberns: Which objects are you trying to avoid instantiating? The only `new` in there instantiates a `KeyValuePair` which should stay on the stack and not produce any garbage. — Gabe, Nov 07 '10 at 04:48
brianberns: I just checked and determined that my method only allocates one object per key above and beyond the amount required to create the `Lookup` in the first place. — Gabe, Nov 07 '10 at 05:57

Linq - convert an ILookup into another ILookup

2 Answers2