Liệt kê dung lượng trong python

Trong khi làm việc với bài đăng của mình về bảng băm, tôi đã bắt gặp khái niệm về mảng/danh sách được thay đổi kích thước động, mà tôi không biết gì về nó. Tôi muốn viết một bài cụ thể về cách chúng ta có thể thay đổi kích thước mảng hoặc danh sách vì tôi nghĩ rằng các chi tiết hữu ích khi thảo luận về các cấu trúc dữ liệu phức tạp hơn. Rất cám ơn bài viết tuyệt vời của Yasufumi Taniguchi đã hướng dẫn bài viết này [1]. Trước tiên, chúng ta sẽ nói về vị trí các mảng và danh sách được thay đổi kích thước động phát huy tác dụng và một số yếu tố cần xem xét khi thay đổi kích thước chúng, sau đó chúng ta sẽ tìm hiểu một số chi tiết về mức độ hiệu quả của việc thay đổi kích thước

Nội dung chính Hiển thị

Những yếu tố cần xem xét trong thay đổi kích thước động?

Một số ngôn ngữ lập trình cho phép bạn tạo cấu trúc dữ liệu như danh sách và mảng sẽ tự động phát triển khi bạn thêm mục [2]. [Tuy nhiên, đôi khi bạn phải khai báo kích thước của cấu trúc ngay từ đầu và bạn không thể vượt quá dung lượng đó sau khi phiên bản đó đã được tạo [2]. ] Ví dụ: nếu chúng ta tạo một danh sách bằng Python, chúng ta có thể liên tục thêm hoặc xóa các mục khỏi danh sách mà không quản lý rõ ràng kích thước của danh sách - Python sẽ làm điều đó cho chúng ta trong nền [1]. Thay đổi kích thước đơn giản có nghĩa là khi danh sách thay đổi kích thước - ví dụ: khi chúng tôi nối thêm nhiều phần tử hơn - danh sách được sao chép sang một danh sách mới, lớn hơn với nhiều chỗ hơn cho các mục nhập bổ sung [1]

Một cách tiếp cận điển hình để thay đổi kích thước là tăng gấp đôi kích thước của danh sách sau khi danh sách đầy [2]. Việc nhân đôi danh sách có thể mất thời gian và không gian bổ sung, nhưng ý tưởng là nó xảy ra không thường xuyên đủ để danh sách vẫn là một cấu trúc dữ liệu khá hiệu quả [cả về thời gian và không gian] [2]

Trên thực tế, có một số yếu tố cần cân bằng để đảm bảo rằng điều này là đúng - rằng danh sách được thay đổi kích thước động là một cấu trúc hiệu quả [1]. Ví dụ: chúng tôi phải quyết định mở rộng danh sách bao nhiêu - nếu chúng tôi thêm quá ít bộ nhớ, thì chúng tôi sẽ lãng phí thời gian vào việc thực hiện thao tác thay đổi kích thước quá thường xuyên [1]. Nếu chúng ta thêm quá nhiều bộ nhớ, thì chúng ta sẽ sử dụng không gian không hiệu quả [1]. Tương tự, khi chúng ta cần giảm kích thước của danh sách, chúng ta nên giảm bao nhiêu khoảng trống? . Giảm quá nhiều không gian có nghĩa là sau đó chúng tôi sẽ cần thực hiện nhiều thay đổi kích thước tốn kém sau này khi chúng tôi thêm lại các phần tử vào danh sách [1]

Chúng tôi có thể mô tả mức độ chúng tôi tăng hoặc giảm kích thước của danh sách với mỗi lần thay đổi kích thước động theo hệ số thay đổi kích thước k [1-2]. Các ngôn ngữ khác nhau sử dụng các giá trị khác nhau cho k [Python có k = 1. 125, Java có k = 2] nhưng nói chung, k lớn hơn 1 và do đó thay đổi kích thước [hoặc phân bổ lại] sẽ tạo ra một mảng lớn gấp k lần mảng trước đó [1]

