I was reading this question about Lists and deferred execution.
SLaks mentioned you can replace the ToList() in this code with a Join() instead and it'd be much faster.
How can I change this code to use IEnumerable.Join()?
var dic = new Dictionary<int, string>();
for (int i = 0; i < 20000; i++)
{
dic.Add(i, i.ToString());
}
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key).ToList();
var list2 = dic.Where(f => list.Contains(f.Key)).ToList();
You can change the code as shown below
var list = dic.Where(f => f.Value.StartsWith("1")).ToList();
var list2 = dic.Join(list, d=> d.Key, a => a.Key, (d, a) => new {d, a}).Select(m => m.d).ToList();
Yes, the Join would be faster compared to Contains.
To validate run the following program which returns the output as
Test1- Item count: 1111
Time to execute: 100542
Test2- Item count: 1111
Time to execute: 31441
Program:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
public class Program
{
private static void Benchmark(Action act, int iterations)
{
Stopwatch sw = Stopwatch.StartNew();
for (int i = 0; i < iterations; i++)
{
act.Invoke();
}
sw.Stop();
Console.WriteLine("Time to execute: " + (sw.ElapsedTicks).ToString());
}
public static void Test1()
{
var dic = new Dictionary<int, string>();
for(int i=0; i<2000; i++)
{
dic.Add(i, i.ToString());
}
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key).ToList();
var list2 = dic.Where(f => list.Contains(f.Key)).ToList();
Console.WriteLine("Test1- Item count: "+ list2.Count());
}
public static void Test2()
{
var dic = new Dictionary<int, string>();
for(int i=0; i<2000; i++)
{
dic.Add(i, i.ToString());
}
var list = dic.Where(f => f.Value.StartsWith("1")).ToList();
var list2 = dic.Join(list, d=> d.Key, a => a.Key, (d, a) => new {d, a}).Select(m => m.d).ToList();
Console.WriteLine("Test2- Item count: "+ list2.Count());
}
public static void Main(string[] args)
{
Benchmark(()=> Test1(), 1);
Benchmark(() => Test2(), 1);
}
}
The join is much faster because it will internally create a HashSet to perform the lookup, whereas the list.Contains forces an inefficient iteration to find a match.
The current code:
var sw = Stopwatch.StartNew();
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key).ToList();
var list2 = dic.Where(f => list.Contains(f.Key)).ToList();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);
Outputs about 32.4966.
Whereas this:
var sw = Stopwatch.StartNew();
var query =
from f in dic
where f.Value.StartsWith("1")
join x in dic on f.Key equals x.Key
select x;
var list2 = query.ToList();
Console.WriteLine(sw.Elapsed.TotalMilliseconds);
Outputs about 2.4568.
You still need a .ToList() to cause the query to execute.
The first approach has a O(n^2) execution and the second a O(n).
It is simple. But I am not sure if it will be faster it needs to be tested,
var dic = new Dictionary<int, string>();
for (int i = 0; i < 20000; i++)
{
dic.Add(i, i.ToString());
}
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key); //.ToList();
var list2 = (from item in dic
join listItem in list
on item.Key equals listItem
select item).ToList();
Here I have run profiler using the code below:
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int ResultLength = 11111;
const int NElements = 20000;
static readonly int[] RandomArrayOrderCache = RandomArrayOrder();
static readonly Dictionary<int, string> dic = Enumerable.Range(0, NElements).ToDictionary(k => k, v => v.ToString());
static readonly KeyValuePair<int, string>[] UnorderedList =
dic.OrderBy((k) => RandomArrayOrderCache[k.Key]).ToArray();
static int[] RandomArrayOrder()
{
var result = Enumerable.Range(0, NElements).ToArray();
var random = new Random();
for (int i = 0; i <= 10000000; i++)
{
var i1 = random.Next(0, result.Length - 1);
var i2 = random.Next(0, result.Length - 1);
var tmp = result[i1];
result[i1] = result[i2];
result[i2] = tmp;
}
return result;
}
public static List<KeyValuePair<int, string>> TestWithoutToListUsingJoin()
{
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key);// .ToList();
return (from item in dic
join listItem in list
on item.Key equals listItem
select item).ToList();
}
public static List<KeyValuePair<int, string>> TestWithToListUsingJoin()
{
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key).ToList();
return (from item in dic
join listItem in list
on item.Key equals listItem
select item).ToList();
}
public static List<KeyValuePair<int, string>> TestWithToListUsingJoinButRandomizeElementOrder()
{
var list = UnorderedList.Where(f => f.Value.StartsWith("1")).Select(f => f.Key).ToList();
return (from item in dic
join listItem in list
on item.Key equals listItem
select item).ToList();
}
public static List<KeyValuePair<int, string>> TestWithoutToListUsingJoinButRandomizeElementOrder()
{
var list = UnorderedList.Where(f => f.Value.StartsWith("1")).Select(f => f.Key);
return (from item in dic
join listItem in list
on item.Key equals listItem
select item).ToList();
}
public static List<KeyValuePair<int, string>> TestWithToListOldWay()
{
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key).ToList();
return dic.Where(f => list.Contains(f.Key)).ToList();
}
public static List<KeyValuePair<int, string>> TestWithoutToListOldWay()
{
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key);// .ToList();
return dic.Where(f => list.Contains(f.Key)).ToList();
}
public static List<KeyValuePair<int, string>> TestWithoutToListIfItWasUsedWithAReferenceType()
{
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Value);// .ToList();
return (from item in dic
join listItem in list
on item.Value equals listItem
select item).ToList();
}
public static List<KeyValuePair<int, string>> TestWithToListIfItWasUsedWithAReferenceType()
{
var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Value).ToList();
return (from item in dic
join listItem in list
on item.Value equals listItem
select item).ToList();
}
public static void Main(string[] args)
{
long dummy = 0;
long numberOfRetries = 1000;
for (int i = 0; i < numberOfRetries; ++i)
{
dummy += TestWithoutToListUsingJoin().Count;
dummy += TestWithToListUsingJoin().Count;
dummy += TestWithToListOldWay().Count;
// This takes ridicilous amount of time so I am disabling it from this test to compare others better
//dummy += TestWithoutOldWay().Count;
// Added these two to compare the heap vs stack caching effects on times
dummy += TestWithoutToListIfItWasUsedWithAReferenceType().Count;
dummy += TestWithToListIfItWasUsedWithAReferenceType().Count;
dummy += TestWithToListUsingJoinButRandomizeElementOrder().Count;
dummy += TestWithoutToListUsingJoinButRandomizeElementOrder().Count;
}
Environment.Exit(dummy == ResultLength * 7 * numberOfRetries ? 0 : 1);
}
}
Here are the results:
From the results we can see the reason why. Because the first list where you are using on the where clause is a struct list.So it benefits greatly from the CPU cache. But when we use a reference type where the instances spread across the heap then we see the benfit diminishes. Same result we can see on randomly spread keys too. The performance impact you gain using ToList is ordered values in contiguous memory hitting CPU cache mostly,