python - 分布的迭代排列
问题描述
我正在尝试生成各种分布的所有可能组合。
例如,假设您有 5 点可用于 4 个类别,但您最多只能在任何给定类别上花费 2 点。在这种情况下,所有可能的解决方案如下:
[0, 1, 2, 2]
[0, 2, 1, 2]
[0, 2, 2, 1]
[1, 0, 2, 2]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 2, 0, 2]
[1, 2, 1, 1]
[1, 2, 2, 0]
[2, 0, 1, 2]
[2, 0, 2, 1]
[2, 1, 0, 2]
[2, 1, 1, 1]
[2, 1, 2, 0]
[2, 2, 0, 1]
[2, 2, 1, 0]
我已经成功地制作了一个递归函数来实现这一点,但是对于大量的类别,它需要很长时间才能生成。我试图制作一个迭代函数,希望能加快它的速度,但我似乎无法让它考虑到类别最大值。
这是我的递归函数(count = 点,dist = 零填充数组,大小与 max_allo 相同)
def distribute_recursive(count, max_allo, dist, depth=0):
for ration in range(max(count - sum(max_allo[depth + 1:]), 0), min(count, max_allo[depth]) + 1):
dist[depth] = ration
count -= ration
if depth + 1 < len(dist):
distribute_recursive(count, max_allo, dist, depth + 1)
else:
print(dist)
count += ration
解决方案
递归并不慢
递归并不是让它变慢的原因。考虑一个更好的算法
def dist (count, limit, points, acc = []):
if count is 0:
if sum (acc) is points:
yield acc
else:
for x in range (limit + 1):
yield from dist (count - 1, limit, points, acc + [x])
您可以在列表中收集生成的结果
print (list (dist (count = 4, limit = 2, points = 5)))
修剪无效组合
上面,我们使用一个固定范围的limit + 1
,但是看看如果我们用 a (eg) limit = 2
and points = 5
...生成一个组合会发生什么
[ 2, ... ] # 3 points remaining
[ 2, 2, ... ] # 1 point remaining
limit + 1
在这一点上,使用( )的固定范围[ 0, 1, 2 ]
是愚蠢的,因为我们知道我们只剩下 1 点可以花费。这里唯一剩下的选择是0
或1
...
[ 2, 2, 1 ... ] # 0 points remaining
上面我们知道我们可以使用一个空的范围,[ 0 ]
因为没有剩余的积分可以花费。这将阻止我们尝试验证组合,例如
[ 2, 2, 2, ... ] # -1 points remaining
[ 2, 2, 2, 0, ... ] # -1 points remaining
[ 2, 2, 2, 1, ... ] # -2 points remaining
[ 2, 2, 2, 2, ... ] # -3 points remaining
如果count
非常大,这可以排除大量无效组合
[ 2, 2, 2, 2, 2, 2, 2, 2, 2, ... ] # -15 points remaining
为了实现这种优化,我们可以向函数添加另一个参数dist
,但是在 5 个参数时,它会开始看起来很乱。相反,我们引入了一个辅助功能来控制loop
. 添加我们的优化,我们用固定范围换取动态范围min (limit, remaining) + 1
。最后,由于我们知道分配了多少点,我们不再需要测试sum
每个组合的 从我们的算法中删除了另一个昂贵的操作
# revision: prune invalid combinations
def dist (count, limit, points):
def loop (count, remaining, acc):
if count is 0:
if remaining is 0:
yield acc
else:
for x in range (min (limit, remaining) + 1):
yield from loop (count - 1, remaining - x, acc + [x])
yield from loop (count, points, [])
基准
在下面的基准测试中,我们程序的第一个版本被重命名为dist1
使用动态范围的更快的程序dist2
。我们设置了三个测试,small
、medium
和large
def small (prg):
return list (prg (count = 4, limit = 2, points = 5))
def medium (prg):
return list (prg (count = 8, limit = 3, points = 7))
def large (prg):
return list (prg (count = 16, limit = 5, points = 10))
现在我们运行测试,将每个程序作为参数传递。测试注意large
,只完成 1 次通过,因为dist1
需要一段时间才能生成结果
print (timeit ('small (dist1)', number = 10000, globals = globals ()))
print (timeit ('small (dist2)', number = 10000, globals = globals ()))
print (timeit ('medium (dist1)', number = 100, globals = globals ()))
print (timeit ('medium (dist2)', number = 100, globals = globals ()))
print (timeit ('large (dist1)', number = 1, globals = globals ()))
print (timeit ('large (dist2)', number = 1, globals = globals ()))
测试结果small
表明,修剪无效组合并没有太大区别。然而,在medium
和large
情况下,差异是巨大的。我们的旧程序需要 30 多分钟才能完成大型集,但使用新程序只需 1 秒多一点!
dist1 small 0.8512216459494084
dist2 small 0.8610155049245805 (0.98x speed-up)
dist1 medium 6.142372329952195
dist2 medium 0.9355670949444175 (6.57x speed-up)
dist1 large 1933.0877765258774
dist2 large 1.4107366011012346 (1370.26x speed-up)
作为参考框架,每个结果的大小打印在下面
print (len (small (dist2))) # 16 (this is the example in your question)
print (len (medium (dist2))) # 2472
print (len (large (dist2))) # 336336
检查我们的理解
在 和 的large
基准测试中count = 12
,limit = 5
使用我们未优化的程序,我们迭代了 5 12或 244,140,625 种可能的组合。使用我们优化的程序,我们跳过所有无效组合,从而产生 336,336 个有效答案。通过单独分析组合计数,我们发现 99.86% 的可能组合是无效的。如果对每个组合的分析花费相同的时间,由于无效的组合修剪,我们可以预期优化程序的性能至少提高 725.88 倍。
在large
基准测试中,以 1370.26 倍的速度测量,优化后的程序符合我们的预期,甚至超出了预期。额外的加速可能是由于我们取消了调用sum
呼呼格
为了证明这种技术适用于非常大的数据集,请考虑huge
基准。我们的程序在 7 16或 33,232,930,569,601 种可能性中找到 17,321,844 个有效组合。
在这个测试中,我们优化的程序修剪了 99.99479% 的无效组合。将这些数字与之前的数据集相关联,我们估计优化后的程序运行速度比未优化版本快 1,918,556.16 倍。
使用未优化程序的该基准测试的理论运行时间为117.60 年。优化后的程序只需 1 多分钟即可找到答案。
def huge (prg):
return list (prg (count = 16, limit = 7, points = 12))
print (timeit ('huge (dist2)', number = 1, globals = globals ()))
# 68.06868170504458
print (len (huge (dist2)))
# 17321844
推荐阅读
- laravel - 无法使用 axios 将图像上传到外部 API
- r - 消费者支出调查 - 生成日历年人口权重变量
- css - 当 flex-direction 设置为“列”时,什么属性控制宽度?
- javascript - 如何推动元素反应钩子状态数组
- floating-point - 浮点精度和运算顺序
- angular - 如何通过打字稿中的指令阻止垫选择?
- python - Selenium chromedriver python 允许多次下载
- c# - Xamarin.Forms. XAML Label IsVisible condition is not getting evaluated as expected
- r - dplyr::mutate() 的向量化函数
- hyperledger-fabric - Fabric python SDK中关于channel的一些问题