Difference Between Lookup() and Dictionary(Of List())

Difference between Lookup() and Dictionary(Of list())

Two significant differences:

• Lookup is immutable. Yay :) (At least, I believe the concrete Lookup class is immutable, and the ILookup interface doesn't provide any mutating members. There could be other mutable implementations, of course.)
• When you lookup a key which isn't present in a lookup, you get an empty sequence back instead of a KeyNotFoundException. (Hence there's no TryGetValue, AFAICR.)

They're likely to be equivalent in efficiency - the lookup may well use a Dictionary<TKey, GroupingImplementation<TValue>> behind the scenes, for example. Choose between them based on your requirements. Personally I find that the lookup is usually a better fit than a Dictionary<TKey, List<TValue>>, mostly due to the first two points above.

Note that as an implementation detail, the concrete implementation of IGrouping<,> which is used for the values implements IList<TValue>, which means that it's efficient to use with Count(), ElementAt() etc.

Difference between Lookup() and Dictionary(Of list())

Two significant differences:

• Lookup is immutable. Yay :) (At least, I believe the concrete Lookup class is immutable, and the ILookup interface doesn't provide any mutating members. There could be other mutable implementations, of course.)
• When you lookup a key which isn't present in a lookup, you get an empty sequence back instead of a KeyNotFoundException. (Hence there's no TryGetValue, AFAICR.)

They're likely to be equivalent in efficiency - the lookup may well use a Dictionary<TKey, GroupingImplementation<TValue>> behind the scenes, for example. Choose between them based on your requirements. Personally I find that the lookup is usually a better fit than a Dictionary<TKey, List<TValue>>, mostly due to the first two points above.

Note that as an implementation detail, the concrete implementation of IGrouping<,> which is used for the values implements IList<TValue>, which means that it's efficient to use with Count(), ElementAt() etc.

Difference between ReadOnlyDictionary and Lookup in .Net

Lookups are an easy way to group collections, where you could have one or more values for a given key. A Dictionary gives you one value for a give key, and one value only. Depending on your scenario, it may make most sense to have a Dictionary where you get back one value, or you may want to have a Lookup which would give you a collection of values.

Without a Lookup if you wanted a collection of values for a certain key you'd be stuck with something ugly like

Dictionary<int, IEnumerable<String>>

Yuk. See https://msdn.microsoft.com/en-us/library/bb460184%28v=vs.110%29.aspx?f=255&MSPPError=-2147217396 for more on Lookups.

What is the point of LookupTKey, TElement?

It's a cross between an IGrouping and a dictionary. It lets you group items together by a key, but then access them via that key in an efficient manner (rather than just iterating over them all, which is what GroupBy lets you do).

For example, you could take a load of .NET types and build a lookup by namespace... then get to all the types in a particular namespace very easily:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Xml;

public class Test
{
    static void Main()
    {
        // Just types covering some different assemblies
        Type[] sampleTypes = new[] { typeof(List<>), typeof(string), 
                                     typeof(Enumerable), typeof(XmlReader) };

        // All the types in those assemblies
        IEnumerable<Type> allTypes = sampleTypes.Select(t => t.Assembly)
                                               .SelectMany(a => a.GetTypes());

        // Grouped by namespace, but indexable
        ILookup<string, Type> lookup = allTypes.ToLookup(t => t.Namespace);

        foreach (Type type in lookup["System"])
        {
            Console.WriteLine("{0}: {1}", 
                              type.FullName, type.Assembly.GetName().Name);
        }
    }
}

