làm thế nào để đo thời gian chạy của thuật toán trong python

Question

thể Duplicates:
Accurate timing of functions in python
accurately measure time python function takes

Làm thế nào tôi có thể mesure và so sánh thời gian chạy của thuật toán của tôi viết bằng python .Also hướng tôi đến một trang web/diễn đàn thuật toán tốt đẹp như stackoverflow nếu bạn có thể.

Answer 1

Tôi không chắc chắn 100% có nghĩa là gì "chạy lần các thuật toán của tôi viết bằng python", vì vậy tôi nghĩ tôi có thể cố gắng để cung cấp một cái nhìn rộng lớn hơn tại một số các câu trả lời tiềm năng.

• Thuật toán không có thời gian chạy; triển khai có thể được hẹn giờ, nhưng một thuật toán là một cách tiếp cận trừu tượng để làm một cái gì đó. Phần phổ biến nhất và thường là phần có giá trị nhất của việc tối ưu hóa một chương trình là analyzing the algorithm, thường sử dụng phân tích tiệm cận và tính toán độ phức tạp big O theo thời gian, không gian, sử dụng đĩa và v.v.

  Máy tính không thể thực hiện bước này cho bạn. Điều này đòi hỏi phải làm toán để tìm ra cách thức hoạt động của một cái gì đó. Tối ưu hóa mặt này của sự vật là thành phần chính để có hiệu suất có thể mở rộng.

• Bạn có thể thời gian triển khai cụ thể của mình. Cách tốt nhất để làm điều này trong Python là sử dụng timeit. Cách mà dường như hầu hết mọi thứ muốn được sử dụng là tạo một mô-đun có chức năng gói gọn những gì bạn muốn gọi và gọi nó từ dòng lệnh với python -m timeit ....

  Sử dụng thời gian để so sánh nhiều đoạn mã khi thực hiện tối ưu hóa vi mô, nhưng thường không phải là công cụ chính xác bạn muốn so sánh hai thuật toán khác nhau. Nó là phổ biến mà những gì bạn muốn là phân tích tiệm cận, nhưng nó có thể bạn muốn các loại phân tích phức tạp hơn.

• Bạn phải biết thời gian. Hầu hết các đoạn mã không đáng được cải thiện. Bạn cần thực hiện thay đổi khi thực sự đếm, đặc biệt là khi bạn đang thực hiện tối ưu hóa vi mô và không cải thiện độ phức tạp tiệm cận của thuật toán.

  Nếu bạn tăng gấp bốn lần tốc độ của một hàm trong đó mã của bạn dành 1% thời gian, đó không phải là tốc độ thực. Nếu bạn tăng tốc độ 20% cho một chức năng mà chương trình của bạn dành 50% thời gian, bạn sẽ có được lợi ích thực sự.

  Để xác định thời gian dành cho chương trình Python thực, hãy sử dụng stdlib profiling utilities. Điều này sẽ cho bạn biết nơi nào trong một chương trình ví dụ mã của bạn đang dành thời gian của nó.

Answer 2

Mô-đun timeit hữu ích cho việc này và được đưa vào phân phối Python chuẩn.

Ví dụ:

import timeit 
timeit.Timer('for i in xrange(10): oct(i)').timeit() 

Answer 3

Đối với thuật toán nhỏ, bạn có thể sử dụng các mô-đun timeit từ tài liệu python:

def test(): 
    "Stupid test function" 
    L = [] 
    for i in range(100): 
     L.append(i) 

if __name__=='__main__': 
    from timeit import Timer 
    t = Timer("test()", "from __main__ import test") 
    print t.timeit() 

Ít chính xác nhưng vẫn có giá trị bạn có thể sử dụng thời gian mô-đun như thế này:

from time import time 
t0 = time() 
call_mifuntion_vers_1() 
t1 = time() 
call_mifunction_vers_2() 
t2 = time() 

print 'function vers1 takes %f' %(t1-t0) 
print 'function vers2 takes %f' %(t2-t1) 

Answer 4

Ngôn ngữ lập trình không quan trọng; đo độ phức tạp thời gian chạy của thuật toán hoạt động theo cùng một cách bất kể ngôn ngữ. Analysis of Algorithms bởi Stanford trên Google Code University là tài nguyên rất tốt để tự dạy cho mình cách phân tích độ phức tạp thời gian chạy của thuật toán và mã.

Nếu tất cả những gì bạn muốn làm là đo thời gian đã trôi qua mà một hàm hoặc một phần mã đã chạy trong Python, thì bạn có thể sử dụng các mô-đun timeit hoặc time, tùy thuộc vào thời gian chạy mã.

Answer 5

Sử dụng trang trí để đo thời gian thực hiện cho các chức năng có thể hữu ích. Có một ví dụ tại http://www.zopyx.com/blog/a-python-decorator-for-measuring-the-execution-time-of-methods.

Dưới đây tôi đã không biết xấu hổ đã dán mã từ trang web được đề cập ở trên để ví dụ tồn tại tại SO trong trường hợp trang web bị xóa khỏi mạng.

import time             

def timeit(method): 

    def timed(*args, **kw): 
     ts = time.time() 
     result = method(*args, **kw) 
     te = time.time() 

     print '%r (%r, %r) %2.2f sec' % \ 
       (method.__name__, args, kw, te-ts) 
     return result 

    return timed 

class Foo(object): 

    @timeit 
    def foo(self, a=2, b=3): 
     time.sleep(0.2) 

@timeit 
def f1(): 
    time.sleep(1) 
    print 'f1' 

@timeit 
def f2(a): 
    time.sleep(2) 
    print 'f2',a 

@timeit 
def f3(a, *args, **kw): 
    time.sleep(0.3) 
    print 'f3', args, kw 

f1() 
f2(42) 
f3(42, 43, foo=2) 
Foo().foo() 

// John