怎样衡量算法在运行过程中所用的时间？

Question

我正在研究下面的算法（A star 算法），我想计算它需要的总时间。我已经了解到需要导入 import timeit 库来计时, 但我不知道如何应用它。请问是否能给我一些建议或者解决方法呢？

这是我在 Python 中的代码：

import random
import math
grid = [[random.randint(0,1) for i in range(100)]for j in range(100)]        
# clear starting and end point of potential obstacles
grid[2][2] = 0
grid[95][95] = 0
init = [5,5]                           
goal = [len(grid)-10,len(grid[0])-12]
heuristic = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
for i in range(len(grid)):    
    for j in range(len(grid[0])):            
        heuristic[i][j] = abs(i - goal[0]) + abs(j - goal[1])
delta = [[-1 , 0],   #up 
         [ 0 ,-1],   #left
         [ 1 , 0],   #down
         [ 0 , 1]]   #right
delta_name = ['^','<','V','>']  #The name of above actions
cost = 1   #Each step costs you one
drone_height = 60
def search():
    #open list elements are of the type [g,x,y]
    closed = [[0 for row in range(len(grid[0]))] for col in range(len(grid))]
    action = [[-1 for row in range(len(grid[0]))] for col in range(len(grid))]
    #We initialize the starting location as checked
    closed[init[0]][init[1]] = 1
    expand=[[-1 for row in range(len(grid[0]))] for col in range(len(grid))]
    # we assigned the cordinates and g value
    x = init[0]
    y = init[1]
    g = 0
    h = heuristic[x][y]
    f = g + h
    #our open list will contain our initial value
    open = [[f, g, h, x, y]]

    found  = False   #flag that is set when search complete
    resign = False   #Flag set if we can't find expand
    count = 0

    #print('initial open list:')
    #for i in range(len(open)):
            #print('  ', open[i])
    #print('----')

    while found is False and resign is False:
        #Check if we still have elements in the open list
        if len(open) == 0:    #If our open list is empty, there is nothing to expand.
            resign = True
            print('Fail')
            print('############# Search terminated without success')
            print()
        else: 
            #if there is still elements on our list
            #remove node from list
            open.sort()             
            open.reverse()          #reverse the list
            next = open.pop()       
            #print('list item')
            #print('next')

            x = next[3]
            y = next[4]
            g = next[1]
            expand[x][y] = count
            count+=1
            #Check if we are done
            if x == goal[0] and y == goal[1]:
                found = True
                print(next) #The three elements above this "if".
                print('############## Search is success')
                print()
            else:
                #expand winning element and add to new open list
                for i in range(len(delta)):      
                    x2 = x + delta[i][0]
                    y2 = y + delta[i][1]
                    #if x2 and y2 falls into the grid
                    if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 <= len(grid[0])-1:
                        #if x2 and y2 not checked yet and there is not obstacles
                        if closed[x2][y2] == 0 and grid[x2][y2] == 0 :
                            g2 = g + cost             #we increment the cose
                            h2 = heuristic[x2][y2]
                            f2 = g2 + h2
                            open.append([f2,g2,h2,x2,y2])   
                            #print('append list item')
                            #print([g2,x2,y2])
                            #Then we check them to never expand again
                            closed[x2][y2] = 1
                            action[x2][y2] = i
    for i in range(len(expand)):
        print(expand[i])
    print()
    policy=[[' ' for row in range(len(grid[0]))] for col in range(len(grid))]
    x=goal[0]
    y=goal[1]
    policy[x][y]='*'
    while x !=init[0] or y !=init[1]:
        x2=x-delta[action[x][y]][0]
        y2=y-delta[action[x][y]][1]
        policy[x2][y2]= delta_name[action[x][y]]
        x=x2
        y=y2
    for i in range(len(policy)):
        print(policy[i])

search()

- user11791503

---

你看过模块文档了吗？它包含了几个例子。 - MisterMiyagi

@MisterMiyagi 是的先生，但那些只是简单的示例。 - user11791503

最简单的方法是 import time，然后执行 s = time.time(); your_code(); e = time.time(); total_time = e-s。 - WiseDev

@Chen 你告诉我，这是你的程序。你想知道什么时间？你的标题说“算法所需的经过时间”，那么我猜测你的“算法”只是search()函数，对吧？你并不想知道声明类、导入和上面的变量所需的时间，对吗？ - WiseDev

让我们在聊天中继续这个讨论。点击此处进入聊天室。 - user11791503

Answer 1

Just import time and do a basic calculation like:

...
import time

t1 = time.time()

#your code

t2 = time.time()
runtime = t2-t1 #Here time is in second

- BeRational

---

亲爱的，您是指我将从“import random”到“search()”之间的代码放在t1和t2之间吗？ - user11791503

@Chen 是的，如果您想测量程序的总执行时间，您可以简单地将所有代码放在一起，如果您只是想要处理时间，请在 t1 行之前放置您的 import。 - Xiidref

@Xiidref 是的，我想要我的所有代码。 - user11791503

@Chen，你需要把所有你想要测量的内容放在“t1=…”和“t2=…”之间。如果你想要包括导入所需的时间，也可以把导入放在那里。但我认为这并不理想，因为你只想测量算法计算所花费的时间。 - BeRational

@Madafakar 我把它放在函数 def t1 search() 之前和调用函数 t2 search() 之前，结果是零。 - user11791503

@Madafakar 它会给出秒数，是吗？ - user11791503

Answer 2

使用timeit模块的最简单方法如下：

def search(...):
    . . .

timeit.Timer(function).timeit(number=NUMBER)

- Abulurd

---

你的意思是我把这行代码 timeit.Timer(function).timeit(number=NUMBER) 放在 def search() 里面，它就会计算时间？ - user11791503

Answer 3

或者，您可以使用time终端命令。
这允许您测量您键入的任何命令的执行时间。

您只需执行以下操作
time [your command here]

如果您的Python文件名为program.py，那么您只需键入
time python program.py

- Tobias W