更快替代嵌套循环？

Question

我需要创建一个数字组合列表.数字很​​小所以我可以使用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但我不确定如何将其合并.

任何建议将不胜感激.或者,也许这是做我想要的最快的方式？

编辑 几个快速点(道歉我没有把这些放在原帖中):

• 它们的数量和顺序(2,3,4,3,4,3,3等)非常重要,因此使用诸如使用LINQ生成排列的解决方案将无济于事,因为每个"列"中的最大值是不同
• 我不是数学家,所以如果我没有正确使用'permutations'和'组合'之类的技术术语,我会道歉:)
• 我确实需要一次填充所有这些组合 - 我不能只根据索引获取一个或另一个
• 使用byte比使用更快int,我保证.拥有67m +字节数组而不是整数,在内存使用方面也要好得多
• 我的最终目标是寻找嵌套循环的更快替代方案.
• 我考虑过使用并行编程,但是由于我想要实现的迭代性,我找不到成功的方法(即使有ConcurrentBag) - 但是我很高兴被证明是错的:)

结论

Caramiriel提供了一个很好的微优化,可以在一段时间内完成循环,因此我将答案标记为正确.Eric还提到预先分配List更快.但是,在这个阶段,似乎嵌套循环实际上是最快的方式(令人沮丧,我知道!).

如果你想要尝试我试图用的基准测试StopWatch,那么在每个循环中使用13个循环计数最多4个 - 这使得列表中的行数大约为67m +.在我的机器上(i5-3320M 2.6GHz),优化版本需要大约2.2秒.

Answer 1

您可以使用结构的属性并提前分配结构.我在下面的示例中删除了一些级别,但我相信您将能够找出具体细节.运行速度比原始速度快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;
                }
            }
        }
    }
}

它更快,因为每次将它添加到列表时它都不会分配新列表.此外,由于它正在创建此列表,因此需要引用其他所有值(a,b,c,d,e).您可以假设每个值仅在循环内修改一次,因此我们可以对其进行优化(数据位置).

另请阅读副作用的评论.

编辑答案使用T[]而不是a List<T>.

Answer 2

你正在做的是计数(使用可变基数,但仍在计算).

由于使用的是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].

正如您所看到的,您可以轻松避免所有这些循环:)即使您预先计算了所有列表,因为您可以简单地实现Carry-Ripple计数器.

计数器是一个非常研究的主题,如果你觉得,我强烈建议你搜索一些文献.

Answer 3

在我的机器上,这会生成222 ms vs 760 ms(13 for for循环)的组合:

private static byte[,] GenerateCombinations(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;
}

Answer 4

方法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毫秒才能在我的计算机上完成,这比所讨论的代码快了大约10.4%(需要658毫秒).

方法3

或者,您可以使用以下技术进行低成本初始化,以便以稀疏方式进行访问.当仅需要一些元素并且预先确定它们全部被认为是不必要时,这是特别有利的.此外,当内存不足时,这些技术可能成为处理更大元素时唯一可行的选择.

在该实现中,在访问时,每个元素在运行中被懒惰地确定.当然,这是以访问期间产生的额外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毫秒来完成我的计算机上(也创建&加入到Array如在方法2),大约是一个较慢的36.3%比有问题的代码(这需要658ms).

Answer 5

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

Answer 6

List在内部有一个数组,它存储它的值,具有固定的长度.当您调用List.Add时,它会检查是否有足够的空间.当它无法添加新元素时,它将创建一个更大尺寸的新数组,复制所有之前的元素,然后添加新元素.这需要相当多的周期.

既然您已经知道了元素的数量,那么您可以创建正确大小的列表,这应该快得多.

另外,不确定如何访问这些值,但你可以创建一个这样的东西,并将图像保存在代码中(从磁盘加载它可能比你现在做的慢.你现在多少次读/写事情？

Answer 7

这是一种只需要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转换它