(I'd normally use var for most of these declarations, in normal code.)

Time complexity for lookup in dictionary.values() lists vs sets

Let be x in s the operation which searches in a list, {x=item , s=list}

The average case - assuming parameters generated uniformly at random - for such operation will be O(n)

For more info about time complexity, here's the official link

Finding difference between two list of dictionary in Python

A set is the perfect solution for this problem. Unfortunately, python will not let you add dictionaries to a set, because they are mutable and their hashcode could change between insert and lookup.

If you "freeze" the items to make them immutable, you can then add them to set objects instead of a list; and then take a set difference using the minus operator:

In [20]: i_set = { frozenset(row.items()) for row in incoming_rows }

In [21]: a_set = { frozenset(row.items())  for row in available_row }

In [22]: (i_set - a_set)
Out[22]: 
{frozenset({('column_name', 'CONFIG_ID'),
            ('data_type', 'numeric(10,0)'),
            ('table_name', 'CONFIG')}),
 frozenset({('column_name', 'CREATE_DATE'),
            ('data_type', 'VARCHAR(20)'),
            ('table_name', 'CONFIG')}),
 frozenset({('column_name', 'CONFIG_TYPE'),
            ('data_type', 'varchar(1)'),
            ('table_name', 'CONFIG')})}

Edit: To unfreeze:

In [25]: [dict(i) for i in i_set - a_set]
Out[25]: 
[{'column_name': 'CONFIG_ID',
  'data_type': 'numeric(10,0)',
  'table_name': 'CONFIG'},
 {'column_name': 'CREATE_DATE',
  'data_type': 'VARCHAR(20)',
  'table_name': 'CONFIG'},
 {'column_name': 'CONFIG_TYPE',
  'data_type': 'varchar(1)',
  'table_name': 'CONFIG'}]

Python: List vs Dict for look up table

Speed

Lookups in lists are O(n), lookups in dictionaries are amortized O(1), with regard to the number of items in the data structure. If you don't need to associate values, use sets.

Memory

Both dictionaries and sets use hashing and they use much more memory than only for object storage. According to A.M. Kuchling in Beautiful Code, the implementation tries to keep the hash 2/3 full, so you might waste quite some memory.

If you do not add new entries on the fly (which you do, based on your updated question), it might be worthwhile to sort the list and use binary search. This is O(log n), and is likely to be slower for strings, impossible for objects which do not have a natural ordering.

Is the Lookup collection faster and more optimized than List of tuples in C#?

Which is faster to loop through with a foreach?

To iterate over, a list will be orders of magnitude faster. Just take a gander at the Lookup.GetEnumerator() function and how much work it's doing because it doesn't store the original elements in a list:

   public IEnumerator<IGrouping<TKey, TElement>> GetEnumerator() {
        Grouping g = lastGrouping;
        if (g != null) {
            do {
                g = g.next;
                yield return g;
            } while (g != lastGrouping);
        }
    }

I actually sat down and wrote a benchmark for it:

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.17763.1282 (1809/October2018Update/Redstone5)
Intel Core i7-8850H CPU 2.60GHz (Coffee Lake), 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=5.0.100-preview.4.20258.7
  [Host]     : .NET Core 3.1.4 (CoreCLR 4.700.20.20201, CoreFX 4.700.20.22101), X64 RyuJIT  [AttachedDebugger]
  DefaultJob : .NET Core 3.1.4 (CoreCLR 4.700.20.20201, CoreFX 4.700.20.22101), X64 RyuJIT

|     Method |      n |           Mean |        Error |       StdDev |    Gen 0 | Gen 1 | Gen 2 | Allocated |
|----------- |------- |---------------:|-------------:|-------------:|---------:|------:|------:|----------:|
| LookupTest |    100 |     2,733.6 ns |     25.08 ns |     22.23 ns |   0.8583 |     - |     - |    4048 B |
|   ListTest |    100 |       263.6 ns |      1.54 ns |      1.20 ns |        - |     - |     - |         - |
| LookupTest |   1000 |    27,185.6 ns |    245.01 ns |    217.20 ns |   8.4839 |     - |     - |   40048 B |
|   ListTest |   1000 |     2,306.6 ns |     22.53 ns |     19.97 ns |        - |     - |     - |         - |
| LookupTest |  10000 |   274,364.4 ns |  5,041.13 ns |  6,554.89 ns |  84.9609 |     - |     - |  400048 B |
|   ListTest |  10000 |    22,903.7 ns |    178.62 ns |    158.34 ns |        - |     - |     - |         - |
| LookupTest | 100000 | 2,774,880.1 ns | 49,165.10 ns | 58,527.55 ns | 847.6563 |     - |     - | 4000008 B |
|   ListTest | 100000 |   231,208.2 ns |  4,449.43 ns |  4,369.93 ns |        - |     - |     - |         - |

Should I use a C# Dictionary if I only need fast lookup of keys, and values are irrelevant?

You can use HashSet<T>.

The HashSet<T> class provides high-performance set operations. A set
is a collection that contains no duplicate elements, and whose
elements are in no particular order.

---

Related Topics