Hướng dẫn speed up for loop python - tăng tốc cho vòng lặp python

Danh sách các hệ thống toàn diện, lập chỉ mục boolean và biên dịch đúng (JIT) để tăng tốc độ lên tới 200 lần.

Khi khám phá một bộ dữ liệu mới và muốn thực hiện một số kiểm tra hoặc tính toán nhanh chóng, người ta sẽ bị cám dỗ để ghi mã một cách lười biếng mà không suy nghĩ nhiều về tối ưu hóa. Mặc dù điều này có thể hữu ích ngay từ đầu, nhưng có thể dễ dàng xảy ra khi thời gian chờ thực thi mã vượt qua thời gian mà nó sẽ có để viết mọi thứ đúng cách.hen exploring a new dataset and wanting to do some quick checks or calculations, one is tempted to lazily write code without giving much thought about optimization. While this might be useful in the beginning, it can easily happen that the time waiting for code execution overcomes the time that it would have taken to write everything properly.

Bài viết này cho thấy một số cách cơ bản về cách tăng tốc thời gian tính toán trong Python. Với ví dụ về dữ liệu lọc, chúng tôi sẽ thảo luận về một số phương pháp sử dụng Python, Numpy, Numba, Pandas cũng như K-D-cây thuần túy.

Lọc nhanh các bộ dữ liệu

Là một nhiệm vụ ví dụ, chúng tôi sẽ giải quyết vấn đề lọc các bộ dữ liệu một cách hiệu quả. Đối với điều này, chúng tôi sẽ sử dụng các điểm trong một không gian hai chiều, nhưng đây có thể là bất cứ thứ gì trong không gian N chiều, cho dù đây là dữ liệu của khách hàng hay các phép đo của một thí nghiệm.

Hãy giả sử, chúng tôi muốn trích xuất tất cả các điểm trong một hình chữ nhật với giữa [0,2, 0,4] và [0,4, 0,6]. Cách ngây thơ để làm điều này sẽ là vòng lặp cho từng điểm và kiểm tra xem nó có đáp ứng tiêu chí này không. CodeWise, điều này có thể trông giống như sau: Đầu tiên, chúng tôi tạo một hàm để phân phối ngẫu nhiên các điểm trong không gian n chiều với Numpy, sau đó là một hàm để lặp qua các mục. Để đo thời gian tính toán, chúng tôi sử dụng thời gian và trực quan hóa các kết quả lọc bằng matplotlib.

Loop: 72 ms ± 2.11 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Như chúng ta có thể thấy, đối với máy được thử nghiệm, nó đã mất khoảng. 70 ms để trích xuất các điểm trong một hình chữ nhật từ bộ dữ liệu 100.000 điểm.

Lưu ý rằng khi kết hợp các biểu thức, bạn muốn sử dụng logic và (và) không phải là bitwise và (&). Khi điều kiện đầu tiên là sai, nó dừng đánh giá.

Mặc dù Numpy là tốt để tương tác với các mảng N chiều lớn, chúng tôi cũng nên xem xét chi phí bổ sung mà chúng tôi có được bằng cách sử dụng các đối tượng không có. Trong ví dụ cụ thể này, chúng tôi không sử dụng bất kỳ hoạt động toán học nào mà chúng tôi có thể hưởng lợi từ vectơ hóa Numpy.

Vì vậy, bây giờ hãy để điểm chuẩn của vòng lặp này chống lại việc triển khai Python thuần túy của vòng lặp. Ở đây, sự khác biệt là sử dụng một danh sách các bộ dữ liệu thay vì một mảng numpy.

Python loop: 27.9 ms ± 638 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Việc thực hiện bây giờ chỉ mất khoảng. 28 ms, vì vậy ít hơn một nửa thời gian thực hiện trước đó. Điều này nhấn mạnh sự giảm hiệu suất tiềm năng có thể xảy ra khi sử dụng các gói được tối ưu hóa cao cho các nhiệm vụ khá đơn giản.

Chức năng Python: Danh sách hiểu, bản đồ và bộ lọc

Để thực hiện một so sánh rộng hơn, chúng tôi cũng sẽ điểm chuẩn so với ba phương thức tích hợp trong Python: Liệt kê toàn diện, bản đồ và bộ lọc.

