嵌套循环的更快替代？
我需要创build一个数字组合的列表。 数字非常小，所以我可以使用byte而不是int 。 然而，它需要许多嵌套循环，以获得每一个可能的组合。 我想知道是否有更高效的方式去做我以后的事情。 到目前为止的代码是：
var data = new List<byte[]>(); for (byte a = 0; a < 2; a++) for (byte b = 0; b < 3; b++) for (byte c = 0; c < 4; c++) for (byte d = 0; d < 3; d++) for (byte e = 0; e < 4; e++) for (byte f = 0; f < 3; f++) for (byte g = 0; g < 3; g++) for (byte h = 0; h < 4; h++) for (byte i = 0; i < 2; i++) for (byte j = 0; j < 4; j++) for (byte k = 0; k < 4; k++) for (byte l = 0; l < 3; l++) for (byte m = 0; m < 4; m++) { data.Add(new [] {a, b, c, d, e, f, g, h, i, j, k, l, m}); }
我正在考虑使用类似于BitArray东西，但我不知道如何将它纳入。
任何build议将不胜感激。 另外，也许这是做我想做的最快的方式？
编辑几个快速点（和道歉，我没有把这些原来的职位）：
- 它们的数量和顺序（2,3,4,3,4,3,3等）非常重要，所以使用诸如使用LINQ生成排列的解决scheme将无济于事，因为每个“列”中的最大值是不同
- 我不是一个math家，所以我很抱歉，如果我不正确地使用'permutations'和'组合'这样的技术术语:)
- 我确实需要一次填充所有这些组合 – 我不能仅仅根据索引来抓取这些组合
- 使用
byte比使用int更快，我保证它。 内存使用情况也好得多，有67m +的字节数组而不是ints - 我的最终目标是寻找更快的替代嵌套循环。
- 我考虑使用并行编程，但由于我试图实现的迭代性质，我找不到成功的方法（即使与
ConcurrentBag） – 但是我很高兴被certificate是错误的:)
结论
Caramiriel提供了一个很好的微型优化，可以缩短循环的一些时间，所以我将这个答案标记为正确的。 埃里克还提到预分配列表速度更快。 但是，在这个阶段，嵌套循环似乎是最快的方法（令人沮丧，我知道！）。
如果您想尝试使用StopWatch进行基准testing，请在每个循环中进行13次循环计数，最多可达到4次 – 这使得列表中大约有67m +行。 在我的机器（i5-3320M 2.6GHz）大约需要2.2s做优化版本。
您可以使用结构的属性并提前分配结构。 我在下面的示例中删除了一些关卡，但是我相信你能弄清楚具体的细节。 运行速度比原来快了5-6倍（释放模式）。
该块：
struct ByteBlock { public byte A; public byte B; public byte C; public byte D; public byte E; }
循环：
var data = new ByteBlock[2*3*4*3*4]; var counter = 0; var bytes = new ByteBlock(); for (byte a = 0; a < 2; a++) { bytes.A = a; for (byte b = 0; b < 3; b++) { bytes.B = b; for (byte c = 0; c < 4; c++) { bytes.C = c; for (byte d = 0; d < 3; d++) { bytes.D = d; for (byte e = 0; e < 4; e++) { bytes.E = e; data[counter++] = bytes; } } } } }
速度更快，因为每次将其添加到列表中时都不会分配新列表。 另外，因为它正在创build这个列表，所以需要引用其他每个值（a，b，c，d，e）。 你可以假设每个值只在循环中修改一次，所以我们可以优化它（数据局部性）。
同时阅读有关副作用的评论。
编辑答案使用T[]而不是List<T> 。
你正在做的是计数（可变基数，但仍在计数）。
由于您使用的是C＃，我假设您不想使用有用的内存布局和数据结构，以便真正优化代码。
所以在这里，我发布了一些不同的东西，可能不适合你的情况，但值得注意的是：如果你真的以稀疏的方式访问列表，这里有一个类可以让你计算线性时间的第i个元素比其他答案指数）
class Counter { public int[] Radices; public int[] this[int n] { get { int[] v = new int[Radices.Length]; int i = Radices.Length - 1; while (n != 0 && i >= 0) { //Hope C# has an IL-opcode for div-and-reminder like x86 do v[i] = n % Radices[i]; n /= Radices[i--]; } return v; } } }
你可以这样使用这个类
Counter c = new Counter(); c.Radices = new int[] { 2,3,4,3,4,3,3,4,2,4,4,3,4};
现在c[i]和你的列表一样，把它命名为l ， l[i] 。
正如你所看到的，你可以很容易地避免所有这些循环:)即使你预先计算所有的列表，因为你可以简单地实现一个进位纹波计数器。
柜台是一个非常研究的学科，我强烈build议您search一些文学，如果你觉得。
方法1
使其更快的一种方法是指定容量，如果您打算继续使用List<byte[]> ，就像这样。
var data = new List<byte[]>(2 * 3 * 4 * 3 * 4 * 3 * 3 * 4 * 2 * 4 * 4 * 3 * 4);
方法2
此外，您可以直接使用System.Array来获得更快的访问。 如果你的问题坚持认为每一个元素都是物理地存储在内存中，我推荐这种方法。
var data = new byte[2 * 3 * 4 * 3 * 4 * 3 * 3 * 4 * 2 * 4 * 4 * 3 * 4][]; int counter = 0; for (byte a = 0; a < 2; a++) for (byte b = 0; b < 3; b++) for (byte c = 0; c < 4; c++) for (byte d = 0; d < 3; d++) for (byte e = 0; e < 4; e++) for (byte f = 0; f < 3; f++) for (byte g = 0; g < 3; g++) for (byte h = 0; h < 4; h++) for (byte i = 0; i < 2; i++) for (byte j = 0; j < 4; j++) for (byte k = 0; k < 4; k++) for (byte l = 0; l < 3; l++) for (byte m = 0; m < 4; m++) data[counter++] = new[] { a, b, c, d, e, f, g, h, i, j, k, l, m };
这需要596毫秒才能在我的电脑上完成，比有问题的代码（需要658毫秒） 快10.4％ 。
方法3
或者，您可以使用以下技术进行低成本初始化，以适合稀疏访问。 如果仅仅需要某些内容，并且预先确定这些内容，则这是特别有利的。 而且，当内存不足时，像这样的技术可能成为处理更多元素时唯一可行的select。
在这个实现中，每个元素都是在访问时被懒惰地确定的。 当然，这是以访问期间发生的额外CPU为代价的。
class HypotheticalBytes { private readonly int _c1, _c2, _c3, _c4, _c5, _c6, _c7, _c8, _c9, _c10, _c11, _c12; private readonly int _t0, _t1, _t2, _t3, _t4, _t5, _t6, _t7, _t8, _t9, _t10, _t11; public int Count { get { return _t0; } } public HypotheticalBytes( int c0, int c1, int c2, int c3, int c4, int c5, int c6, int c7, int c8, int c9, int c10, int c11, int c12) { _c1 = c1; _c2 = c2; _c3 = c3; _c4 = c4; _c5 = c5; _c6 = c6; _c7 = c7; _c8 = c8; _c9 = c9; _c10 = c10; _c11 = c11; _c12 = c12; _t11 = _c12 * c11; _t10 = _t11 * c10; _t9 = _t10 * c9; _t8 = _t9 * c8; _t7 = _t8 * c7; _t6 = _t7 * c6; _t5 = _t6 * c5; _t4 = _t5 * c4; _t3 = _t4 * c3; _t2 = _t3 * c2; _t1 = _t2 * c1; _t0 = _t1 * c0; } public byte[] this[int index] { get { return new[] { (byte)(index / _t1), (byte)((index / _t2) % _c1), (byte)((index / _t3) % _c2), (byte)((index / _t4) % _c3), (byte)((index / _t5) % _c4), (byte)((index / _t6) % _c5), (byte)((index / _t7) % _c6), (byte)((index / _t8) % _c7), (byte)((index / _t9) % _c8), (byte)((index / _t10) % _c9), (byte)((index / _t11) % _c10), (byte)((index / _c12) % _c11), (byte)(index % _c12) }; } } }
这需要897毫秒才能在我的电脑上完成（还创build并添加到方法2中的一个
Array），这比有问题的代码（这需要658毫秒） 慢大约36.3％ 。
在我的机器上，这会在222 ms vs 760 ms（13 for for循环）中生成组合：
private static byte[,] GenerateCombinations(params byte[] maxNumberPerLevel) { var levels = maxNumberPerLevel.Length; var periodsPerLevel = new int[levels]; var totalItems = 1; for (var i = 0; i < levels; i++) { periodsPerLevel[i] = totalItems; totalItems *= maxNumberPerLevel[i]; } var results = new byte[totalItems, levels]; Parallel.For(0, levels, level => { var periodPerLevel = periodsPerLevel[level]; var maxPerLevel = maxNumberPerLevel[level]; for (var i = 0; i < totalItems; i++) results[i, level] = (byte)(i / periodPerLevel % maxPerLevel); }); return results; }
var numbers = new[] { 2, 3, 4, 3, 4, 3, 3, 4, 2, 4, 4, 3, 4 }; var result = (numbers.Select(i => Enumerable.Range(0, i))).CartesianProduct();
使用http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/上的扩展方法;
public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) { // base case: IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() }; foreach (var sequence in sequences) { // don't close over the loop variable (fixed in C# 5 BTW) var s = sequence; // recursive case: use SelectMany to build // the new product out of the old one result = from seq in result from item in s select seq.Concat(new[] { item }); } return result; }
List在内部有一个数组，它有一个固定的长度。 当您调用List.Add时，会检查是否有足够的空间。 当它不能添加新元素时，它会创build一个更大尺寸的新数组，将所有以前的元素复制过来，然后添加新的元素。 这需要相当多的周期。
既然你已经知道了元素的数量，你可以创build正确大小的列表，这个速度应该已经快了很多。
此外，不知道你如何访问值，但你可以创build一个这样的事情，并保存图像的代码（从磁盘加载它可能会比你现在要做的更慢，你读/写了多less次事情？
这是一个不同的方式，只需要2个循环。 这个想法是增加第一个元素，如果这个数字超过了增加下一个。
您可以使用currentValues.Clone并将该克隆版本添加到您的列表中，而不是显示数据。 对我来说，这跑得比你的版本快。
byte[] maxValues = {2, 3, 4}; byte[] currentValues = {0, 0, 0}; do { Console.WriteLine("{0}, {1}, {2}", currentValues[0], currentValues[1], currentValues[2]); currentValues[0] += 1; for (int i = 0; i <= maxValues.Count - 2; i++) { if (currentValues[i] < maxValues[i]) { break; } currentValues[i] = 0; currentValues[i + 1] += 1; } // Stop the whole thing if the last number is over // } while (currentValues[currentValues.Length-1] < maxValues[maxValues.Length-1]); } while (currentValues.Last() < maxValues.Last());
- 希望这个代码工作，我从vb转换它
你所有的数字都是编译时间不变的。
将所有循环展开到列表中（使用您的程序编写代码）如何：
data.Add(new [] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}); data.Add(new [] {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}); etc.
这应该至less带走for循环的开销（如果有的话）。
我不太熟悉C＃，但似乎有一些序列化对象的方法。 如果你只是生成该列表并以某种forms序列化呢？ 不过，我不确定反序列化是否更快，然后创build列表并添加元素。
你需要的结果是一个数组的数组？ 使用当前的设置，内部数组的长度是固定的，可以用结构replace。 这将允许整个事物被保留作为一个连续的内存块，并提供对元素的更容易的访问（不知道你以后如何使用这个东西）。
下面的方法是更快（我的盒子上的原始41毫秒和1071毫秒）：
struct element { public byte a; public byte b; public byte c; public byte d; public byte e; public byte f; public byte g; public byte h; public byte i; public byte j; public byte k; public byte l; public byte m; } element[] WithStruct() { var t = new element[3981312]; int z = 0; for (byte a = 0; a < 2; a++) for (byte b = 0; b < 3; b++) for (byte c = 0; c < 4; c++) for (byte d = 0; d < 3; d++) for (byte e = 0; e < 4; e++) for (byte f = 0; f < 3; f++) for (byte g = 0; g < 3; g++) for (byte h = 0; h < 4; h++) for (byte i = 0; i < 2; i++) for (byte j = 0; j < 4; j++) for (byte k = 0; k < 4; k++) for (byte l = 0; l < 3; l++) for (byte m = 0; m < 4; m++) { t[z].a = a; t[z].b = b; t[z].c = c; t[z].d = d; t[z].e = e; t[z].f = f; t[z].g = g; t[z].h = h; t[z].i = i; t[z].j = j; t[z].k = k; t[z].l = l; t[z].m = m; z++; } return t; }
那么使用Parallel.For()来运行它呢？ （结构优化荣誉@Caramiriel ）。 我稍微修改了值（a是5而不是2），所以我对结果更有信心。
var data = new ConcurrentStack<List<Bytes>>(); var sw = new Stopwatch(); sw.Start(); Parallel.For(0, 5, () => new List<Bytes>(3*4*3*4*3*3*4*2*4*4*3*4), (a, loop, localList) => { var bytes = new Bytes(); bytes.A = (byte) a; for (byte b = 0; b < 3; b++) { bytes.B = b; for (byte c = 0; c < 4; c++) { bytes.C = c; for (byte d = 0; d < 3; d++) { bytes.D = d; for (byte e = 0; e < 4; e++) { bytes.E = e; for (byte f = 0; f < 3; f++) { bytes.F = f; for (byte g = 0; g < 3; g++) { bytes.G = g; for (byte h = 0; h < 4; h++) { bytes.H = h; for (byte i = 0; i < 2; i++) { bytes.I = i; for (byte j = 0; j < 4; j++) { bytes.J = j; for (byte k = 0; k < 4; k++) { bytes.K = k; for (byte l = 0; l < 3; l++) { bytes.L = l; for (byte m = 0; m < 4; m++) { bytes.M = m; localList.Add(bytes); } } } } } } } } } } } } return localList; }, x => { data.Push(x); }); var joinedData = _join(data);
_join()是一个私有方法，定义如下：
private static IList<Bytes> _join(IEnumerable<IList<Bytes>> data) { var value = new List<Bytes>(); foreach (var d in data) { value.AddRange(d); } return value; }
在我的系统上，这个版本运行速度快了大约6倍（1.718秒，比0.266秒）。
你的一些数字完全符合一个整数倍的位数，所以你可以用上一级的数字“打包”它们：
for (byte lm = 0; lm < 12; lm++) { ... t[z].l = (lm&12)>>2; t[z].m = lm&3; ... }
当然，这使得代码不太可读，但是你保存了一个循环。 这可以做到每次其中一个数字是两个幂，这是你的情况七次。
这是另一个解决scheme。 在VS之外，它的运行速度为437.5 ms，比原始代码（我的电脑上的593.7）快了26％：
static List<byte[]> Combinations(byte[] maxs) { int length = maxs.Length; int count = 1; // 3981312; Array.ForEach(maxs, m => count *= m); byte[][] data = new byte[count][]; byte[] counters = new byte[length]; for (int r = 0; r < count; r++) { byte[] row = new byte[length]; for (int c = 0; c < length; c++) row[c] = counters[c]; data[r] = row; for (int i = length - 1; i >= 0; i--) { counters[i]++; if (counters[i] == maxs[i]) counters[i] = 0; else break; } } return data.ToList(); }
