使用Python中定义的元素值最快生成置换 [英] Fastest possible generation of permutation with defined element values in Python
问题描述
尝试生成排列，可以与生成器或生成的列表列表一起使用(但也许我需要很多内存?)在Internet和SO上进行了查找，但找不到为每个列表定义值的版本元素.
Trying to generate permutations, could be used with generator or produced List of Lists (but maybe I need a lot of memory?) Looked on the Internet and SO, but couldn't find a version where I define the values for each element.
顺便说一句，它将有多少排列?
BTW How many permutations it will be?
8个元素，每个值的范围为1-15
8 elements with each value from 1-15
这是我的代码，但是也许有更好，更快的方法来生成它:
Here is my code, but maybe there is a better, faster way to generate it:
任何提示都值得赞赏！
import time
from tqdm import tqdm
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = range(n)
cycles = range(n, n-r, -1)
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
plist = []
for item in tqdm(permutations('123456789ABCDEF',8)):
plist.append(item)
len(plist)
推荐答案
You just copied the code from the itertools.permutations() documentation. That explicitly states that it is roughly equivalent, because it is only there to help you understand what itertools.permutations() does. The code is not intended to be used in production settings.
使用itertools.permutations()本身. itertools模块已被设计用于最大效率.该模块是用C编码的，并且总是会击败纯Python实现.
Use itertools.permutations() itself. The itertools module is designed for maximum efficiency already. The module is coded in C, and will always beat a pure Python implementation, hands down.
您还浪费了将值附加到列表的迭代；每个.append()表达式都需要一个属性查找和一个方法调用.您可以通过调用list()在单个表达式中构建plist:
You are also wasting iterations on appending values to a list; each .append() expression requires an attribute lookup and a method call. You can build plist in a single expression by calling list():
plist = list(permutations('123456789ABCDEF', 8))
但是，您确实不希望执行该调用，因为将所有可能的排列作为单独的对象生成会花费很多时间，为此分配内存需要花费时间和会降低计算机的速度.
However, you really don't want to execute that call, because that'll take a lot of time to produce all possible permutations as separate objects, and allocating the memory for that takes time and will slow down your machine.
k -的排列数n 用k计算！ /(n-k)！)，其中n = 15且k = 8，就是15！ /(15-8)!，因此超过25亿的结果，即259_459_200 .在64位操作系统上，大约需要30GB的内存(列表对象为2GB，元组为27G，15个1位数字字符串共享时仅为字节).
The number of k-permutations of n is calculated with k! / (n - k)!), with n=15 and k=8, that's 15! / (15 - 8)!, so just over a quarter billion results, 259_459_200. On a 64-bit OS that'll require about ~30GB of memory (2GB for the list object, 27G for the tuples, mere bytes for the 15 1-digit strings as they are shared).
如果您真的想处理这些排列，我将遍历生成器并直接使用每个结果.您仍然必须迭代25亿次，因此仍然需要花费很多时间，但是至少您不必立即尝试将其全部保存在内存中.
If you really want to process those permutations, I'd just loop over the generator and use each result directly. You'll still have to iterate a quarter-billion times, so it'll still take a lot of time, but at least you don't then try to hold it all in memory at once.
或者，总是寻找其他方法来解决您的问题.生成所有可能的排列将产生很多可能性.您上一个问题得到的答案指出，对于比特定问题而言，搜索200kb的数据来寻找可能的候选对象要比对每个8个8排列的搜索进行4万次搜索更为有效.总值达2.59亿排列的可能性更大，从另一个方向处理您的问题可能会使您的问题空间易于管理.
Alternatively, always look for other ways to solve your problem. Generating all possible permutations will produce a very large number of possibilities. Your previous question received an answer that pointed out that for than specific problem, searching through 200kb of data for likely candidates was more efficient than to do 40k searches for every possible 8-permutation of 8. With 259 million permutations there is an even larger chance that processing your problem from another direction might keep your problem space manageable.
这篇关于使用Python中定义的元素值最快生成置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