• Danh sách hiểu biết: Danh sách toàn diện được biết là thực hiện, nói chung, tốt hơn so với các vòng lặp vì chúng không cần gọi hàm nối ở mỗi lần lặp.
• Bản đồ: Điều này áp dụng một hàm cho tất cả các yếu tố của danh sách đầu vào.
• Bộ lọc: Điều này trả về một danh sách các phần tử mà một hàm trả về true.

List comprehension: 21.3 ms ± 299 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Filter:   26.8 ms ± 349 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Map:   27 ms ± 265 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Phương pháp hiểu danh sách nhanh hơn một chút. Đây là, như chúng tôi mong đợi, từ việc tiết kiệm thời gian không gọi chức năng nối tiếp. Hàm bản đồ và bộ lọc không cho thấy sự gia tăng tốc độ đáng kể so với vòng python tinh khiết.

Suy nghĩ về việc triển khai đầu tiên của hơn 70 ms Tại sao người ta nên sử dụng Numpy ngay từ đầu? Một điều chúng ta có thể làm là sử dụng lập chỉ mục Boolean. Ở đây chúng tôi thực hiện kiểm tra cho từng cột tiêu chí khôn ngoan. Sau đó, chúng ta có thể kết hợp chúng với một chỉ mục boolean và truy cập trực tiếp các giá trị nằm trong phạm vi.

Boolean index: 639 µs ± 28.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Giải pháp sử dụng chỉ số Boolean chỉ mất khoảng. 640 Laus, vì vậy một cải tiến gấp 50 lần về tốc độ so với lần thực hiện nhanh nhất mà chúng tôi đã thử nghiệm cho đến nay.

Đi nhanh hơn: Numba

Chúng ta thậm chí có thể đẩy điều này hơn nữa? Vâng, chúng tôi có thể. Một cách là sử dụng numba:

Numba dịch các hàm Python sang mã máy được tối ưu hóa trong thời gian chạy bằng thư viện trình biên dịch LLVM tiêu chuẩn trong ngành. Các thuật toán số được biên dịch numba trong Python có thể tiếp cận tốc độ của C hoặc Fortran.

Việc triển khai Numba khá dễ dàng nếu người ta sử dụng Numpy và đặc biệt hiệu suất nếu mã có nhiều vòng lặp. Nếu các chức năng được thiết lập chính xác, tức là sử dụng các vòng lặp và các hàm numpy cơ bản, một bổ sung đơn giản của trình trang trí @njit sẽ gắn cờ hàm được biên dịch trong numba và sẽ được thưởng với tốc độ tăng. Vui lòng kiểm tra tài liệu Numbas để tìm hiểu về các chi tiết trong việc thiết lập các chức năng tương thích numba.

Lưu ý rằng chúng tôi đang sử dụng phiên bản gần đây nhất của Numba (0,45) đã giới thiệu danh sách đánh máy. Ngoài ra, lưu ý rằng chúng tôi đang thực hiện các chức năng một lần trước khi thời gian không tính đến thời gian biên dịch. Bây giờ, hãy để Lừa xem các chức năng thực hiện như thế nào khi được biên dịch với Numba:

Boolean index with numba: 341 µs ± 8.97 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Loop with numba:  970 µs ± 11.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Sau khi biên dịch chức năng với LLVM, ngay cả thời gian thực hiện cho bộ lọc boolean nhanh là một nửa và chỉ mất khoảng. 340 Pha. Điều thú vị hơn, ngay cả vòng lặp không hiệu quả ngay từ đầu hiện được tăng từ 72 ms lên dưới 1 ms, làm nổi bật tiềm năng của numba đối với mã tối ưu hóa kém.

Dữ liệu trong Bảng: Gấu trúc

Trước đây, chúng tôi đã thấy rằng các loại dữ liệu có thể ảnh hưởng đến kiểu dữ liệu. Người ta phải quyết định cẩn thận giữa hiệu suất mã, giao tiếp dễ dàng và mã có thể đọc được. Pandas, ví dụ, rất hữu ích trong việc điều khiển dữ liệu bảng. Tuy nhiên, cấu trúc dữ liệu có thể giảm hiệu suất. Để đặt điều này trong quan điểm, chúng tôi cũng sẽ so sánh các chức năng trên bo mạch để lọc như truy vấn và eval và cũng chỉ lập boolean.

Pandas Query:  8.77 ms ± 173 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Pandas Eval:  8.23 ms ± 131 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Pandas Boolean index: 7.73 ms ± 178 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Có thể cho rằng, thời gian thực hiện nhanh hơn nhiều so với vòng lặp ban đầu của chúng tôi không được tối ưu hóa. Tuy nhiên, nó chậm hơn đáng kể so với các phiên bản tối ưu hóa. Do đó, nó phù hợp để thăm dò ban đầu nhưng sau đó nên được tối ưu hóa.

