Cách nối không có dấu cách Python

Tôi luôn sử dụng để nối các chuỗi bằng toán tử “+” bất kể ngôn ngữ mà tôi mã hóa chỉ để sau này nhận ra rằng tôi đã làm sai. Chính xác là không hiệu quả

Hôm nay, chúng ta sẽ thảo luận về nối chuỗi trong python và cách thực hiện hiệu quả

Nối đơn giản

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

Output:
helloworld

Như chúng ta đã biết thực tế là các đối tượng chuỗi là bất biến trong python, bất kỳ thao tác nối nào sử dụng toán tử “+” đều có thể gây 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 thêm 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 khoảng trắng trong một chuỗi và in chuỗi mới không có khoảng trắng. Điều này lặp qua từng ký tự input_string và nối thành một chuỗi mới có tên là output_string trong khi bỏ qua các khoảng trắng

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

Lý do cho điều này là, trên mỗi thao tác “+”, một chuỗi mới được tạo (Bạn có nhớ chuỗi là bất biến không?) mỗi lần và các giá trị hiện có phải được sao chép từng ký tự

Độ phức tạp về thời gian của thao tác này là O(n²). Chờ đã…làm thế nào?

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

Để có được ý tưởng cơ bản về độ phức tạp thời gian và độ 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 lặp lại chương trình ví dụ bằng cách lặp lại

Trong lần lặp 1, một đối tượng chuỗi mới được tạo và ký tự “T” được sao chép vào output_string. Vì vậy, chuỗi mới của chúng tôi bây giờ có 1 ký tự

Trong lần lặp lại 2, một chuỗi mới lại được tạo và lần này, “T” được sao chép. Thêm vào đó, “h” được thêm vào. Điều này diễn ra cho mỗi lần lặp lại. (Tôi đã bỏ qua bước lặp cho khoảng trắng để đơn giản)

Vì vậy, mô hình nào chúng ta quan sát ở đây?

Đối với mỗi lần nối, số ký tự được sao chép tăng theo phương trình 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à cứ như vậy cho đến hết 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 nối là 1(số ký tự) + 2(số ký tự) + 3(số ký tự) + …. + (n)

Điều này đưa chúng ta đến tổng của n số tự nhiên là n(n+1)/2 sẽ cho chúng ta O(xn²), trong đó x = số ký tự. Vì số lượng ký tự cho mỗi lần nối 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 việc nối các chuỗi có độ dài khác nhau. Để nối 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 chuỗi do nối lặp lại

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

Từ các tài liệu python

Nối các chuỗi bất biế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 nối lặp lại sẽ có chi phí thời gian chạy bậc hai trong tổng chiều dài chuỗi

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 một danh sách để lưu trữ tất cả các chuỗi được nối và nối chúng bằng lệnh str. phương thức tham gia ()

str. join() lấy một iterable làm đối số và trả về một chuỗi là phép nối của tất cả các đối tượng chuỗi trong iterable

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 của mình để lưu trữ mọi chuỗi vào danh sách và cuối cùng nối chúng. Xin lưu ý rằng việc thêm vào danh sách luôn là O(1). Vì vậy, điều đó sẽ 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 để nối các chuỗi thay vì sử dụng dấu “+”. Độ phức tạp về thời gian của việc sử dụng phép nối () 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 về thời gian thực hiện sẽ chỉ đáng kể nếu các chuỗi được nối dài. Đối với các chuỗi nhỏ hơn, chúng ta có thể không thấy sự khác biệt lớn

• https. // tài liệu. con trăn. org/3/library/stdtypes. html#str. tham gia

• https. // tài liệu. con trăn. org/3/library/stdtypes. html

Ghi chú. 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 nhận xét. Đ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 sẽ vẫn giữ nguyên do độ phức tạp thời gian của quá trình phân tách là O(n)