Phiên bản này thực hiện chính xác cùng một tập hợp các thao tác chuỗi như phiên bản đầu tiên, nhưng loại bỏ vòng lặp for để chuyển sang vòng lặp ngụ ý nhanh hơn của hàm reduce[]
Chắc chắn, tôi đã trả lời, nhưng nó làm như vậy với chi phí gọi hàm [hàm lambda] cho mỗi mục danh sách. Tôi cá là nó chậm hơn, vì chi phí gọi hàm trong Python lớn hơn chi phí vòng lặp
[OK, vì vậy tôi đã thực hiện các so sánh. f2[] mất nhiều thời gian hơn 60% so với f1[]. Vì vậy, ở đó. -]
Hừm, bạn tôi nói. Tôi cần cái này nhanh hơn. OK, tôi đã nói, làm thế nào về phiên bản này
def f3[list]:
string = ""
for character in map[chr, list]:
string = string + character
return string
Trước sự ngạc nhiên của cả hai chúng tôi, tốc độ f3[] nhanh gấp đôi so với f1[]. Lý do khiến chúng tôi ngạc nhiên gấp đôi. đầu tiên, nó sử dụng nhiều bộ nhớ hơn [kết quả của map[chr, list] là một danh sách khác có cùng độ dài];
Tất nhiên, không gian so với thời gian là một sự đánh đổi nổi tiếng, vì vậy điều đầu tiên không nên làm chúng ta ngạc nhiên. Tuy nhiên, tại sao hai vòng lặp lại nhanh hơn một?
Đầu tiên, trong f1[], hàm tích hợp chr[] được tra cứu trên mỗi lần lặp, trong khi ở f3[], hàm này chỉ được tra cứu một lần [làm đối số cho map[]]. Việc tra cứu này tương đối tốn kém, tôi đã nói với bạn mình, vì các quy tắc phạm vi động của Python có nghĩa là nó được tra cứu lần đầu tiên [không thành công] trong từ điển chung của mô-đun hiện tại, sau đó trong từ điển của hàm tích hợp [nơi nó được tìm thấy . Tồi tệ hơn, các tra cứu từ điển không thành công [trung bình] chậm hơn một chút so với các tra cứu thành công, do cách hoạt động của chuỗi băm
Lý do thứ hai khiến f3[] nhanh hơn f1[] là lệnh gọi chr[item], được thực thi bởi trình thông dịch mã byte, có thể chậm hơn một chút so với khi được thực thi bởi hàm map[] - trình thông dịch mã byte phải thực thi
Điều này khiến chúng tôi cân nhắc một giải pháp thỏa hiệp, điều này sẽ không lãng phí thêm dung lượng nhưng sẽ tăng tốc độ tìm kiếm hàm chr[]
def f4[list]:
string = ""
lchr = chr
for item in list:
string = string + lchr[item]
return string
Như mong đợi, f4[] chậm hơn f3[], nhưng chỉ 25%; . Điều này là do tra cứu biến cục bộ nhanh hơn nhiều so với tra cứu biến toàn cục hoặc tích hợp sẵn. "trình biên dịch" Python tối ưu hóa hầu hết các thân hàm để đối với các biến cục bộ, không cần tra cứu từ điển mà chỉ cần thao tác lập chỉ mục mảng đơn giản là đủ. Tốc độ tương đối của f4[] so với f1[] và f3[] cho thấy rằng cả hai lý do khiến f3[] đóng góp nhanh hơn, nhưng lý do đầu tiên [ít tra cứu hơn] quan trọng hơn một chút. [Để có được dữ liệu chính xác hơn về điều này, chúng tôi sẽ phải sử dụng công cụ thông dịch. ]
Tuy nhiên, phiên bản tốt nhất của chúng tôi, f3[], chỉ nhanh gấp đôi so với phiên bản đơn giản nhất, f1[]. Chúng ta có thể làm tốt hơn không?
Tôi đã lo lắng rằng hành vi bậc hai của thuật toán đang giết chết chúng tôi. Cho đến nay, chúng tôi đã sử dụng danh sách 256 số nguyên làm dữ liệu kiểm tra, vì đó là thứ mà bạn tôi cần hàm cho. Nhưng nếu nó được áp dụng cho một danh sách hai nghìn ký tự thì sao? . Dễ dàng nhận thấy, ngoài tốn phí, để tạo một danh sách độ dài N theo cách này còn có 1 + 2 + 3 +. + [N-1] ký tự được sao chép tổng cộng, hoặc N*[N-1]/2, hoặc 0. 5*N**2 - 0. 5*N. Ngoài ra, còn có N hoạt động cấp phát chuỗi, nhưng đối với N đủ lớn, thuật ngữ chứa N**2 sẽ chiếm ưu thế. Thật vậy, đối với một danh sách dài gấp 8 lần [2048 mục], tất cả các chức năng này đều mất nhiều thời gian hơn gấp 8 lần; . Tôi không dám thử một danh sách dài 64 lần
Có một kỹ thuật chung để tránh hành vi bậc hai trong các thuật toán như thế này. Tôi đã mã hóa nó như sau cho các chuỗi có chính xác 256 mục
def f5[list]:
string = ""
for i in range[0, 256, 16]: # 0, 16, 32, 48, 64, ...
s = ""
for character in map[chr, list[i:i+16]]:
s = s + character
string = string + s
return string
Thật không may, đối với danh sách 256 mục, phiên bản này chạy chậm hơn một chút [mặc dù trong vòng 20%] của f3[]. Vì viết một phiên bản chung sẽ chỉ làm nó chậm hơn, nên chúng tôi không bận tâm theo đuổi con đường này nữa [ngoại trừ việc chúng tôi cũng so sánh nó với một biến thể không sử dụng map[], tất nhiên là nó lại chậm hơn]
Cuối cùng, tôi đã thử một cách tiếp cận hoàn toàn khác. chỉ sử dụng các vòng lặp ngụ ý. Lưu ý rằng toàn bộ hoạt động có thể được mô tả như sau. áp dụng chr[] cho từng mục danh sách; . Chúng tôi đã sử dụng một vòng lặp ngụ ý cho phần đầu tiên. bản đồ[]. May mắn thay, có một số hàm nối chuỗi trong mô-đun chuỗi được triển khai trong C. Đặc biệt, chuỗi. joinfields[list_of_strings, delimiter] nối một danh sách các chuỗi, đặt một dấu phân cách lựa chọn giữa mỗi hai chuỗi. Không có gì ngăn chúng ta nối một danh sách các ký tự [chỉ là các chuỗi có độ dài một trong Python], sử dụng chuỗi trống làm dấu phân cách. Lo và kìa
import string
def f6[list]:
return string.joinfields[map[chr, list], ""]
Chức năng này chạy nhanh gấp bốn đến năm lần so với ứng cử viên nhanh nhất của chúng tôi, f3[]. Hơn nữa, nó không có hành vi bậc hai của các phiên bản khác
Và người chiến thắng là
Ngày hôm sau, tôi nhớ một góc kỳ lạ của Python. mô-đun mảng. Điều này xảy ra để có một thao tác tạo một mảng các số nguyên rộng 1 byte từ danh sách các số nguyên Python và mọi mảng có thể được ghi vào một tệp hoặc được chuyển đổi thành một chuỗi dưới dạng cấu trúc dữ liệu nhị phân. Đây là chức năng của chúng tôi được thực hiện bằng cách sử dụng các hoạt động này
import array
def f7[list]:
return array.array['B', list].tostring[]
Tốc độ này nhanh gấp khoảng ba lần so với f6[] hoặc nhanh gấp 12 đến 15 lần so với f3[]. nó cũng sử dụng ít bộ nhớ trung gian hơn - nó chỉ phân bổ 2 đối tượng N byte [cộng với chi phí cố định], trong khi f6[] bắt đầu bằng cách phân bổ danh sách N mục, thường tốn 4N byte [8N byte trên máy 64 bit] -
Dừng lại, bạn của tôi nói, trước khi bạn rơi vào thời điểm tiêu cực - điều này đủ nhanh cho chương trình của tôi. Tôi đã đồng ý, mặc dù tôi đã muốn thử một cách tiếp cận khác. viết toàn bộ chức năng trong C. Điều này có thể có các yêu cầu lưu trữ tối thiểu [nó sẽ phân bổ một chuỗi có độ dài N ngay lập tức] và lưu một số hướng dẫn trong mã C mà tôi biết là có trong mô-đun mảng, do tính tổng quát của nó [nó hỗ trợ độ rộng số nguyên là 1, 2 . Tuy nhiên, sẽ không thể tránh khỏi việc phải trích xuất từng mục từ danh sách và trích xuất số nguyên C từ chúng, cả hai đều là hoạt động khá tốn kém trong API Python-C, vì vậy tôi mong đợi ở . Với nỗ lực viết và thử nghiệm một tiện ích mở rộng [so với việc tạo ra các lớp lót Python đó], cũng như sự phụ thuộc vào tiện ích mở rộng Python không chuẩn, tôi đã quyết định không theo đuổi tùy chọn này
Sự kết luận
Nếu bạn cảm thấy cần tốc độ, hãy sử dụng các chức năng tích hợp sẵn - bạn không thể đánh bại một vòng lặp được viết bằng C. Kiểm tra hướng dẫn sử dụng thư viện để biết chức năng tích hợp thực hiện những gì bạn muốn. Nếu không có, đây là một số hướng dẫn để tối ưu hóa vòng lặp
- Quy tắc số một. chỉ tối ưu hóa khi có tắc nghẽn tốc độ đã được chứng minh. Chỉ tối ưu vòng lặp trong cùng. [Quy tắc này độc lập với Python, nhưng lặp lại nó cũng không hại gì, vì nó có thể tiết kiệm rất nhiều công sức. . -]
- Nhỏ là đẹp. Với các khoản phí khổng lồ của Python đối với các hướng dẫn mã byte và tra cứu biến, việc thêm các kiểm tra bổ sung hiếm khi được đền đáp để tiết kiệm một chút công việc
- Sử dụng các hoạt động nội tại. Vòng lặp ngụ ý trong map[] nhanh hơn vòng lặp for rõ ràng;
- Tránh gọi các hàm được viết bằng Python trong vòng lặp bên trong của bạn. Điều này bao gồm lambdas. Nội tuyến vòng lặp bên trong có thể tiết kiệm rất nhiều thời gian
- Biến cục bộ nhanh hơn biến toàn cục; . Và trong Python, tên hàm [toàn cầu hoặc tích hợp sẵn] cũng là hằng số toàn cầu
- Cố gắng sử dụng map[], filter[] hoặc reduce[] để thay thế vòng lặp for rõ ràng, nhưng chỉ khi bạn có thể sử dụng hàm tích hợp. map với chức năng tích hợp vượt qua vòng lặp for, nhưng vòng lặp for với mã nội tuyến sẽ vượt qua map với chức năng lambda
- Kiểm tra các thuật toán của bạn cho hành vi bậc hai. Nhưng lưu ý rằng một thuật toán phức tạp hơn chỉ mang lại hiệu quả cho N lớn - đối với N nhỏ, độ phức tạp không được đền đáp. Trong trường hợp của chúng tôi, 256 hóa ra đủ nhỏ để phiên bản đơn giản hơn vẫn nhanh hơn một chút. Số dặm của bạn có thể thay đổi - điều này đáng để điều tra
- Và cuối cùng nhưng không kém phần quan trọng. thu thập dữ liệu. Mô-đun hồ sơ tuyệt vời của Python có thể nhanh chóng hiển thị nút cổ chai trong mã của bạn. nếu bạn đang xem xét các phiên bản khác nhau của một thuật toán, hãy kiểm tra thuật toán đó trong một vòng lặp chặt chẽ bằng cách sử dụng thời gian. chức năng đồng hồ []
Nhân tiện, đây là chức năng thời gian mà tôi đã sử dụng. nó gọi hàm f n*10 lần với đối số a và in tên hàm theo sau là thời gian thực hiện, được làm tròn thành mili giây. 10 cuộc gọi lặp lại được thực hiện để giảm thiểu chi phí vòng lặp của chính chức năng thời gian. Bạn có thể tiến xa hơn nữa và thực hiện 100 cuộc gọi. Cũng lưu ý rằng phạm vi biểu thức [n] được tính toán bên ngoài dấu ngoặc thời gian - một mẹo khác để giảm thiểu chi phí hoạt động do chức năng thời gian gây ra. Nếu bạn lo lắng về chi phí này, bạn có thể hiệu chỉnh nó bằng cách gọi chức năng định thời với chức năng không làm gì cả
import time
def timing[f, n, a]:
print f.__name__,
r = range[n]
t1 = time.clock[]
for i in r:
f[a]; f[a]; f[a]; f[a]; f[a]; f[a]; f[a]; f[a]; f[a]; f[a]
t2 = time.clock[]
print round[t2-t1, 3]
phần kết
Vài ngày sau, bạn tôi quay lại với câu hỏi. làm thế nào để bạn thực hiện các hoạt động ngược lại? . e. tạo danh sách các giá trị ASCII số nguyên từ một chuỗi. Ồ không, chúng ta lại bắt đầu, nó vụt qua tâm trí tôi
Nhưng lần này, nó tương đối không đau. Có hai ứng cử viên, rõ ràng
def g1[string]:
return map[ord, string]
và phần nào ít rõ ràng hơn
import array
def g2[string]:
return array.array['b', string].tolist[]
Thời gian cho những điều này cho thấy rằng g2[] nhanh gấp khoảng năm lần so với g1[]. Có một nhược điểm. g2[] trả về số nguyên trong phạm vi -128. 127, trong khi g1[] trả về số nguyên trong phạm vi 0. 255. Nếu bạn cần các số nguyên dương, g1[] sẽ nhanh hơn bất kỳ thao tác hậu xử lý nào mà bạn có thể thực hiện đối với kết quả từ g2[]. [Ghi chú. vì bài tiểu luận này được viết, mã kiểu chữ 'B' đã được thêm vào mô-đun mảng, nơi lưu trữ các byte không dấu, vì vậy không có lý do gì để thích g1[] hơn nữa. ]