Từ điển Python vs Nếu Tốc độ Tuyên bố

Question

Tôi đã tìm thấy một vài liên kết nói về các trường hợp chuyển đổi nhanh hơn trong C++ so với nếu khác vì nó có thể được tối ưu hóa trong quá trình biên dịch. Sau đó tôi tìm thấy một số gợi ý mà mọi người sử dụng từ điển có thể nhanh hơn câu lệnh If. Tuy nhiên, hầu hết các cuộc hội thoại là về một số công việc cuối cùng chỉ cần kết thúc thảo luận rằng họ nên tối ưu hóa các phần khác của mã đầu tiên và nó sẽ không quan trọng trừ khi bạn làm hàng triệu nếu có. Bất cứ ai có thể giải thích lý do tại sao điều này?

Giả sử tôi có 100 số duy nhất sẽ được phát trực tiếp tới mã python liên tục. Tôi muốn kiểm tra xem nó là số nào, sau đó thực hiện một cái gì đó. Vì vậy, tôi có thể làm một tấn nếu có, hoặc tôi có thể đặt mỗi số trong một từ điển. Đối với lợi ích của đối số, cho phép nói một sợi đơn của nó.

Có ai đó hiểu lớp giữa python và thực thi cấp thấp có thể giải thích cách hoạt động của lớp này không?

Cảm ơn :)

Answer 1

Tuy nhiên, hầu hết các cuộc nói chuyện là về ai đó làm việc cuối chỉ kết thúc lên thảo luận rằng họ nên tối ưu hóa các bộ phận khác của mã đầu tiên và nó sẽ không vấn đề trừ khi bạn làm hàng triệu người nếu khác. Bất cứ ai có thể giải thích lý do tại sao điều này là?

Nói chung, bạn chỉ nên tối ưu hóa mã nếu bạn thực sự cần, tức là hiệu suất của chương trình chậm một cách bất thường.

Nếu trường hợp này xảy ra, bạn nên sử dụng trình lược tả để xác định phần nào thực sự gây ra nhiều sự cố nhất. Đối với Python, mô-đun cProfile là khá tốt cho việc này.

Có ai đó hiểu lớp giữa python và mức thấp thực thi có thể giải thích cách hoạt động này không?

Nếu bạn muốn có ý tưởng về cách mã của bạn thực hiện, hãy xem mô-đun dis.

Một ví dụ nhanh chóng ...

import dis 

# Here are the things we might want to do 
def do_something_a(): 
    print 'I did a' 


def do_something_b(): 
    print 'I did b' 


def do_something_c(): 
    print 'I did c' 


# Case 1 
def f1(x): 
    if x == 1: 
     do_something_a() 
    elif x == 2: 
     do_something_b() 
    elif x == 3: 
     do_something_c() 


# Case 2 
FUNC_MAP = {1: do_something_a, 2: do_something_b, 3: do_something_c} 
def f2(x): 
    FUNC_MAP[x]() 


# Show how the functions execute 
print 'Case 1' 
dis.dis(f1) 
print '\n\nCase 2' 
dis.dis(f2) 

... mà kết quả đầu ra ...

Case 1 
18   0 LOAD_FAST    0 (x) 
       3 LOAD_CONST    1 (1) 
       6 COMPARE_OP    2 (==) 
       9 POP_JUMP_IF_FALSE  22 

19   12 LOAD_GLOBAL    0 (do_something_a) 
      15 CALL_FUNCTION   0 
      18 POP_TOP 
      19 JUMP_FORWARD   44 (to 66) 

20  >> 22 LOAD_FAST    0 (x) 
      25 LOAD_CONST    2 (2) 
      28 COMPARE_OP    2 (==) 
      31 POP_JUMP_IF_FALSE  44 

21   34 LOAD_GLOBAL    1 (do_something_b) 
      37 CALL_FUNCTION   0 
      40 POP_TOP 
      41 JUMP_FORWARD   22 (to 66) 

22  >> 44 LOAD_FAST    0 (x) 
      47 LOAD_CONST    3 (3) 
      50 COMPARE_OP    2 (==) 
      53 POP_JUMP_IF_FALSE  66 

23   56 LOAD_GLOBAL    2 (do_something_c) 
      59 CALL_FUNCTION   0 
      62 POP_TOP 
      63 JUMP_FORWARD    0 (to 66) 
     >> 66 LOAD_CONST    0 (None) 
      69 RETURN_VALUE 


Case 2 
29   0 LOAD_GLOBAL    0 (FUNC_MAP) 
       3 LOAD_FAST    0 (x) 
       6 BINARY_SUBSCR 
       7 CALL_FUNCTION   0 
      10 POP_TOP 
      11 LOAD_CONST    0 (None) 
      14 RETURN_VALUE 

... do đó, nó khá dễ dàng để xem những chức năng phải thực hiện các hướng dẫn nhất.

Vì điều đó thực sự nhanh hơn, đó là điều bạn phải kiểm tra bằng cách lập hồ sơ.

Answer 2

if/elif/cấu trúc khác so sánh chính nó đã được trao cho một chuỗi các giá trị có thể từng cái một cho đến khi nó tìm thấy một trận đấu trong điều kiện của một số câu lệnh if, sau đó đọc những gì nó được cho là thực thi từ bên trong khối if. Quá trình này có thể mất nhiều thời gian, vì có quá nhiều séc (trung bình là n/2, đối với n giá trị có thể) phải được thực hiện cho mọi lần tra cứu.

Lý do một chuỗi các câu lệnh if khó tối ưu hơn câu lệnh switch là điều kiện kiểm tra (những gì bên trong parens trong C++) có thể thay đổi trạng thái của một số biến liên quan đến lần kiểm tra tiếp theo. bạn phải làm theo thứ tự. Các hạn chế trên báo cáo chuyển đổi loại bỏ khả năng đó, do đó, thứ tự không quan trọng (tôi nghĩ).

---

Từ điển Python are implemented as hash tables. Ý tưởng là: nếu bạn có thể xử lý số lượng lớn tùy ý và có RAM vô hạn, bạn có thể tạo một mảng lớn các con trỏ hàm được lập chỉ mục bằng cách truyền bất kỳ giá trị tra cứu nào của bạn tới số nguyên và sử dụng chỉ mục đó. Tra cứu sẽ gần như tức thời.

Bạn không thể làm điều đó, tất nhiên, nhưng bạn có thể tạo một mảng của một số chiều dài dễ quản lý, vượt qua giá trị tra cứu để một hash function (mà tạo ra một số nguyên nào, tùy thuộc vào giá trị tra cứu), sau đó % của bạn kết quả với chiều dài mảng của bạn để có được một chỉ mục trong giới hạn của mảng đó. Bằng cách đó, tra cứu mất nhiều thời gian cần thiết để gọi hàm băm một lần, lấy mô-đun và nhảy đến một chỉ mục. Nếu số lượng giá trị tra cứu có thể khác nhau đủ lớn, chi phí của hàm băm sẽ trở nên không đáng kể so với kiểm tra điều kiện n/2.

(Thực tế, vì nhiều giá trị tra cứu khác nhau chắc chắn sẽ ánh xạ tới cùng một chỉ mục, nó không hoàn toàn đơn giản. Bạn phải kiểm tra và giải quyết xung đột có thể xảy ra theo một số cách. của nó là như đã mô tả ở trên.)