Hướng dẫn is reduce faster than for loop python? - giảm nhanh hơn for loop python?

Cảnh báo

Trang này ở đây vì lý do lịch sử và nó có thể chứa thông tin lỗi thời hoặc không chính xác.

Phiên bản đầu tiên tôi nghĩ ra hoàn toàn đơn giản:

    def f1(list):
        string = ""
        for item in list:
            string = string + chr(item)
        return string

Đó không thể là cách nhanh nhất để làm điều đó, bạn của tôi nói. Làm thế nào về điều này:

    def f2(list):
        return reduce(lambda string, item: string + chr(item), list, "")

Phiên bản này thực hiện chính xác cùng một tập hợp các hoạt động chuỗi như phiên bản đầu tiên, nhưng được loại bỏ chi phí vòng lặp cho vòng lặp nhanh hơn, ngụ ý của hàm giảm ().

Chắc chắn, tôi đã trả lời, nhưng nó làm như vậy với chi phí của một cuộc gọi chức năng (hàm Lambda) cho mỗi mục danh sách. Tôi betcha nó chậm hơn, vì chức năng gọi trên đầu trong Python lớn hơn so với chi phí vòng lặp.

(OK, vì vậy tôi đã thực hiện các so sánh.

Hmm, bạn của tôi nói. Tôi cần điều 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 chúng tôi, F3 () đã nhanh gấp đôi so với F1 ()! Lý do khiến chúng tôi ngạc nhiên là gấp đôi: đầu tiên, nó sử dụng nhiều lưu trữ hơn (kết quả của MAP (CHR, danh sách) là một danh sách khác có cùng độ dài); Thứ hai, nó chứa hai vòng thay vì một (một (một hàm được hàm ý bởi hàm map () và vòng lặp cho vòng).

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 người đầu tiên không nên làm chúng tôi ngạc nhiên. Tuy nhiên, làm thế nào có hai vòng nhanh hơn một vòng? Hai lý do.

Đầ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 trong f3 (), nó chỉ được tra cứu một lần (như đối số để lập bản đồ ()). Việc tìm kiếm này tương đối đắt tiền, tôi đã nói với bạn tôi, vì các quy tắc phạm vi năng động của Python có nghĩa là lần đầu tiên nó được tra cứu (không thành công) trong từ điển toàn cầu của mô-đun hiện tại, và sau đó trong từ điển của chức năng tích hợp (nơi nó được tìm thấy ). Tồi tệ hơn, tra cứu từ điển không thành công là (trung bình) chậm hơn một chút so với những người thành công, vì cách thức hoạt động của chuỗi băm.

Lý do thứ hai tại sao f3 () nhanh hơn f1 () là cuộc gọi đến chr (item), do trình thông dịch bytecode thực thi, có lẽ chậm hơn một chút so với khi được thực thi bởi hàm map () Ba hướng dẫn bytecode cho mỗi cuộc gọi (tải 'chr', tải 'mục', cuộc gọi), trong khi hàm bản đồ () thực hiện tất cả trong C.

Điều này khiến chúng tôi xem xét một sự thỏa hiệp, điều này sẽ không lãng phí thêm không gian, nhưng sẽ tăng tốc độ tra cứu cho hàm chr ():

    def f4(list):
        string = ""
        lchr = chr
        for item in list:
            string = string + lchr(item)
        return string

Đúng như dự đoán, F4 () chậm hơn F3 (), nhưng chỉ bằng 25%; Nó vẫn nhanh hơn khoảng 40% so với F1 (). Điều này là do các tra cứu biến cục bộ nhanh hơn nhiều so với tra cứu biến toàn cầu hoặc tích hợp: "Trình biên dịch" Python tối ưu hóa hầu hết các cơ quan chức năng để đối với các biến cục bộ, không cần tra cứu từ điển, nhưng một hoạt động 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 cả hai lý do tại sao F3 () đóng góp nhanh hơn, nhưng lý do đầu tiên (nhỏ hơn) là 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 điều chỉnh trình 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 đã 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 thử nghiệm, vì đó là những gì bạn tôi cần chức năng. Nhưng điều gì sẽ xảy ra nếu nó được áp dụng cho một danh sách hai ngàn ký tự? Chúng tôi sẽ kết hợp các chuỗi dài hơn và dài hơn, một nhân vật tại một thời điểm. Thật dễ dàng để thấy rằng, ngoài chi phí, để tạo một danh sách độ dài n theo cách này, còn có 1 + 2 + 3 + ... + (n-1) các 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 phân bổ chuỗi, nhưng đối với N đủ lớn, thuật ngữ chứa n ** 2 sẽ chiếm lấy. 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 hơn 8 lần; Trên thực tế, gần 16 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 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 phạm vi 20%) của F3 (). Vì viết một phiên bản chung sẽ chỉ làm chậm nó hơn, chúng tôi không bận tâm đến việc theo đuổi con đường này thêm 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à 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; Sau đó kết hợp các ký tự kết quả. Chúng tôi đã sử dụng một vòng lặp ngụ ý cho phần đầu tiên: map (). May mắn thay, có một số hàm kết nối chuỗi trong mô -đun chuỗi được triển khai trong C. Cụ thể, String.JoinFields (list_of_strings, Delimiter) kết hợp một danh sách các chuỗi, đặt một 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à 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), "")

Hàm 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 hoạt động để tạo ra 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 triển khai 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()