Bây giờ chúng ta đã có một số trực giác cơ bản về cách hoạt động của việc thay đổi kích thước danh sách hoặc mảng, hãy xem xét các chi tiết cụ thể của quá trình triển khai

Độ phức tạp về thời gian của việc thay đổi kích thước mảng và danh sách

Giả sử rằng chúng ta có một danh sách có hệ số thay đổi kích thước k = 2 - nghĩa là, mỗi khi chúng ta thay đổi kích thước danh sách, nó sẽ tăng gấp đôi hoặc giảm một nửa kích thước [tùy thuộc vào việc chúng ta đang thêm hay xóa phần tử]. Hãy nhớ rằng mỗi khi chúng ta thay đổi kích thước của danh sách, chúng ta phải sao chép nó sang một danh sách mới và phải mất O[1] thời gian để sao chép một phần tử. Vì vậy, hãy xem điều gì sẽ xảy ra khi chúng tôi thêm các mục vào danh sách bắt đầu bằng kích thước 2, với một phần tử được chứa trong đó [1]

Như bạn có thể thấy trong Hình 1, chúng ta phải sao chép danh sách nhiều lần khi chúng ta tiếp tục thêm các phần tử vào nó [1]. Mỗi lần chúng tôi sao chép, phải mất O[n] thời gian trong đó n là số mục trong danh sách. Tổng cộng, chúng ta có thể viết độ phức tạp về thời gian của việc thêm n mục là [1]

Về cơ bản, chúng ta có thể bỏ qua các điều khoản không đổi và giảm điều này để thấy rằng độ phức tạp về thời gian của việc thay đổi kích thước danh sách hoặc mảng là O[n] [1-2]

Nhưng thời gian chạy khấu hao của việc thay đổi kích thước danh sách chỉ là O[1] [2]. Tại sao vậy? . Chúng ta sẽ giả sử rằng k = 2 để nếu danh sách có kích thước x, thì trước khi thay đổi kích thước, nó có kích thước x/2 và do đó, các phần tử x/2 phải được sao chép sang danh sách mới có kích thước x [2]

Tăng công suất cuối cùng. Đã sao chép N/2 phần tử

Lần tăng công suất trước. Đã sao chép N/4 phần tử

Lần tăng công suất trước. Đã sao chép N/8 phần tử

Tăng công suất lần thứ hai. Đã sao chép 2 yếu tố

Tăng công suất đầu tiên. Đã sao chép 1 phần tử

Bây giờ, hãy cộng tổng số bản sao mà chúng ta phải thực hiện để chèn N phần tử vào danh sách [2]

Tại sao tổng nhỏ hơn N? . Nếu bạn đi một nửa quãng đường đó, rồi một nửa quãng đường còn lại, rồi lại một nửa, bạn sẽ gần như không bao giờ đến được cửa hàng tạp hóa [i. e. bạn sẽ gần như, nhưng không bao giờ hoàn toàn đạt được N] [2]. Vì vậy, tổng số lần chèn vào danh sách mất O[n] thời gian, mặc dù nói chung, việc chèn có thể được thực hiện trong thời gian không đổi vì chúng tôi đang phân bổ chi phí cho nhiều thao tác thay đổi kích thước [2]. Thời gian chạy trong trường hợp xấu nhất là O[n] [2]

Tôi hy vọng lời giải thích đó hữu ích. Đây là điều cần cân nhắc khi tạo các cấu trúc dữ liệu phức tạp hơn sẽ dựa vào danh sách hoặc mảng tự động thay đổi kích thước, vì việc thay đổi kích thước có thể mất nhiều thời gian, như chúng ta đã thấy ở đây

Người giới thiệu

[1] Taniguchi, Y. Những điều bạn nên biết về Danh sách Python. Trung bình. 14 Thg 1 2019. https. //Trung bình. com/@yasufumy/data-structure-dynamic-array-3370cd7088ec Đã truy cập vào ngày 16 tháng 1 năm 2021