如何快速迭代(唯一的)组合?

2024-05-13 01:10:37 发布

您现在位置:Python中文网/ 问答频道 /正文

我的脚本执行以下操作:我有一个带有拼字架及其“值”的文本文件:

BYZZZZĄ -8.038175
BYZZZĄŹ -14.072675
BYZZZĄŻ -1.238175
BYZZĄŹŻ -3.588175
BZZZZZĄ -13.938175
BZZZZĄŹ -9.738175
BZZZZĄŻ -10.538175
BZZZĄŹŻ -19.072675
CCCDDĄĆ -16.088175
CCCDEĄĆ -4.288175
CCCDĄĆĘ -5.588175
CCCDFĄĆ -16.788175
CCCDGĄĆ -10.338175

现在我要生成部分机架及其值的列表。部分机架的值是所有可用的完整机架的加权和。所以对于一个6个字母的机架CCCDDA,它应该是(CCCDDAA*8+CCCDDAB*2+CCCDDAD*1+CCCDDAE*7)/N,其中N是所有机架的数量。乘法器等于袋子里剩下的字母数,例如总共有9个A,但在CCCDDA里已经有一个了,所以我们只乘8。你知道吗

字母分布如下(第四栏):

A   a   1   9   1
Ą   ą   5   1   1
B   b   3   2   0
C   c   2   3   0
Ć   ć   6   1   0
D   d   2   3   0
E   e   1   7   1
Ę   ę   5   1   1
F   f   5   1   0
G   g   3   2   0
H   h   3   2   0
I   i   1   8   1
J   j   3   2   0
K   k   2   3   0
L   l   2   3   0
Ł   ł   3   2   0
M   m   2   3   0
N   n   1   5   0
Ń   ń   7   1   0
O   o   1   6   1
Ó   ó   5   1   1
P   p   2   3   0
R   r   1   4   0
S   s   1   4   0
Ś   ś   5   1   0
T   t   2   3   0
U   u   3   2   1
W   w   1   4   0
Y   y   2   4   1
Z   z   1   5   0
Ź   ź   9   1   0
Ż   ż   5   1   0
blank   0   2

可能有11M机架,因此计算所有部分值非常耗时。这是我目前的方法(也可以在github上找到):

#-*- coding: utf-8 -*-

import io
import itertools
import time

def loadAlphabet(filename):
    fil = io.open(filename, encoding="utf-8")
    lines = fil.readlines()
    letters = {}
    for line in lines:
        line = line.split()
        if line[0] == 'blank':
            letters[u'?'] = int(line[2])
        else:
            letters[u'%s' % line[0]] = int(line[3])
    fil.close()
    return letters

def adjustBag(rack, bag):
    newBag = bag.copy()
    for letter in rack:
        newBag[letter] -= 1
    return newBag

def partialValue(rackLen):

    bag = loadAlphabet("../data/alphabets/polish.quackle_alphabet")
    racks = io.open("racks%d.txt" % rackLen, encoding='utf-8').read().splitlines()
    leaveList = io.open("leavesSorted.txt", encoding='utf-8').read().splitlines()

    leaves = {}

    # create a dictionary of leave:value
    for line in leaveList:
        (lv, val) = line.split()
        leaves[lv] = float(val)

    outFile = io.open("rack%doutput.txt" % rackLen, 'w', encoding='utf-8')

    for r in racks:
        smallerBag = adjustBag(r, bag)
        bagList = []

        for letter in smallerBag:
            bagList += smallerBag[letter]*letter

        combs= itertools.combinations(bagList, 7-rackLen)
        combSet = set(combs)

        sumVals = 0.0
        i = 0.0
        avgVal = 0.0

        for elem in combSet:
            multiplier = 1.0
            for letter in elem:
                multiplier *= smallerBag[letter]

            fullrack = u''.join(sorted(r + u''.join(elem)))
            sumVals += leaves[fullrack]*multiplier
            i+= multiplier

        avgVal = sumVals / i
        outFile.write(u'%s %f\n' % (r, avgVal))

partialValue(5)

我已经加快了速度,从迭代整个itertools.combinations生成器(old code)到从生成器创建一个集,然后计算乘数。我还可以通过创建一个只包含唯一组合的生成器来改进它(这样我就可以跳过set()生成),但是我没有找到一个内置函数。你知道吗

如何优化代码的速度?(也欢迎其他提示)


Tags: iniofor字母lineopenutfencoding