So sánh định lượng i

Để so sánh các phương pháp theo cách định lượng hơn, chúng ta có thể đánh giá chúng với nhau. Đối với điều này, chúng tôi sử dụng gói perfplot cung cấp một cách tuyệt vời để làm như vậy.

Lưu ý rằng thời gian thực hiện, cũng như các kích thước dữ liệu, nằm trên thang đo logarit

Nhiều truy vấn và bộ dữ liệu lớn hơn

Cuối cùng, chúng tôi sẽ thảo luận về các chiến lược mà chúng tôi có thể sử dụng cho các bộ dữ liệu lớn hơn và khi sử dụng nhiều truy vấn hơn. Cho đến nay chúng tôi đã xem xét thời gian khi luôn kiểm tra một điểm tham chiếu cố định. Giả sử thay vì một điểm, chúng ta có một danh sách các điểm và muốn lọc dữ liệu nhiều lần. Rõ ràng, sẽ có lợi nếu chúng ta có thể sử dụng một số thứ tự trong dữ liệu, ví dụ: Khi có một điểm ở góc trên bên trái chỉ đến các điểm truy vấn ở góc cụ thể đó.

Chúng ta có thể làm như vậy bằng cách sắp xếp dữ liệu trước và sau đó có thể chọn một tiểu mục bằng một chỉ mục. Ý tưởng ở đây là thời gian để sắp xếp mảng phải được bù vào thời gian lưu liên tục tìm kiếm một mảng nhỏ hơn.

Để tăng thêm độ phức tạp, bây giờ chúng tôi cũng tìm kiếm trong chiều thứ ba, cắt giảm hiệu quả một voxel trong không gian. Vì chúng tôi chỉ quan tâm đến thời gian, hiện tại, chúng tôi chỉ báo cáo độ dài của các mảng được lọc.

Chúng tôi viết lại hàm boolean_index_numba để chấp nhận khối lượng tham chiếu tùy ý ở dạng [xmin, xmax], [ymin, ymax] và [zmin, zmax]. Chúng tôi xác định một trình bao bọc có tên nhiều_queries liên tục thực thi chức năng này. Việc so sánh sẽ chống lại hàm nhiều_queries_index sắp xếp dữ liệu trước và chỉ chuyển một tập hợp con cho boolean_index_numba_multiple.

Multiple queries:  433 ms ± 11.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Multiple queries with subset: 110 ms ± 1.66 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Count for multiple_queries: 687,369
Count for multiple_queries: 687,369

Đối với ví dụ này, thời gian thực hiện hiện đã giảm xuống chỉ còn một phần tư. Tỷ lệ tăng tốc độ với số lượng điểm truy vấn. Như một lưu ý bổ sung, việc trích xuất chỉ số tối thiểu và tối đa tương đối nhanh.

Cấu trúc khác: K-D-Trees

Ý tưởng cấu trúc trước dữ liệu để tăng thời gian truy cập có thể được mở rộng hơn nữa, ví dụ: Người ta có thể nghĩ đến việc sắp xếp lại trên dữ liệu được tập hợp lại. Người ta có thể nghĩ đến việc tạo ra các thùng N-chiều để tập hợp dữ liệu hiệu quả.

Một cách tiếp cận mở rộng ý tưởng này và sử dụng cấu trúc cây để lập chỉ mục dữ liệu là cây K-D cho phép tra cứu nhanh hàng xóm cho một điểm nhất định. Dưới một định nghĩa ngắn từ Wikipedia:

Trong khoa học máy tính, một cây K-D là một cấu trúc dữ liệu phân vùng không gian để tổ chức các điểm trong không gian k chiều. Cây K-D là một cấu trúc dữ liệu hữu ích cho một số ứng dụng, chẳng hạn như các tìm kiếm liên quan đến khóa tìm kiếm đa chiều.

May mắn thay, chúng tôi không cần phải tự mình thực hiện K-D-Tree nhưng có thể sử dụng một triển khai hiện có từ SCIPY. Nó không chỉ có một triển khai Python thuần túy mà còn là phiên bản được tối ưu hóa C mà chúng ta có thể sử dụng cho phương pháp này. Nó đi kèm với một chức năng tích hợp có tên là query_ball_tree cho phép tìm kiếm tất cả các hàng xóm trong một bán kính nhất định. Khi chúng tôi đang tìm kiếm các điểm trong một hình vuông xung quanh một điểm nhất định, chúng tôi chỉ cần đặt định mức Minkowski thành Chebyshev (P = Hồi Inf,).

