Hướng dẫn time complexity of str in python - độ phức tạp về thời gian của str trong python

Tôi luôn luôn kết hợp các chuỗi bằng cách sử dụng nhà điều hành++không phân biệt ngôn ngữ mà tôi mã chỉ để nhận ra sau đó rằng tôi đã làm sai chúng. Để chính xác, không hiệu quả.

Hôm nay, chúng ta sẽ thảo luận về sự kết hợp chuỗi trong Python và cách thực hiện nó một cách hiệu quả.

Một sự kết hợp đơn giản:

x =  "hello"
y =  "world"
print(x + y)

Output:
helloworld

Như chúng ta nhận thức được thực tế rằng các đối tượng chuỗi là bất biến trong Python, bất kỳ hoạt động nối nào sử dụng toán tử+++có thể chứng minh là tốn kém.

Tại sao nó như vậy?

Các đối tượng chuỗi là bất biến trong Python và bất kỳ thao tác nối nào cũng tạo ra một chuỗi mới, sao chép ký tự chuỗi cũ theo ký tự và sau đó nối dây chuỗi mới được nối.

Để rõ ràng, hãy để tôi giải thích với một ví dụ:

    def concat_strings():
        """
        This is a program to remove spaces in a string
        :return:
        """

        *input_string = "Th is is an ex am pl ew it hs pa ce"

        output_string = ""

        for i in input_string:
            if i == " ":
                pass
            else:
                output_string += i

        print(output_string)


    concat_strings()

    Output:
    Thisisanexamplewithspace

Chương trình này loại bỏ các không gian trắng trong một chuỗi và in chuỗi mới mà không có khoảng trắng. Điều này lặp lại thông qua ký tự Input_String theo ký tự và kết hợp với một chuỗi mới có tên Output_String trong khi bỏ qua các không gian trắng.

Mặc dù điều này hoàn thành công việc, điều này không hiệu quả lắm, phải không?

Lý do cho điều này là, trên mỗi hoạt động của++, một chuỗi mới được tạo ra (hãy nhớ các chuỗi là bất biến?) Mỗi ​​lần và các giá trị hiện có phải được sao chép ký tự theo ký tự.

Độ phức tạp của thời gian của hoạt động này là O (N²). Chờ đợi… làm thế nào?

Kết nối bằng cách sử dụng toán tử + dưới mui xe:

Để có được một ý tưởng cơ bản về sự phức tạp về thời gian và sự phức tạp không gian, vui lòng tham khảo bài viết này.

Hãy hướng dẫn việc lặp lại chương trình ví dụ bằng cách lặp.

Trong Lặp lại 1, một đối tượng chuỗi mới được tạo và ký tự là T Tiên được sao chép vào Output_String. Vì vậy, chuỗi mới của chúng tôi hiện có 1 ký tự.

Trong Lặp lại 2, một lần nữa, một chuỗi mới được tạo và lần này, Tiên được sao chép. Thêm vào đó, thì H Hv còn được thêm vào. Điều này tiếp tục cho mỗi lần lặp. (Tôi đã bỏ qua việc lặp lại cho không gian để đơn giản).

Vì vậy, những gì chúng ta quan sát ở đây?

Đối với mỗi lần ghép, số lượng ký tự được sao chép tăng bậc hai.

Iteration 1:
1 character (“T”) = 1

Iteration 2:
2 characters(“T”, “h”) = 1+1

Iteration 3:
3 characters(“T”, “h”, “i”) = 1+1+1

Iteration 4:
4 characters(“T”, “h”, “i”, ”s”) = 1+1+1+1

và như vậy cho đến khi chiều dài của chuỗi.

Nếu chúng ta quan sát mẫu, số lượng bản sao trong quá trình ghép là 1 (không có ký tự) + 2 (số lượng ký tự) + 3 (số lượng ký tự) +, .. + (n).

