logo标签列表

有没有办法加速这个函数？

python-3.xf#benchmarkinglist-comprehension
4

我正在比较这个F#函数的性能：

let e28 N =                               
  seq {for i in 2L..2L..N do for j in 1..4 -> i} |> Seq.scan (+) 1L |> Seq.sum

使用Python 3.3相应的等价代码：

def e28a(N = 100000):
    diagNumber = 1                             
    sum        = diagNumber                
    for width in range(2, N+1, 2):
        for j in range(4):          
            diagNumber += width             
            sum        += diagNumber            
    return sum

import itertools as it
def e28b(N = 100000):
    return sum(it.accumulate(it.chain([1], (i for i in range(2, N+1, 2) for j in range(4)))))    

import numpy as np
def e28c(N = 100000):
    return np.sum(np.cumsum(np.fromiter(chain([1], (i for i in range(2, N+1, 2) for j in range(4))), np.int64)))

我正在使用64位的CPython 3.3.1，在Windows 7上的性能大约比C++慢574倍。这是N = 100000时的时间：

e28: 23毫秒；e28a: 48.4毫秒；e28b: 49.7毫秒；e28c: 40.2毫秒；C++版本：0.07毫秒

有没有一些简单易行的方法来优化Python代码而不改变底层算法？

我没有时间查看你的所有代码，但似乎使用生成器可能会有所帮助。 - K DawG
@KDawG e28b和e28c正在使用生成器。 - Paul Jurczak
1
你是如何让N=100000时e28运行的？我会遇到算术溢出，除非我将所有内容注释为int64。 - Kit
@Kit 很好的发现，我又犯了一个剪切粘贴错误。现在已经更正了，F#性能不再荒谬地快了。 - Paul Jurczak
3个回答
4
F#的版本可以通过切换到过程式、可变的方法（比如你的python e28a）来加速约10倍。当“负载操作”（在这种情况下，只是+）非常微不足道时，组合器的使用最终会增加相对显着的开销。另外值得一提的是，Seq.sum使用了检查算术，这也增加了一点开销。

F#的一个好处是，如果需要性能关键的热路径，可以退回到过程式/可变风格。
let e28_original N =
  seq {
    for i in 2UL..2UL..N do 
        for j in 1..4 do
            yield i
  }
  |> Seq.scan (+) 1UL
  |> Seq.sum

let e28_mutable N = 
  let mutable sum = 1UL
  let mutable total = sum                            
  for i in 2UL..2UL..N do 
      for j in 1..4 do
         sum <- sum + i
         total <- total + sum
  total

let time f =
    f () |> ignore // allow for warmup / JIT
    let sw = System.Diagnostics.Stopwatch.StartNew()
    let result = f ()
    sw.Stop()
    printfn "Result: %A Elapsed: %A" result sw.Elapsed

time (fun _ -> e28_original 100000UL)
time (fun _ -> e28_mutable 100000UL)

结果

Result: 666691667100001UL Elapsed: 00:00:00.0429414
Result: 666691667100001UL Elapsed: 00:00:00.0034971
1
你可以通过像这样展开内部循环来将其提高近10％：for i in 2UL..2UL..N do sum <- sum + i total <- total + sum sum <- sum + i total <- total + sum sum <- sum + i total <- total + sum sum <- sum + i total <- total + sum - N_A
我一直在寻找Python代码加速的方法，但由于我提供了一个命令式Python示例（e28a），所以有一个命令式F#示例也是公平的。它快了一个数量级 - 很好知道。谢谢。 - Paul Jurczak
time 函数赞！我的标准时钟分辨率已经用完了，这个函数对我帮助很大。你的 e28_mutable 速度提升了23毫秒 -> 1.58毫秒。 - Paul Jurczak
3

使用您的 F# 版本，我得到了：


> e28(100000L);;
Real: 00:00:00.061, CPU: 00:00:00.062, GC gen0: 2, gen1: 0, gen2: 0
val it : int64 = 666691667100001L

使用:

let e28d N =
    seq {2L..2L..N}
    |> Seq.collect(fun x->seq{yield x;yield x; yield x; yield x})
    |> Seq.scan (+) 1L
    |> Seq.sum

I got:

> e28d(100000L);;
Real: 00:00:00.040, CPU: 00:00:00.031, GC gen0: 2, gen1: 0, gen2: 0
val it : int64 = 666691667100001L

