# Calculating n-ary Cartesian Product too slow

The method gets called extensively throughout my programm, is there any way I can speed it up or improve other aspects?

The code calculates the n-ary Cartesian Product of a List containing n Lists, so that for example:

Product([[1],[2,3],[4,5]]) yields [1,2,4],[1,2,5],[1,3,4],[1,3,5]

public static IEnumerable<T[]> Product<T>(T[][] items)
{
T[] currentItem = new T[items.Length];
static IEnumerable<T[]> go(T[][] items, T[] currentItem, int index)
{
if (index == items.Length)
{
yield return currentItem;
yield break;
}
else
{
foreach (T item in items[index])
{
currentItem[index] = item;
foreach(var j in go(items, currentItem, index + 1))
{
yield return j;
}
}
}

}
return go(items, currentItem, 0);
}


A possible problem i can think of, is the

foreach(var j in go(items, currentItem, index + 1))
{
yield return j;
}


section, since it takes n yields for every (single) array that is part of the n-ary Cartesian Product.

• I must admit that I do not understand what this code does. Usually, it is enough to have two nested loops to create a cartesian product, but here you additionally have a recursive call. Also, a cartesian product is usually done over two sets. What are the two sets here? Can you please explain what your algorithm is supposed to do and how it works? – Olivier Jacot-Descombes Jan 17 at 16:39
• I made an edit to the Post – LukasB97 Jan 17 at 16:53
• Thank you for the edit. How big are the lists? – Olivier Jacot-Descombes Jan 17 at 17:01
• The number of lists( < 15 in my use case) is always greater than the length of one individual list. – LukasB97 Jan 17 at 17:12
• The total number of resulting lists is the product of the lengths of the individual input lists. This can be a huge number with 15 input lists. There is probably nothing wrong with the code. – Olivier Jacot-Descombes Jan 17 at 21:11

The implementation contains one small but important bug (or feature?), it yields the same array instance from each loop.

Consider this example.

int[][] numbers = new[] { new[] { 1 }, new[] { 2, 3 }, new[] { 4, 5 } };

foreach (int[] arr in Product(numbers))
{
Console.WriteLine(string.Join(", ", arr));
}


The output is perfect

1, 2, 4
1, 2, 5
1, 3, 4
1, 3, 5


But if you want to store the result as jagged array and process it later:

foreach (int[] arr in Product(numbers).ToArray())
{
Console.WriteLine(string.Join(", ", arr));
}


You'll get this output

1, 3, 5
1, 3, 5
1, 3, 5
1, 3, 5


That's because it's an array of four references to the same array.

Next small thing is one redundant line of code

yield break;


You don't need it because previous line is the last statement in the method. The method exits after it.

Fix is simple

public static IEnumerable<T[]> Product<T>(T[][] items)
{
T[] currentItem = new T[items.Length];
static IEnumerable<T[]> Go(T[][] items, T[] currentItem, int index)
{
if (index == items.Length)
{
yield return (T[])currentItem.Clone();
}
else
{
foreach (T item in items[index])
{
currentItem[index] = item;
foreach (T[] j in Go(items, currentItem, index + 1))
{
yield return (T[])j.Clone();
}
}
}
}
return Go(items, currentItem, 0);
}


That's it.

Performance while keeping it as returning arrays will be slow because e.g. for 10 arrays of 10 items it will yield 10*10*10*10*10*10*10*10*10*10 = 10000000000 arrays of 10 items each. But you want up to 15. It won't be fast at all.

But let's try to eliminate the recursion.

Consider an alternative implementation of the same

public static IEnumerable<T[]> MyProduct<T>(T[][] items)
{
int length = items.Length;
int[] indexes = new int[length];

while (true)
{
T[] arr = new T[length];
for (int i = 0; i < length; i++)
{
arr[i] = items[i][indexes[i]];
}
yield return arr;

int row = length - 1;
indexes[row]++;
while (indexes[row] == items[row].Length)
{
if (row == 0)
yield break;
indexes[row] = 0;
row--;
indexes[row]++;
}
}
}


To understand this implementation imagine a digital clock. What if you make 3 arrays 24,60,60 items and fill it with numbers from 0 to 23/59. The Product will yield time to display for each second of the day - 86400 arrays of 3 items each. Then imagine how clock counts time on display and you'll catch the idea of this implementation.

Looks like it works

1, 2, 4
1, 2, 5
1, 3, 4
1, 3, 5


And finally let's make a benchmark for both implementations. Using Benchmark.NET of course. For example with 6 arrays of 6 items each.

[MemoryDiagnoser]
public class MyBenckmark
{
private int[][] numbers;

[GlobalSetup]
public void Setup()
{
numbers = new int[6][];
for (int i = 0; i < 6; i++)
{
numbers[i] = Enumerable.Range(i * 6, 6).ToArray();
}
}

[Benchmark]
public void RunProduct()
{
foreach(var _ in Product(numbers)) ;
}

[Benchmark]
public void RunMyProduct()
{
foreach (var _ in MyProduct(numbers)) ;
}

public static IEnumerable<T[]> Product<T>(T[][] items)
{
T[] currentItem = new T[items.Length];
static IEnumerable<T[]> Go(T[][] items, T[] currentItem, int index)
{
if (index == items.Length)
{
yield return (T[])currentItem.Clone();
}
else
{
foreach (T item in items[index])
{
currentItem[index] = item;
foreach (T[] j in Go(items, currentItem, index + 1))
{
yield return (T[])j.Clone();
}
}
}
}
return Go(items, currentItem, 0);
}

public static IEnumerable<T[]> MyProduct<T>(T[][] items)
{
int length = items.Length;
int[] indexes = new int[length];

while (true)
{
T[] arr = new T[length];
for (int i = 0; i < length; i++)
{
arr[i] = items[i][indexes[i]];
}
yield return arr;

int row = length - 1;
indexes[row]++;
while (indexes[row] == items[row].Length)
{
if (row == 0)
yield break;
indexes[row] = 0;
row--;
indexes[row]++;
}
}
}
}


Go!

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i7-4700HQ CPU 2.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.102
[Host]     : .NET Core 3.1.11 (CoreCLR 4.700.20.56602, CoreFX 4.700.20.56604), X64 RyuJIT
DefaultJob : .NET Core 3.1.11 (CoreCLR 4.700.20.56602, CoreFX 4.700.20.56604), X64 RyuJIT

|       Method |      Mean |     Error |    StdDev |     Gen 0 | Gen 1 | Gen 2 | Allocated |
|------------- |----------:|----------:|----------:|----------:|------:|------:|----------:|
|   RunProduct | 28.509 ms | 0.2488 ms | 0.2077 ms | 6750.0000 |     - |     - |  20.08 MB |
| RunMyProduct |  1.274 ms | 0.0103 ms | 0.0086 ms |  712.8906 |     - |     - |   2.14 MB |


You vote.

• Wow, thank you so much, that helped a lot! – LukasB97 Jan 18 at 9:07