How could I measure the elapsed time that my algorithm takes throughout its running?

Question

I'm working on my below algorithm (A star algorithm) and I want to calculate the whole time that it takes. I have read that I want to import this library for time import timeit, but I'm stuck with how could I apply it. Could I get a recommendation or fixing to my problem, please?.

This is below my code in 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()

Did you take a look at the module documentation? It includes several examples. — MisterMiyagi, Aug 08 '19 at 06:02
simplest way is to `import time` `s = time.time(); your_code(); e = time.time(); total_time = e-s` — WiseDev, Aug 08 '19 at 06:07
@BlueRineS Dear Do you mean I put my code from import random until search() between import time s = time.time() and e = time.time(); total_time = e-s? — , Aug 08 '19 at 06:15
@Chen no, I mean that that you put the code _you're timing_ between `s` and `e`, because that's what you're interested in.. — WiseDev, Aug 08 '19 at 06:17
@Chen You tell me, it's your program.. What time do you want to know? Your title says "elapsed time the algorithm takes", so I would guess your "algorithm" is only the `search()` function right? You are not interested in knowing the time it takes to declare the classes, imports and variables above, right? — WiseDev, Aug 08 '19 at 06:23
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/197658/discussion-between-chen-and-bluerine-s). — , Aug 08 '19 at 06:25

score 2 · Accepted Answer · edited Aug 08 '19 at 06:10

2

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

edited Aug 08 '19 at 06:10

Xiidref

1,456
8
20

answered Aug 08 '19 at 06:07

BeRational

46
5

Dear Do you mean I put my code from import random until search() between t1 and t2? – Aug 08 '19 at 06:12
@Chen yes you can simply put all your code if you want to measure the total time of execution of your program, if you just want time time of processing put your import before the t1 line – Xiidref Aug 08 '19 at 06:15
@Xiidref Yes, I want my all code – Aug 08 '19 at 06:16
@Chen You put everything you want to measure between `t1 =... ` and `t2=... `. If you want to include the time the imports take, you could also put your imports there. But i think thats not desirable since you want to measure only the time your algorithm takes to calculate what it's calculating. – BeRational Aug 08 '19 at 06:18
@Madafakar I put it before the function def t1 search() and before the calling of the function t2 search(), it gave me zero. – Aug 08 '19 at 06:24
@Madafakar it will give the time in seconds, rights? – Aug 08 '19 at 09:00

score 1 · Answer 2 · answered Aug 08 '19 at 06:11

1

The simplest way to use the timeit module is as follows:

def search(...):
    . . .

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

answered Aug 08 '19 at 06:11

Abulurd

1,018
4
15
31

Do you mean I put this line timeit.Timer(function).timeit(number=NUMBER) inside the def search() and it will calculate the time? – Aug 08 '19 at 06:14

score 0 · Answer 3 · answered Aug 08 '19 at 06:47

Alternatively, you could use the time terminal command.
This allows you to measure the execution time of any command you type.

You would simply do
time [your command here]

If your python file was called program.py, then you would just type
time python program.py

How could I measure the elapsed time that my algorithm takes throughout its running?

3 Answers3