Tree construction: 37.7 ms ± 1.39 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Query time:  86.4 µs ± 1.61 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Total time:  224 ms ± 11.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Count for k-d-tree: 687,369

Từ thời gian, chúng ta có thể thấy rằng phải mất khoảng 40 ms để xây dựng cây, tuy nhiên, bước truy vấn chỉ có trong phạm vi 100, do đó thậm chí còn nhanh hơn so với việc lập chỉ mục Boolean được tối ưu hóa.

Lưu ý rằng K-D-Tree chỉ sử dụng một khoảng cách duy nhất, vì vậy nếu người ta quan tâm đến việc tìm kiếm trong một hình chữ nhật và không phải một hình vuông, người ta sẽ cần mở rộng trục. Cũng có thể thay đổi định mức Minkowski thành ví dụ: Tìm kiếm trong một vòng tròn thay vì một hình vuông. Theo đó, việc tìm kiếm với một cửa sổ tương đối có thể đạt được bằng cách chuyển đổi log.

So sánh định lượng II

Một lần nữa chúng tôi sẽ sử dụng perfplot để đưa ra một so sánh định lượng hơn. Đối với điều này, chúng tôi sẽ truy vấn một triệu điểm so với số điểm ngày càng tăng.

Lưu ý rằng chúng tôi kiểm tra dữ liệu trong phạm vi lớn, thời gian thực hiện của perfplot có thể rất chậm

Đối với phạm vi dữ liệu này, sự so sánh giữa KDTREE, nhiều_queries và phiên bản được lập chỉ mục của nhiều truy vấn cho thấy hành vi mong đợi: chi phí ban đầu của việc xây dựng cây hoặc sắp xếp dữ liệu thừa thềm khi tìm kiếm đối với các bộ dữ liệu lớn hơn. KDTREE dự kiến ​​sẽ vượt trội so với phiên bản được lập chỉ mục của nhiều truy vấn cho các bộ dữ liệu lớn hơn.

Đó là để nhấn mạnh rằng khi việc triển khai SCIPY dễ dàng chấp nhận dữ liệu N chiều, rất đơn giản để mở rộng cho nhiều chiều hơn nữa.

Bản tóm tắt

Tốc độ lọc thử nghiệm cho các phương pháp khác nhau làm nổi bật cách mã có thể được tối ưu hóa một cách hiệu quả. Thời gian thực hiện dao động từ hơn 70 ms để triển khai chậm đến khoảng. 300 Pha cho một phiên bản tối ưu hóa bằng cách sử dụng lập chỉ mục Boolean, hiển thị hơn 200 lần cải tiến. Những phát hiện chính có thể được tóm tắt như sau:

• Python thuần túy có thể nhanh.
• Numba rất có lợi ngay cả đối với các vòng không được tối ưu hóa.
• Các chức năng trên tàu có thể nhanh hơn Python thuần túy nhưng cũng có khả năng cải thiện.
• Khi thực hiện các truy vấn lớn trên các bộ dữ liệu lớn, việc sắp xếp dữ liệu có lợi.
• K-D-cây cung cấp một cách hiệu quả để lọc trong không gian N chiều khi có các truy vấn lớn.

Thời gian thực hiện có thể tăng tốc hơn nữa khi nghĩ đến song song, trên CPU hoặc GPU. Lưu ý rằng dấu chân bộ nhớ của các phương pháp không được xem xét cho các ví dụ này. Khi có các tệp quá lớn để tải trong bộ nhớ, việc phân hủy các biểu thức dữ liệu hoặc trình tạo có thể tiện dụng. Nếu bạn thấy rằng bất kỳ cách tiếp cận nào bị thiếu hoặc có khả năng cung cấp kết quả tốt hơn, hãy cho tôi biết. Tôi tò mò muốn xem những cách khác tồn tại để thực hiện lọc nhanh.

Là cho vòng lặp nhanh hơn trong khi vòng lặp trong Python?

Python có phải là vòng lặp nhanh không?

Làm cách nào để thực hiện Python nhanh hơn?

Bản đồ có nhanh hơn so với vòng lặp không?