Python実装プログラム実行時間メトリック分析

自分のコラムをお勧めします:Pythonのケースを共有して、学んだことを

に使います
一:アルゴリズム時間複雑度分析関数の設計

プログラムの実行時間の長さはアルゴリズムの設計と解いた問題の規模と関係がある.

入力サイズ(すなわち問題規模)が大きくなると、プログラムの実行時間の増加割合、すなわちアルゴリズムの時間複雑度となる.

設計構想は以下の通りである.

は関数buildData(n)を定義し、n規模のテスト入力データを構築して返します.たとえば、ランダムなn個の数のリストを並べ替えます.

def buildData(n):
    """       n     ,    ，  n     """
    data = [random.randrange(n) for i in range(n)]
    return data

は、関数timing(f,data)を定義し、f(data)を呼び出す実行時間を返す.

def timing(f, data):
    """      f(data)       """
    start = time.time() #      
    f(data)  #  f(data)
    end = time.time()  #      
    return end - start #      

は関数timingAnalysis(f,m 1,m 2,runs,buildData)を定義し、関数fが異なる入力規模:10 m 1,10 m 1+1,...,10 m 2でruns回を実行する平均時間を測定し出力する.関数はbuildData(n)規模nのデータdataを呼び出し、timing(f,data)を呼び出して関数の実行時間を測定する.

def timingAnalysis(f,m1, m2, runs, buildData) :
    """    f       : 10**m1,.... ,10**m2  runs    """
    for n in [10**i for i in range(m1, m2+1)]:  #10**m1,...，10**m2
          data = buildData (n)
          total = 0.0  #      
          for i in range(runs) : #    runs 
              total += timing(f, data) #  f       
          strResult = '    {:10}   {:15}  {}       : {}  '
          print (strResult.format(n, f.__name__, runs, total/runs))

テストコードにおいて、様々なソートアルゴリズムを導入し(本明細書では後述しないが、興味のある者は完全なコードをダウンロードして表示することができる)、各ソートアルゴリズムを分析する時間的複雑さを呼び出す.

二:アルゴリズム時間複雑度分析関数の実現と応用
time_analysis.py

import time
import random

def timing(f, data):
    """      f(data)       """
    start = time.time() #      
    f(data)  #  f(data)
    end = time.time()  #      
    return end - start #      

def timingAnalysis(f,m1, m2, runs, buildData) :
    """    f       : 10**m1,.... ,10**m2  runs    """
    for n in [10**i for i in range(m1, m2+1)]:  #10**m1,...，10**m2
          data = buildData (n)
          total = 0.0  #      
          for i in range(runs) : #    runs 
              total += timing(f, data) #  f       
          strResult = '    {:10}   {:15}  {}       : {}  '
          print (strResult.format(n, f.__name__, runs, total/runs))

def buildData(n):
    """       n     ,    ，  n     """
    data = [random.randrange(n) for i in range(n)]
    return data


#    

if __name__ ==  "__main__" :
    from bubbleSort import bubbleSort
    from selectionSort import selectionSort
    from insertSort import insertSort
    from mergeSort import mergeSort
    from quickSort import quickSort

    def quickSort1 (a) :
        quickSort(a, 0, len(a) - 1)

    #      ，       
    timingAnalysis (bubbleSort, 2, 4, 1, buildData)
    print()

    #      ，       
    timingAnalysis (selectionSort, 2, 4, 1, buildData)
    print()

    #      ，       
    timingAnalysis (insertSort, 2, 4, 1, buildData)
    print()

    #      ，       
    timingAnalysis (mergeSort, 1, 4, 1, buildData)
    print()

    #      ，       
    timingAnalysis (quickSort1, 1, 4, 1, buildData)
    print()

    #      sort，       
    timingAnalysis(sorted, 1, 4, 1, buildData)

実行:

           100   bubbleSort       1       : 0.000997781753540039  
          1000   bubbleSort       1       : 0.10474658012390137  
         10000   bubbleSort       1       : 8.514265298843384  

           100   selectionSort    1       : 0.0  
          1000   selectionSort    1       : 0.044878244400024414  
         10000   selectionSort    1       : 4.592764377593994  

           100   insertSort       1       : 0.0009894371032714844  
          1000   insertSort       1       : 0.0917809009552002  
         10000   insertSort       1       : 7.810081720352173  

            10   mergeSort        1       : 0.0  
           100   mergeSort        1       : 0.000997304916381836  
          1000   mergeSort        1       : 0.0029914379119873047  
         10000   mergeSort        1       : 0.03091740608215332  

            10   quickSort1       1       : 0.0  
           100   quickSort1       1       : 0.0009975433349609375  
          1000   quickSort1       1       : 0.001994609832763672  
         10000   quickSort1       1       : 0.02396249771118164  

            10   sorted           1       : 0.0  
           100   sorted           1       : 0.0  
          1000   sorted           1       : 0.0  
         10000   sorted           1       : 0.0019676685333251953