更快的替代嵌套的循环？ [英] Faster alternative to nested loops?

问题描述

我有必要创造数字的组合的列表。这些数字是相当小的，所以我可以用字节，而不是 INT 。然而，它要求以获得每一个可能的组合，许多嵌套循环。我想知道如果有一个更有效的方式做我后。到目前为止的代码是：

I have a need to create a list of combinations of numbers. The numbers are quite small so I can use byte rather than int. However it requires many nested loops in order to get every possible combination. I'm wondering if there's a more efficient manner to do what I'm after. Code so far is:

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 ，但我不知道我怎么能合并它。

I was considering using something like a BitArray but I'm not sure how I could incorporate it.

任何建议将不胜感激。或者，也许这就是做我想做的最快方法是什么？

Any recommendations would be greatly appreciated. Alternatively, perhaps this is the fastest way of doing what I want?

修改
快速点（和道歉的情侣我没T把这些在原岗位）：

EDIT Couple of quick points (and apologies I didn't put these in the original post):

• 的数量和它们的顺序（2，3，4，3，4， 3,3等）是非常重要的，因此，使用使用LINQ 韩元的解决方案，如生成置换'T帮助，因为在每一个最大值'列'是不同的


• 我不是数学家，所以我道歉，如果我不使用技术术语，如置换和组合正确的：）


• 我做需要填充所有这些组合在一次 - 我不能只抓一个或另一个基于指数


• 使用字节比使用 INT ，我保证更快它。这也是好多了内存的使用有个字节，而不是整数


• 我在这里的最终目标是寻找一个更快的替代方案，以嵌套的循环67米+阵列。


• 我考虑过使用并行编程，但是由于我想要达到的迭代特性，我无法找到一个方法来做到这一点成功（甚至 ConcurrentBag ） - 但是我很高兴是错的证明：）

• The numbers and the order of them (2, 3, 4, 3, 4, 3, 3 etc) are very important, so using a solution such as Generating Permutations using LINQ won't help because the maximums in each 'column' are different
• I'm not a mathematician, so I apologise if I'm not using the technical terms like 'permutations' and 'combinations' correctly :)
• I do need to populate all of these combinations at once - I can't just grab one or another based on an index
• Using byte is faster than using int, I guarantee it. It's also a lot better on memory usage to have 67m+ arrays of bytes rather than ints
• My ultimate goal here is to look for a faster alternative to nested loops.
• I considered using parallel programming, but due to the iterative nature of what I'm trying to achieve, I couldn't find a way to do it successfully (even with ConcurrentBag) - however I'm happy to be proved wrong :)

结论

Caramiriel提供了一个良好的微优化其刮胡子一些时间的循环，所以我标志着答案为正确。埃里克还提到，它是更快预分配列表。但是，在这个阶段似乎嵌套循环，其实做这个（郁闷，我知道了！）的最快的方式。

Caramiriel has provided a good micro-optimisation which shaves some time off the loops, so I've marked that answer as correct. Eric also mentioned that it is faster to pre-allocate the List. But, at this stage it seems that the nested loops are in fact the fastest possible way of doing this (depressing, I know!).

如果你想尝试准确我试图用基准秒表，进入13圈每圈数到4 - 这使得在列表中大约67米+线。在我的机器（i5-3320M 2.6GHz的）大约需要2.2S做优化版本。

If you want to try exactly what I was trying to benchmark with StopWatch, go with 13 loops counting up to 4 in each loop - that makes about 67m+ lines in the list. On my machine (i5-3320M 2.6GHz) it takes about 2.2s to do the optimised version.

推荐答案

您可以使用和结构的特性分配事先的结构。我切断下面的示例中的一些的水平，但我敢肯定，你就可以找出细节。 ，运行速度比原来的（释放模式）快约5-6倍。

You can use the properties of a struct and allocate the structure in advance. I cut off some levels in the sample below, but I'm sure you'll be able to figure out the specifics. Runs about 5-6 times faster than the original (release mode).

块：

struct ByteBlock
{
    public byte A;
    public byte B;
    public byte C;
    public byte D;
    public byte E;
}

循环：

The loop:

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;
                }
            }
        }
    }
}

它，因为它不会每次你将它添加到列表中的时间分配一个新的列表的速度更快。还因为它创建该列表中，它需要每隔一个值（A，B，C，D，E）的引用。你可以假设每个值只在循环里修改一次，所以我们可以优化它这样做（数据位置）。

It's faster because it doesn't allocate a new list every time you add it to the list. Also since it's creating this list, it needs a reference to every other value (a,b,c,d,e). You can assume each value is only modified once inside the loop, so we can optimize it to do so (data locality).

另请阅读副作用的注释。

Also read the comments for side-effects.

编辑使用应答的 T [] 代替列表< T> 。

这篇关于更快的替代嵌套的循环？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！