由于F#是编译语言，而Python是解释语言，所以Python的性能可能不如F#。但是，上述改进方法也可以适用于Python：

>>> def e28a(N = 100000):
    diagNumber = 1;                            
    sum        = diagNumber;                   
    for width in range(2, N+1, 2):
        for j in range(4):          
            diagNumber += width;                
            sum        += diagNumber;           
    return sum;

>>> if __name__ == '__main__':
    import timeit
    print(timeit.timeit("e28a()", setup="from __main__ import e28a", number=10))


0.5249497228663813
>>> def e28a(N = 100000):
    diagNumber = 1;
    sum        = diagNumber;
    for width in range(2, N+1, 2):
        diagNumber += width;
        sum        += diagNumber;
        diagNumber += width;
        sum        += diagNumber;
        diagNumber += width;
        sum        += diagNumber;
        diagNumber += width;
        sum        += diagNumber;
    return sum;

>>> if __name__ == '__main__':
    import timeit
    print(timeit.timeit("e28a()", setup="from __main__ import e28a", number=10))


0.2585966329330063
>>>

这种改进的一部分来自于较少的函数调用，即：

>>> def e28a(N = 100000):
    diagNumber = 1;                            
    sum        = diagNumber;
    temp_range = range(4)             #Change here
    for width in range(2, N+1, 2):
        for j in temp_range:          #Change here
            diagNumber += width;                
            sum        += diagNumber;           
    return sum;

>>> if __name__ == '__main__':
    import timeit
    print(timeit.timeit("e28a()", setup="from __main__ import e28a", number=10))


0.40251470339956086
>>>

我认为另一部分来自于去掉循环。这两个操作在Python中都可能非常昂贵。

我猜这个性能提升来自于不需要迭代生成四个相同值的实例。 - N_A
很好，它可以提高性能和可读性！实际上我想要的是改善Python代码的性能，F#只是用来说明所使用的算法。 - Paul Jurczak
1
请注意我的Python代码修改。基本上只需将我的F#改进应用到Python代码中，就可以实现50％的性能提升！ - N_A
内部循环展开非常有帮助：48.4毫秒-> 22.3毫秒。代码可能更易读，只是有点啰嗦。谢谢。 - Paul Jurczak
1
这在我的机器上快了近一倍。它使用了记忆化和基本算术推导。
你需要定义一个全局变量。
summi=2

def e28d(N = 100000):
    def memo(width):
        global summi
        summi+=width*4+4
        return summi-width*2+2
    x= sum((memo(width*4)) for width in range (2, N+1, 2))+1
    return x

结果：
e28a:

0.0591201782227 秒

e28d:

0.0349650382996 秒

希望它至少是有益的。注意：您需要根据数字是奇数还是偶数来调节它。

更新： 这是一个在Python中运行速度约快100倍（N=100000时约为0.5毫秒）的函数，通过完全避免循环来实现：

import math
def e28e(X = 100000):
    keyint, keybool=int(X/6), X%6
    if keybool/2==0: keyvar=(16*keyint+sum(range(keyint))*12)
    elif keybool/2==1: keyvar=(44*keyint+sum(range(keyint))*36+7) 
    else: keyvar=(28*(keyint+1)+sum(range(keyint+1))*60-2)
    X-=keybool%2
    diag= math.pow(X,2)+2*X+1
    newvar=keyint+int(X/2)+1
    summ= int(diag*newvar+keyvar)
    return summ
缩进最后两行后，我得到了“NameError: global name 'summi' is not defined”的错误。我添加了初始化“summi = 0”，但返回的结果略有偏差：666691667050001而不是666691667100001 :-( 不过速度更快了。 - Paul Jurczak
抱歉，我最初发布的解决方案给出了那个答案。然而，当前帖子（大约一个小时前编辑）给出了正确的答案。请注意“N/2.”这一部分。如果它是奇数，那也是必须向下取整的部分。 - JonLeslieHarding
实际上，要明确一点，关于N的奇偶性，你只需要确保返回值是整数，就可以了。 - JonLeslieHarding
当我在CPython 3.3.1中运行它时，它仍然产生错误的结果：666691667050001.0。 - Paul Jurczak
感谢你的努力，但这是实现不同算法的过程。我在我的问题中使用了“不改变基础算法”的方法。 - Paul Jurczak
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接