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)))

また、Windows 7 で 64 ビット CPython 3.3.1 のパフォーマンスを取得していますが、C++ よりも約 574 倍遅いです。N = 100000 の場合の時間は次のとおりです。

e28: 23ms; e28a: 48.4ms; e28b: 49.7ms; e28c: 40.2ms; C++ バージョン: 0.07ms

基礎となるアルゴリズムを変更せずに Python コードを最適化することで、簡単に達成できることはありますか?

4

3 に答える 3

4

F# バージョンは、手続き型の変更可能なアプローチ ( python などe28a) に切り替えることで、最大 10 倍高速化できます。「ペイロード操作」(この場合は + のみ) が非常に些細な場合、コンビネータを使用すると、比較的大きなオーバーヘッドが追加されます。補足として、Seq.sumチェックされた算術演算を使用するため、オーバーヘッドも少し追加されます。

F# の優れた点の 1 つは、パフォーマンス クリティカルなホット パスが必要な場合に、手続き型/可変スタイルにフォールバックできることです。

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
于 2013-07-05T20:33:44.880 に答える
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

私は得た：

> 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 ではかなり高価になる可能性があります。

于 2013-07-05T18:26:40.480 に答える
1

これは、私のマシンではほぼ 2 倍の速さです。メモ化と基本的な算術演繹を使用します。

グローバル変数を定義する必要があります。 

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
于 2013-07-05T13:52:02.337 に答える