Điều này đưa chúng ta đến tổng n số tự nhiên là n (n+1)/2 sẽ cung cấp cho chúng ta o (xn²), trong đó x = số lượng ký tự. Vì số lượng ký tự cho mỗi lần ghép luôn không đổi ở đây (1 trong trường hợp này), chúng tôi có thể bỏ hệ số không đổi mang lại cho chúng tôi O (N²).

Điều tương tự cũng áp dụng cho sự kết hợp của các chuỗi có chiều dài khác nhau là tốt. Đối với sự kết hợp của các chuỗi có độ dài khác nhau, nó phải là O (N + M) trong đó N và M là độ dài của hai chuỗi được nối. Tuy nhiên, hành vi vẫn sẽ là bậc hai dựa trên độ dài của các chuỗi do sự kết hợp lặp đi lặp lại.

Vì vậy, để tóm tắt, các chuỗi nối với + là một hoạt động tốn kém, đặc biệt là nếu chuỗi được nối là dài.

Từ các tài liệu Python:

Các chuỗi bất biến luôn luôn dẫn đến một đối tượng mới. Điều này có nghĩa là việc xây dựng một chuỗi bằng cách kết hợp lặp đi lặp lại sẽ có chi phí thời gian chạy bậc hai trong tổng chiều dài trình tự.

Làm thế nào để chúng ta vượt qua điều này?

Chà, tốt hơn hết là sử dụng danh sách để lưu trữ tất cả các chuỗi được nối và tham gia chúng bằng phương thức str.join ().

str.join () lấy một điều có thể đi được là một đối số và trả về một chuỗi là một sự kết hợp của tất cả các đối tượng chuỗi trong ITBELBELBE.

def concat_strings():
    *"""
    This is a program to remove spaces in a string
    **:return**:
    """

    *input_string = "Th is is an ex am pl ew it hs pa ce"

    output_lst = list()

    for i in input_string:
        if i == " ":
            pass
        else:
            output_lst.append(i)

    print("".join(output_lst))

Output:

Thisisanexamplewithspace

Ở đây, chúng tôi đã sửa đổi ví dụ trước đây của chúng tôi để lưu trữ mỗi chuỗi vào một danh sách và cuối cùng tham gia cùng họ. Xin lưu ý rằng việc nối vào danh sách luôn luôn là O (1). Vì vậy, điều đó không ảnh hưởng đến thời gian chạy của chương trình.

Đây là một cách hiệu quả hơn để kết hợp các chuỗi thay vì sử dụng một loại++. Độ phức tạp về thời gian của việc sử dụng Jop () cho các chuỗi là O (n) trong đó n là độ dài của chuỗi được nối.

Phải nói rằng, sự khác biệt trong thời gian thực hiện sẽ chỉ có ý nghĩa nếu các chuỗi được nối là dài. Đối với các chuỗi nhỏ hơn, chúng ta có thể không thấy một sự khác biệt lớn.

• https://docs.python.org/3/library/stdtypes.html#str.join

• https://docs.python.org/3/library/stdtypes.html

Lưu ý: Ví dụ thứ hai cũng có thể được viết dưới dạng một lớp lót như được chỉ ra trong các bình luận. Điều này có thể làm giảm thêm số lượng dòng mã. Tuy nhiên, thời gian chạy vẫn sẽ vẫn giống như độ phức tạp thời gian của Split là O (N).

def concat_strings():
    *"""
    This is a program to remove spaces in a string
    **:return**:
    """

    *input_string = "Th is is an ex am pl ew it hs pa ce"

    print("".join(input_string.split()))

Output:

Thisisanexamplewithspace

Summary:

• Các chuỗi nối bằng cách sử dụng + không hiệu quả.

• Độ phức tạp của thời gian của sự kết hợp chuỗi bằng cách sử dụng + là o (n²)

• Luôn luôn tốt hơn để tận dụng str.join () để nối dây

• str.join () thực hiện trong thời gian O (n).