Điều này nhanh gấp 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 lưu trữ 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 các mục, thường có giá 4n byte (8N byte trên máy 64 bit) - Giả sử các đối tượng ký tự được chia sẻ với các đối tượng tương tự ở nơi khác trong chương trình (như số nguyên nhỏ, chuỗi python có độ dài một trong hầu hết các trường hợp).

Dừng lại, bạn của tôi, trước khi bạn bước vào thời gian 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ử thêm một cách tiếp cận: Viết toàn bộ hàm 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 độ dài n ngay lập tức) và lưu một vài hướng dẫn trong mã C mà tôi biết đã có trong mô -đun mảng, vì tính bền của nó (nó hỗ trợ chiều rộng nguyên là 1, 2 và 4 byte). Tuy nhiên, sẽ không thể tránh được các mục từ danh sách một lần và trích xuất số nguyên C từ chúng, cả hai đều là các hoạt động khá tốn kém trong API Python-C, vì vậy tôi mong đợi tại Tăng tốc khiêm tốn nhất so với F7 (). Với nỗ lực viết và thử nghiệm một phần mở rộng (so với việc đánh bại những người bạn Python đó), cũng như sự phụ thuộc vào phần 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 có tốc độ, hãy tìm các chức năng tích hợp-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 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ó ai, đâ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 hóa vòng lặp trong cùng. (Quy tắc này độc lập với Python, nhưng nó không làm tổn thương việc lặp lại nó, vì nó có thể tiết kiệm rất nhiều công việ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, nó hiếm khi được thanh toán để thêm các bài kiểm tra bổ sung để tiết kiệm một chút công việc.
• Sử dụng các hoạt động nội tại. Một vòng lặp ngụ ý trong bản đồ () nhanh hơn một vòng rõ ràng cho vòng lặp; Một vòng lặp trong thời gian với một bộ đếm vòng rõ ràng thậm chí chậm hơn.
• Tránh gọi các chức năng đượ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. Lắp vòng lặp bên trong có thể tiết kiệm rất nhiều thời gian.
• Các biến cục bộ nhanh hơn toàn cầu; Nếu bạn sử dụng hằng số toàn cầu trong một vòng lặp, hãy sao chép nó vào một biến cục bộ trước vòng lặp. Và trong Python, tên chức năng (toàn cầu hoặc tích hợp) cũng là các hằng số toàn cầu!
• Cố gắng sử dụng map (), filter () hoặc giảm () để thay thế một vòng lặp rõ ràng cho vòng lặp, nhưng chỉ khi bạn có thể sử dụng hàm tích hợp: bản đồ với nhịp chức năng tích hợp cho vòng lặp, nhưng Code Code Beats Bản đồ với chức năng Lambda!
• Kiểm tra thuật toán của bạn để biết 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ỉ được đền đáp 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. Số dặm của bạn có thể khác nhau - đ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 thuật toán, hãy kiểm tra nó trong một vòng lặp chặt chẽ bằng hàm thời gian.clock ().

Nhân tiện, đây là chức năng thời gian mà tôi đã sử dụng. Nó gọi một hàm f n*10 lần với đối số A và in tên hàm theo sau là thời gian nó được thực hiện, được làm tròn đến mili giây. 10 cuộc gọi lặp đi lặp lại được thực hiện để giảm thiểu chi phí vòng lặp của chính hàm thời gian. Bạn có thể đi 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 bên ngoài khung thời gian - một thủ thuật khác để giảm thiểu chi phí do hàm 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 hàm thời gian với chức năng không làm gì.

from functools import reduce
from numpy import array, arange
from time import time

def add(x, y):
    return x + y

def sum_columns(x):
    if x.any():
        width = len(x[0])
        total = array([0] * width)
    for row in x:
        total += array(row)
    return total

l = arange(3000000)
l = array([l, l, l])

start = time()
print(reduce(add, l))
print('Reduce took {}'.format(time() - start))

start = time()
print(sum_columns(l))
print('For loop took took {}'.format(time() - start))

Phần kết

Vài ngày sau, bạn tôi đã trở lại với câu hỏi: Làm thế nào để bạn thực hiện hoạt động ngược? I E. Tạo một danh sách các giá trị ASCII số nguyên từ một chuỗi. Ồ không, chúng ta lại đi đây, nó lóe lên trong 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:

from functools import reduce
from numpy import array, arange
from time import time

def add(x, y):
    return x + y

def sum_columns(x):
    if x.any():
        width = len(x[0])
        total = array([0] * width)
    for row in x:
        total += array(row)
    return total

l = arange(3000000)
l = array([l, l, l])

start = time()
print(reduce(add, l))
print('Reduce took {}'.format(time() - start))

start = time()
print(sum_columns(l))
print('For loop took took {}'.format(time() - start))

Và phần nào ít rõ ràng hơn:

from functools import reduce
from numpy import array, arange
from time import time

def add(x, y):
    return x + y

def sum_columns(x):
    if x.any():
        width = len(x[0])
        total = array([0] * width)
    for row in x:
        total += array(row)
    return total

l = arange(3000000)
l = array([l, l, l])

start = time()
print(reduce(add, l))
print('Reduce took {}'.format(time() - start))

start = time()
print(sum_columns(l))
print('For loop took took {}'.format(time() - start))

Thời gian những điều này cho thấy G2 () nhanh gấp khoảng năm lần so với G1 (). Mặc dù vậy, có một tác phẩm: G2 () trả về các 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 cứ điều gì sau xử lý bạn có thể làm trên kết quả từ G2 (). .

Mã mẫu

• thời gian f1 () đến f7 ()
• Thời gian G1 () và G2 ()