我需要创建一个数字组合列表 . 数字很小所以我可以使用 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});
}
我正在考虑使用像_1290192这样的东西,但我不确定如何将其合并 .
任何建议将不胜感激 . 或者,也许这是做我想要的最快的方式?
EDIT 几个快点(道歉我没有把这些放在原帖中):
-
它们的数量和顺序(2,3,4,3,4,3,3等)非常重要,因此使用诸如Generating Permutations using LINQ赢得't help because the maximums in each '列的解决方案是不同的
-
我'm not a mathematician, so I apologise if I'我没有正确使用'permutations'和'combinations'这样的技术术语:)
-
我 do 需要一次填充所有这些组合 - 我不能只根据索引 grab 一个或另一个
-
使用
byte
比使用int
更快,我 guarantee 它 . 在内存使用方面,使用67m字节数组而不是整数也要好得多 -
我的最终目标是寻找嵌套循环的更快替代方案 .
-
我考虑过使用并行编程,但是由于我已经找到了成功的方法(即使使用了
ConcurrentBag
)的迭代性质 - 但是我很高兴被证明是错误的:)
CONCLUSION
Caramiriel提供了一个很好的微优化,可以在一段时间内完成循环,因此我将答案标记为正确 . Eric还提到预先分配List更快 . 但是,在这个阶段,似乎嵌套循环实际上是最快的方式(令人沮丧,我知道!) .
如果你想尝试使用 StopWatch
进行基准测试,那么在每个循环中使用13个循环计数最多4个 - 这使得列表中的行数大约为67m . 在我的机器上(i5-3320M 2.6GHz),优化版本需要大约2.2秒 .
12 回答
你的一些数字完全适合整数位数,所以你可以用上面的数字“打包”它们:
当然,这会使代码的可读性降低,但是您保存了一个循环 . 这可以在每次其中一个数字是2的幂时完成,在您的情况下是七次 .
您可以使用结构的属性并提前分配结构 . 我在下面的示例中删除了一些级别,但我相信您将能够找出具体细节 . 运行速度比原始速度快5-6倍(释放模式) .
块:
循环:
它更快,因为每次将它添加到列表时它都不会分配新列表 . 此外,由于它正在创建此列表,因此需要引用其他所有值(a,b,c,d,e) . 您可以假设每个值仅在循环内修改一次,因此我们可以对其进行优化(数据位置) .
另请阅读副作用的评论 .
编辑答案使用
T[]
而不是List<T>
.你正在做的是计数(使用可变基数,但仍在计算) .
由于您使用的是C#,我假设您不希望使用有用的内存布局和数据结构来让您优化代码 .
所以在这里我发布了一些不同的东西,这可能不适合你的情况,但值得注意的是:如果你实际上以稀疏的方式访问列表,这里有一个让你在线性时间内计算第i个元素的类(而不是比其他答案的指数)
你可以这样使用这个类
现在
c[i]
与您的列表相同,将其命名为l
,l[i]
.正如您所看到的,您可以轻松避免所有这些循环:)即使您预先计算了所有列表,因为您可以简单地实现Carry-Ripple计数器 .
计数器是一个非常研究的主题,如果你觉得,我强烈建议你搜索一些文献 .
您是否需要将结果作为数组数组?使用当前设置,内部阵列的长度是固定的,可以用结构替换 . 这将允许整个事物被保留为一个连续的内存块,并提供更容易访问的元素(不知道你如何使用这个东西) .
下面的方法要快得多(41毫秒对比我盒子上的原件1071毫秒):
Method 1
提高速度的一种方法是,如果您打算继续使用
List<byte[]>
,请指定容量,如下所示 .Method 2
此外,您可以直接使用
System.Array
来获得更快的访问速度 . 如果您的问题坚持要求每个元素都在内存中预先填充,我建议使用此方法 .Method 3
或者,您可以使用以下技术进行低成本初始化,以便以稀疏方式进行访问 . 当仅需要一些元素并且预先确定它们全部被认为是不必要时,这是特别有利的 . 此外,这些技术可能成为处理更多大量元素时唯一可行的选择记忆短缺 .
在该实现中,在访问时,每个元素在运行中被懒惰地确定 . 当然,这是以访问期间产生的额外CPU为代价的 .
在我的机器上,这会生成222 ms vs 760 ms(13 for for循环)的组合:
在http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/使用扩展方法
List在内部有一个数组,它存储它的值,具有固定的长度 . 当您调用List.Add时,它会检查是否有足够的空间 . 当它无法添加新元素时,它将创建一个更大尺寸的新数组,复制所有之前的元素,然后添加新元素 . 这需要相当多的周期 .
既然您已经知道了元素的数量,那么您可以创建正确大小的列表,这应该快得多 .
另外,不确定如何访问这些值,但你可以创建一个这样的东西,并将图像保存在代码中(从磁盘加载它可能比你现在做的慢 . 你现在多少次读/写事情?
这是一种只需要2个循环的不同方式 . 想法是增加第一个元素,如果这个数字超过了增加下一个元素 .
您可以使用currentValues.Clone并将该克隆版本添加到列表中,而不是显示数据 . 对我来说,这比你的版本跑得快 .
你的所有数字都是编译时间常数 .
如何将所有循环展开到列表中(使用您的程序编写代码):
这至少应该消除for循环的开销(如果有的话) .
我对C#不太熟悉,但似乎有一些序列化对象的方法 . 如果你刚刚生成了List并以某种形式序列化了怎么办?我不确定反序列化是否比创建List和添加元素更快 .
使用
Parallel.For()
运行它怎么样? (结构优化赞誉为 @Caramiriel ) . 我略微修改了值(a是5而不是2)所以我对结果更有信心 ._join()
是一个私有方法,定义如下:在我的系统上,这个版本的运行速度大约快6倍(1.718秒对0.266秒) .
这是另一种解决方案 . 在VS之外,它的运行速度最快为437.5毫秒,比原始代码快了26%(在我的计算机上为593.7):