首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >比嵌套循环更快的替代方案?

比嵌套循环更快的替代方案?
EN

Stack Overflow用户
提问于 2015-04-22 14:04:33
回答 12查看 16K关注 0票数 86

我需要创建一个数字组合列表。这个数字非常小,所以我可以使用byte而不是int。然而,它需要许多嵌套循环才能获得所有可能的组合。我想知道有没有更有效的方式来做我想做的事情。到目前为止,代码是:

代码语言:javascript
复制
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等等)是非常重要的,所以使用像Generating Permutations using LINQ这样的解决方案不会有什么帮助,因为每列中的最大值是不同的,
  • 我不是一个数学家,因此,如果我没有正确使用“排列”和“组合”这样的技术术语,我道歉:)
  • I do需要一次填充所有这些组合-我不能仅基于索引抓取一个或另一个使用
  • 使用byte比使用int快,我保证<>E220>它。在内存使用方面,使用67m+字节数组也比使用it
  • 要好得多。我的最终目标是寻找一种更快的替代嵌套循环的方法。
  • 我考虑过使用并行编程,但由于我要实现的是迭代性质,我找不到一种成功的方法(即使使用ConcurrentBag) -尽管我很高兴被证明是错的:)

结论

Caramiriel提供了一个很好的微优化,它减少了一些循环时间,所以我已经标记了这个答案是正确的。Eric还提到,预分配列表的速度更快。但是,在这个阶段,看起来嵌套循环实际上是做这件事最快的方法(令人沮丧,我知道!)。

如果你想尝试我想用StopWatch做基准测试的东西,可以使用13个循环,每个循环最多4个--这使得列表中有大约67m+行。在我的机器(i5-3320M 2.6 the )上,优化后的版本大约需要2.2秒。

EN

回答 12

Stack Overflow用户

回答已采纳

发布于 2015-04-22 14:56:32

提醒一下:在开发自己的解决方案时,您可能不需要这种代码。这可以而且应该只在非常特定的情况下使用。可读性通常比速度更重要。

您可以使用结构的属性并提前分配结构。我在下面的示例中去掉了一些级别,但我相信您将能够弄清楚细节。运行速度比原来的(发布模式)快5-6倍。

区块:

代码语言:javascript
复制
struct ByteBlock
{
    public byte A;
    public byte B;
    public byte C;
    public byte D;
    public byte E;
}

循环:

代码语言:javascript
复制
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[]而不是List<T>

票数 62
EN

Stack Overflow用户

发布于 2015-04-22 18:51:26

您正在做的是计数(使用可变基数,但仍在计数)。

由于您使用的是C#,因此我假设您不想尝试有用的内存布局和数据结构,因为它们会让您真正地对代码进行优化。

所以我在这里发布了一些不同的东西,这可能不适合你的情况,但值得注意的是:如果你实际上以稀疏的方式访问列表,这里有一个类,让你在线性时间内计算第i个元素(而不是像其他答案那样是指数的)。

代码语言:javascript
复制
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;
        }
    }
}

你可以这样使用这个类

代码语言:javascript
复制
Counter c = new Counter();
c.Radices = new int[] { 2,3,4,3,4,3,3,4,2,4,4,3,4};

现在c[i]与您的列表相同,将其命名为ll[i]

正如你所看到的,你可以很容易地避免所有这些循环:)甚至当你整个预先计算所有列表时,因为你可以简单地实现一个进位波纹计数器。

计数器是一个非常研究的课题,我强烈建议你去搜索一些文献。

票数 34
EN

Stack Overflow用户

发布于 2015-04-22 14:22:20

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

代码语言:javascript
复制
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;
}
票数 14
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/29789028

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档