ASCII上的几何平均值更快

Question

是否可以加速以下代码,但不使用外部模块(NumPy等)？只是简单的Python.两条思路:加速计算

chr(int(round( multiplOrds**(1.0/DLen), 0) ) )

或更快地建立所需的结构.目的是找到ASCII符号的ord()的几何平均值,并将其报告为圆值(符号).len(InDict)是高于1的任何东西.例子的结果应该是

KM<I

代码:

def GA():
    InStr="0204507890"
    InDict={
       0:"ABCDEFGHIJ",
       1:"KLMNOPQRST",
       2:"WXYZ#&/()?"
       }

    OutStr = ""

    DLen = len(InDict)
    for pos in zip(InStr, *InDict.values()):
        if pos[0]=="0":
            multiplOrds = 1
            for mul in (ord(char) for char in pos[1:] if char!="!"): multiplOrds*=mul
            OutStr+= chr(int(round( multiplOrds**(1.0/DLen), 0) ) )

    return OutStr

if __name__ == '__main__':
    import timeit
    print(timeit.timeit("GA()", setup="from __main__ import GA"))

Answer 1

第一个想法:

连接字符串很慢,因为它们是不可变的,因此每次修改都会导致创建一个新的复制实例.这就是为什么你不应该做的事情:

s = ""
for i in range(1000000):
    s += chr(65)

每个循环它将创建一个比前一个大一个字符的新字符串实例,旧实例将保留,直到垃圾收集器启动.同样分配内存很慢.

使用生成器表达式存储部分字符串并将它们最终连接在一起的速度大约是代码的两倍和更短:

s = "".join(chr(65) for i in range(1000000))

Answer 2

我假设你使用的是python3.

这是我提供的最快的代码提供的信息,GA_old是旧功能GA优化功能.我将输入初始化移动到全局范围,因为优化初始化并不重要,我假设您从其他地方获取输入,并且不会一直使用相同的输入.

所以这是代码:

InStr="0204507890"
InDict={
   0:"ABCDEFGHIJ",
   1:"KLMNOPQRST",
   2:"WXYZ#&/()?"
}

def GA():
    OutStr = ""

    p = 1.0 / len(InDict)
    for pos,rest in zip(InStr, zip(*InDict.values())):
        if pos == "0":
            product = 1
            for char in rest:
                if char != '!':
                    product*= ord(char)
            OutStr += chr(int(round(product ** p)))
    return OutStr

def GA_old():

    OutStr = ""

    DLen = len(InDict)
    for pos in zip(InStr, *InDict.values()):
        if pos[0]=="0":
            multiplOrds = 1
            for mul in (ord(char) for char in pos[1:] if char!="!"): multiplOrds*=mul
            OutStr+= chr(int(round( multiplOrds**(1.0/DLen), 0) ) )
    return OutStr

if __name__ == '__main__':
    assert GA_old() == GA()
    import timeit
    print(timeit.timeit("GA()", setup="from __main__ import GA", number=100000))
    print(timeit.timeit("GA_old()", setup="from __main__ import GA_old", number=100000))

它在我的机器上产生以下输出(python 3.4.3):

 ? python3 t.py 
0.6274565359999542
1.1968618339960813

我从以下获得的大部分加速:

• 不要在这里使用列表理解for mul in (ord(char) for char in pos[1:] if char!="!"):.看起来像python创建2级迭代器,这是相当慢的.将这种理解嵌入到单循环中,if提高了可读性IMO.
• (非常令人惊讶地)删除round函数的第二个参数非常显着地加速了函数.我无法解释这一点,它看起来像python中的小性能错误.

但我认为它可以进一步优化,但它需要有关您的真实数据的知识(我猜你不会优化这个在几分之一秒内完成的特殊情况).

一些想法:

• 如果您的字符串很长,请尽量不附加到他们但使用其他答案的建议(bytearray或"".join(...))
• 尝试使用缓存chr(int(round( multiplOrds**(1.0/DLen))))(将已经计算的结果放到全局字典中,如果可以在dict中找到它,则不要重新计算值).
• 而不是计算multiplOrds**(1.0/DLen)你可以尝试ord(c) ** DLen为每个可能的字符预先计算表,并尝试multiplOrds在这个预先计算的表中搜索.

这些想法都不会对您发布的输入数据有效,因为它非常小,但它可能适用于更大的输入.