查看锯齿状数组中的每个组合 [英] Looking at each combination in jagged array
问题描述
遍历具有未知行数和未知每行列数的锯齿状数组中每个可能的元素组合的最快方法是什么?
What is the fastest way to loop through each possible combination of elements in a jagged array with an unknown number of rows, and an unknown number of columns in each row?
这个数组...
char[][] myArray = new char[][]{
new char[] {'A', 'B'},
new char[] {'C', 'D'},
new char[] {'E', 'F'}
};
...将返回组合 ACE、ACF、ADE、ADF、BCE、BCF、BDE 和 BDF.
...would return the combinations ACE, ACF, ADE, ADF, BCE, BCF, BDE, and BDF.
使用 C# 完成此任务的最快方法是什么?
What is the fastest way using C# to accomplish this?
推荐答案
这里是 IMO 一个很好的算法，具有最少的分配(避免字符串连接):
Here is IMO a good algorithm with a minimum allocations (avoids string concatenations):
public static class Algorithms
{
public static IEnumerable<string> GetCombinations(this char[][] input)
{
var result = new char[input.Length];
var indices = new int[input.Length];
for (int pos = 0, index = 0; ;)
{
for (; pos < input.Length; pos++, index = 0)
{
indices[pos] = index;
result[pos] = input[pos][index];
}
yield return new string(result);
do
{
if (pos == 0) yield break;
index = indices[--pos] + 1;
}
while (index >= input[pos].Length);
}
}
}
用法:
char[][] myArray = new char[][]{
new char[] {'A', 'B'},
new char[] {'C', 'D'},
new char[] {'E', 'F'}
};
var combinations = myArray.GetCombinations();
基本上它是这样的东西的展开实现
Basically it's an unrolled implementation of something like this
from c1 in input[0]
from c2 in input[1]
...
from cN in input[N]
select new string(new [] { c1, c2, ..., cN })
P.S 如果您确实需要char[] 类型的结果，只需将签名更改为
P.S If you actually need char[] type result, simply change the signature to
public static IEnumerable<char[]> GetCombinations(this char[][] input)
并从 yield 中删除 new string.
但请注意，在这种情况下，如果需要存储组合数组，则可枚举的使用者应负责制作组合数组的副本.从公共 API 设计的角度来看，产生共享的内部变异数组是坏的(邪恶的)，但对于内部性能场景来说是完美的.
But note that in such case the consumer of the enumerable should be responsible of making a copy of the combination array if it needs to store it. Yielding shared internal mutating array is bad (evil) from the public API design standpoint, but perfect for internal performance scenarios.
更新: 由于问题是关于性能的，我做了一个测试，将上述算法 (A) 的字符串版本与 谜题答案(B).我已经针对 VS 之外的 Release 构建的 exe 中不同数量的 26 个字母组合运行了它，结果如下:
UPDATE: Since the question is about the performance, I've made a test to compare the string versions of the above algorithm (A) with the LINQ solution from Enigmativity answer(B). I've ran it against different number of 26 letter alphabet combinations from Release built exe outside the VS, and here are the results:
A: N=2 Count= 676 Time=00:00:00.0010139 Memory= 16K
B: N=2 Count= 676 Time=00:00:00.0042598 Memory= 233K
A: N=3 Count= 17,576 Time=00:00:00.0004310 Memory= 348K
B: N=3 Count= 17,576 Time=00:00:00.0126294 Memory= 2,185K
A: N=4 Count= 456,976 Time=00:00:00.0111155 Memory= 1,496K
B: N=4 Count= 456,976 Time=00:00:00.4019500 Memory= 2,104K
A: N=5 Count= 11,881,376 Time=00:00:00.2813208 Memory= 1,995K
B: N=5 Count= 11,881,376 Time=00:00:13.4492150 Memory= 2,014K
A: N=6 Count= 308,915,776 Time=00:00:07.5473890 Memory= 2,059K
B: N=6 Count= 308,915,776 Time=00:07:37.2985051 Memory= 455K
这里是完整的测试代码，以防有人感兴趣:
Here is the full test code in case someone is interested:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
using System.Threading;
namespace Samples
{
public static class Algorithms
{
public static IEnumerable<string> GetCombinationsA(this char[][] input)
{
var result = new char[input.Length];
var indices = new int[input.Length];
for (int pos = 0, index = 0; ;)
{
for (; pos < input.Length; pos++, index = 0)
{
indices[pos] = index;
result[pos] = input[pos][index];
}
yield return new string(result);
do
{
if (pos == 0) yield break;
index = indices[--pos] + 1;
}
while (index >= input[pos].Length);
}
}
public static IEnumerable<string> GetCombinationsB(this char[][] input)
{
Func<IEnumerable<IEnumerable<char>>, IEnumerable<IEnumerable<char>>> combine = null;
combine = css =>
from c in css.First()
from cs in css.Skip(1).Any()
? combine(css.Skip(1))
: new[] { Enumerable.Empty<char>() }
select new[] { c }.Concat(cs);
return combine(input).Select(c => String.Join("", c));
}
}
class Program
{
class Algorithm
{
public string Name;
public Func<char[][], IEnumerable<string>> Func;
}
static void Main(string[] args)
{
Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
Algorithm[] algorithms =
{
new Algorithm { Name = "A", Func = Algorithms.GetCombinationsA },
new Algorithm { Name = "B", Func = Algorithms.GetCombinationsB },
};
char[][] myArray = { new char[] {'A', 'B'}, new char[] {'C', 'D'}, new char[] {'E', 'F'} };
foreach (var algo in algorithms)
algo.Func(myArray);
var chars = Enumerable.Range('A', 'Z' - 'A' + 1).Select(c => (char)c).ToArray();
for (int n = 2; n < 7; n++)
{
var input = Enumerable.Range(0, n).Select(_ => chars).ToArray();
foreach (var algo in algorithms)
Test(algo, input);
Console.WriteLine();
}
Console.WriteLine("Done.");
Console.ReadLine();
}
static void Test(Algorithm algo, char[][] input)
{
GC.Collect(); GC.WaitForPendingFinalizers();
GC.Collect(); GC.WaitForPendingFinalizers();
var totalMem = GC.GetTotalMemory(false);
var timer = Stopwatch.StartNew();
long count = 0;
foreach (var comb in algo.Func(input)) count++;
timer.Stop();
totalMem = GC.GetTotalMemory(false) - totalMem;
Console.WriteLine($"{algo.Name}: N={input.Length} Count={count,12:n0} Time={timer.Elapsed} Memory={totalMem / 1024,7:n0}K");
}
}
}
这篇关于查看锯齿状数组中的每个组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
