在 Python 中高效地生成词典系列
Generate lexicographic series efficiently in Python
我想生成一个字典序列的数字,这样每个数字的数字总和就是一个给定的常量。有点类似于'subset sum problem'。例如,如果我希望生成 sum = 3 的 4 位数字,那么我有一个类似的系列:
[3 0 0 0]
[2 1 0 0]
[2 0 1 0]
[2 0 0 1]
[1 2 0 0] ...等等。
我使用以下代码在 Python 中成功完成:
import numpy as np
M = 4 # No. of digits
N = 3 # Target sum
a = np.zeros((1,M), int)
b = np.zeros((1,M), int)
a[0][0] = N
jj = 0
while a[jj][M-1] != N:
ii = M-2
while a[jj][ii] == 0:
ii = ii-1
kk = ii
if kk > 0:
b[0][0:kk-1] = a[jj][0:kk-1]
b[0][kk] = a[jj][kk]-1
b[0][kk+1] = N - sum(b[0][0:kk+1])
b[0][kk+2:] = 0
a = np.concatenate((a,b), axis=0)
jj += 1
for ii in range(0,len(a)):
print a[ii]
print len(a)
我认为这不是一种非常有效的方法(因为我是 Python 新手)。它适用于较小的 M 和 N (<10) 值,但超过此值就非常慢。我希望将它用于 M ~ 100 和 N ~ 6。我怎样才能使我的代码更高效或者是否有更好的编码方式?
我有一个更好的解决方案,使用 itertools 如下,
from itertools import product
n = 4 #number of elements
s = 3 #sum of elements
r = []
for x in range(n):
r.append(x)
result = [p for p in product(r, repeat=n) if sum(p) == s]
print(len(result))
print(result)
我是说这更好,因为它在我的系统上花费了 0.1 秒,而您使用 numpy 的代码花费了 0.2 秒。
但就 n=100 和 s=6 而言,此代码需要时间来完成所有组合,我认为计算结果需要几天时间。
我的建议:
- 利用
yield
将其重写为生成器,而不是在每次迭代时连接全局变量的循环。
- 保留 运行 总和,而不是计算数字数组表示形式的某个子集的总和。
- 对您的工作数字表示的单个实例进行操作,而不是在每次迭代时将其副本拼接到临时变量。
注意没有暗示特定的顺序。
改编自 Jorg Arndt 书的非常有效的算法 "Matters Computational"
(章节7.2 Co-lexicographic order for compositions into exactly k parts
)
n = 4
k = 3
x = [0] * n
x[0] = k
while True:
print(x)
v = x[-1]
if (k==v ):
break
x[-1] = 0
j = -2
while (0==x[j]):
j -= 1
x[j] -= 1
x[j+1] = 1 + v
[3, 0, 0, 0]
[2, 1, 0, 0]
[2, 0, 1, 0]
[2, 0, 0, 1]
[1, 2, 0, 0]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 2, 0]
[1, 0, 1, 1]
[1, 0, 0, 2]
[0, 3, 0, 0]
[0, 2, 1, 0]
[0, 2, 0, 1]
[0, 1, 2, 0]
[0, 1, 1, 1]
[0, 1, 0, 2]
[0, 0, 3, 0]
[0, 0, 2, 1]
[0, 0, 1, 2]
[0, 0, 0, 3]
n=100 和 k = 2,3,4,5 (2.8 ghz Cel-1840)Python(也许 numpy 数组更快)的成分数和秒数
2 5050 0.040000200271606445
3 171700 0.9900014400482178
4 4421275 20.02204465866089
5 91962520 372.03577995300293
I expect time 2 hours for 100/6 generation
与 numpy 数组相同 (x = np.zeros((n,), dtype=int)
) 给出 更差 结果 - 但也许是因为我不知道如何正确使用它们
2 5050 0.07999992370605469
3 171700 2.390003204345703
4 4421275 54.74532389640808
本机代码(这是 Delphi,C/C++ 编译器可能会优化得更好)在 21 秒内生成 100/6
3 171700 0.012
4 4421275 0.125
5 91962520 1.544
6 1609344100 20.748
所有测量都完成后才能入睡:)
MSVS VC++:18 秒! (O2 优化)
5 91962520 1.466
6 1609344100 18.283
所以每秒有 1 亿个变体。
大量时间浪费在检查空单元格上(因为填充率很小)。 Arndt 描述的速度是在更高的 k/n 比率下达到的,大约每秒 300-5 亿个变体:
n=25, k=15 25140840660 60.981 400 millions per second
我也找到了使用 itertools 的解决方案(来源:https://bugs.python.org/msg144273)。代码如下:
import itertools
import operator
def combinations_with_replacement(iterable, r):
# combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
pool = tuple(iterable)
n = len(pool)
if not n and r:
return
indices = [0] * r
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != n - 1:
break
else:
return
indices[i:] = [indices[i] + 1] * (r - i)
yield tuple(pool[i] for i in indices)
int_part = lambda n, k: (tuple(map(c.count, range(k))) for c in combinations_with_replacement(range(k), n))
for item in int_part(3,4): print(item)
我想生成一个字典序列的数字,这样每个数字的数字总和就是一个给定的常量。有点类似于'subset sum problem'。例如,如果我希望生成 sum = 3 的 4 位数字,那么我有一个类似的系列:
[3 0 0 0]
[2 1 0 0]
[2 0 1 0]
[2 0 0 1]
[1 2 0 0] ...等等。
我使用以下代码在 Python 中成功完成:
import numpy as np
M = 4 # No. of digits
N = 3 # Target sum
a = np.zeros((1,M), int)
b = np.zeros((1,M), int)
a[0][0] = N
jj = 0
while a[jj][M-1] != N:
ii = M-2
while a[jj][ii] == 0:
ii = ii-1
kk = ii
if kk > 0:
b[0][0:kk-1] = a[jj][0:kk-1]
b[0][kk] = a[jj][kk]-1
b[0][kk+1] = N - sum(b[0][0:kk+1])
b[0][kk+2:] = 0
a = np.concatenate((a,b), axis=0)
jj += 1
for ii in range(0,len(a)):
print a[ii]
print len(a)
我认为这不是一种非常有效的方法(因为我是 Python 新手)。它适用于较小的 M 和 N (<10) 值,但超过此值就非常慢。我希望将它用于 M ~ 100 和 N ~ 6。我怎样才能使我的代码更高效或者是否有更好的编码方式?
我有一个更好的解决方案,使用 itertools 如下,
from itertools import product
n = 4 #number of elements
s = 3 #sum of elements
r = []
for x in range(n):
r.append(x)
result = [p for p in product(r, repeat=n) if sum(p) == s]
print(len(result))
print(result)
我是说这更好,因为它在我的系统上花费了 0.1 秒,而您使用 numpy 的代码花费了 0.2 秒。
但就 n=100 和 s=6 而言,此代码需要时间来完成所有组合,我认为计算结果需要几天时间。
我的建议:
- 利用
yield
将其重写为生成器,而不是在每次迭代时连接全局变量的循环。 - 保留 运行 总和,而不是计算数字数组表示形式的某个子集的总和。
- 对您的工作数字表示的单个实例进行操作,而不是在每次迭代时将其副本拼接到临时变量。
注意没有暗示特定的顺序。
改编自 Jorg Arndt 书的非常有效的算法 "Matters Computational"
(章节7.2 Co-lexicographic order for compositions into exactly k parts
)
n = 4
k = 3
x = [0] * n
x[0] = k
while True:
print(x)
v = x[-1]
if (k==v ):
break
x[-1] = 0
j = -2
while (0==x[j]):
j -= 1
x[j] -= 1
x[j+1] = 1 + v
[3, 0, 0, 0]
[2, 1, 0, 0]
[2, 0, 1, 0]
[2, 0, 0, 1]
[1, 2, 0, 0]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 2, 0]
[1, 0, 1, 1]
[1, 0, 0, 2]
[0, 3, 0, 0]
[0, 2, 1, 0]
[0, 2, 0, 1]
[0, 1, 2, 0]
[0, 1, 1, 1]
[0, 1, 0, 2]
[0, 0, 3, 0]
[0, 0, 2, 1]
[0, 0, 1, 2]
[0, 0, 0, 3]
n=100 和 k = 2,3,4,5 (2.8 ghz Cel-1840)Python(也许 numpy 数组更快)的成分数和秒数
2 5050 0.040000200271606445
3 171700 0.9900014400482178
4 4421275 20.02204465866089
5 91962520 372.03577995300293
I expect time 2 hours for 100/6 generation
与 numpy 数组相同 (x = np.zeros((n,), dtype=int)
) 给出 更差 结果 - 但也许是因为我不知道如何正确使用它们
2 5050 0.07999992370605469
3 171700 2.390003204345703
4 4421275 54.74532389640808
本机代码(这是 Delphi,C/C++ 编译器可能会优化得更好)在 21 秒内生成 100/6
3 171700 0.012
4 4421275 0.125
5 91962520 1.544
6 1609344100 20.748
所有测量都完成后才能入睡:)
MSVS VC++:18 秒! (O2 优化)
5 91962520 1.466
6 1609344100 18.283
所以每秒有 1 亿个变体。 大量时间浪费在检查空单元格上(因为填充率很小)。 Arndt 描述的速度是在更高的 k/n 比率下达到的,大约每秒 300-5 亿个变体:
n=25, k=15 25140840660 60.981 400 millions per second
我也找到了使用 itertools 的解决方案(来源:https://bugs.python.org/msg144273)。代码如下:
import itertools
import operator
def combinations_with_replacement(iterable, r):
# combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
pool = tuple(iterable)
n = len(pool)
if not n and r:
return
indices = [0] * r
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != n - 1:
break
else:
return
indices[i:] = [indices[i] + 1] * (r - i)
yield tuple(pool[i] for i in indices)
int_part = lambda n, k: (tuple(map(c.count, range(k))) for c in combinations_with_replacement(range(k), n))
for item in int_part(3,4): print(item)