Trong khi làm việc trên bài viết của tôi về các bảng băm, tôi đã bắt gặp khái niệm về các mảng/danh sách được thay đổi kích thước động, mà tôi không biết gì về. Tôi muốn viết một bài đăng cụ thể về cách chúng ta có thể thay đổi kích thước mảng hoặc danh sách bởi vì tôi nghĩ rằng các chi tiết rất hữu ích để biết 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 Yasufumi Taniguchis Bài viết xuất sắc đã hướng dẫn bài đăng này [1]. Trước tiên chúng tôi sẽ nói về nơi các mảng và danh sách được thay đổi kích thước động đi vào hoạt độ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 tôi sẽ đi vào một số chi tiết về việc thay đổi kích thước hiệu quả có thể như thế nào.dynamically resized arrays/lists, which I didnt know anything about. I wanted to write a post specifically about how we can resize arrays or lists because I think the details are useful to know when discussing more complex data structures. Many thanks to Yasufumi Taniguchis excellent article for guiding this post [1]. We will first talk about where dynamically resized arrays and lists come into play and some factors to consider when resizing them, then we will get into some of the details of how efficient resizing can be.
Nội phân chính
- Danh sách và mảng được thay đổi kích thước động
- Những yếu tố cần xem xét trong thay đổi kích thước động?
- Độ phức tạp về thời gian của việc thay đổi kích thước mảng và danh sách
- References:
- Video liên Quan
Những yếu tố cần xem xét trong thay đổi kích thước động?
Độ phức tạp về thời gian của việc thay đổi kích thước mảng và danh sách
Video liên Quan
Một số ngôn ngữ lập trình cho phép bạn tạo các 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 các 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 khi bắt đầu và bạn không thể vượt quá khả năng đó một khi trường hợp đó đã được tạo 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 tôi 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 ta nối thêm các yếu tố - danh sách được sao chép vào một danh sách mới, lớn hơn với nhiều chỗ hơn cho các mục 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 này 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].resizing factor k [1-2]. Different languages use different values for k [Python has k = 1.125, Java has k = 2] but in general, k is greater than 1 and so resizing [or reallocation] will create an array that is k times as big as the previous array [1].
Trên thực tế, có một số yếu tố để cân bằng để đảm bảo rằng điều này là đúng - rằng danh sách kích thước động là một cấu trúc hiệu quả [1]. Ví dụ: chúng ta phải quyết định bao nhiêu để mở rộng danh sách bằng cách - nếu chúng ta thêm quá ít bộ nhớ, thì chúng ta sẽ lãng phí thời gian để thực hiện hoạt động 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ẽ không có không gian [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 làm bao nhiêu không gian? Quá ít giảm có nghĩa là sẽ tiếp tục lãng phí bộ nhớ ngay cả sau khi thay đổi kích thước được thực hiện [1]. Quá nhiều việc giảm không gian có nghĩa là sau đó chúng ta sẽ cần thực hiện nhiều lần thay thế tốn kém sau này khi chúng ta thêm các yếu tố trở lại vào danh sách [1].
Độ phức tạp về thời gian của việc thay đổi kích thước mảng và danh sách
Video liên Quan
Một số ngôn ngữ lập trình cho phép bạn tạo các 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 các 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 khi bắt đầu và bạn không thể vượt quá khả năng đó một khi trường hợp đó đã được tạo 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 tôi 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 ta nối thêm các yếu tố - danh sách được sao chép vào một danh sách mới, lớn hơn với nhiều chỗ hơn cho các mục 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 này 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 bằng để đảm bảo rằng điều này là đúng - rằng danh sách kích thước động là một cấu trúc hiệu quả [1]. Ví dụ: chúng ta phải quyết định bao nhiêu để mở rộng danh sách bằng cách - nếu chúng ta thêm quá ít bộ nhớ, thì chúng ta sẽ lãng phí thời gian để thực hiện hoạt động 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ẽ không có không gian [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 làm bao nhiêu không gian? Quá ít giảm có nghĩa là sẽ tiếp tục lãng phí bộ nhớ ngay cả sau khi thay đổi kích thước được thực hiện [1]. Quá nhiều việc giảm không gian có nghĩa là sau đó chúng ta sẽ cần thực hiện nhiều lần thay thế tốn kém sau này khi chúng ta thêm các yếu tố trở lại vào danh sách [1].
Chúng ta có thể mô tả mức độ chúng ta 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 bằng một 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] [1].
Bây giờ chúng ta có một số trực giác cơ bản về cách thay đổi kích thước một danh sách hoặc mảng hoạt động, hãy xem xét các chi tiết cụ thể của việc thực hiện.
Hãy nói rằng chúng tôi có một danh sách có yếu tố thay đổi kích thước k = 2 - nghĩa là mỗi khi chúng tôi thay đổi kích thước danh sách, nó có thể tăng gấp đôi hoặc một nửa kích thước [tùy thuộc vào việc chúng tôi đang nối thêm hoặc loại bỏ các yếu tố]. Hãy nhớ rằng mỗi lần chúng tôi thay đổi kích thước của danh sách, chúng tôi phải sao chép nó vào một danh sách mới và thời gian O [1] cần sao chép một yếu tố. Vì vậy, hãy xem những gì xảy ra khi chúng ta thêm các mục vào danh sách bắt đầu dưới dạng kích thước 2, với một phần tử có trong đó [1]:
Hình 1 - Nguồn [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, thời gian O [n] trong đó n là số lượng 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]:
Phương trình 1
Về cơ bản, chúng ta có thể bỏ qua các thuật ngữ 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 một danh sách hoặc mảng là o [n] [1-2].
Bây giờ hãy thêm tổng số bản sao mà chúng tôi phải tạo để chèn n phần tử vào danh sách [2]:
Phương trình 2
Tại sao tổng ít hơn n? Laakmann McDowell đề nghị nghĩ về nó là khoảng cách bạn cần đi bộ từ nhà đến cửa hàng tạp hóa. Nếu bạn đi bộ một nửa khoảng cách đó, và sau đó một nửa khoảng cách còn lại, và sau đó một nửa, bạn sẽ gần như, nhưng không bao giờ hoàn toàn đến được cửa hàng tạp hóa [tức là 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ố phần chèn vào danh sách mất thời gian O [n], 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 khấu hao chi phí cho nhiều hoạt động thay đổi kích thước [2]. Thời gian chạy trường hợp xấu nhất là O [n] [2].
Tôi hy vọng rằng lời giải thích là hữu ích. Đây là điều cần xem xét 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 thay đổi kích thước động, bởi vì thay đổi kích thước có thể mất thời gian đáng kể, như chúng ta đã thấy ở đây.
References:
[1] Taniguchi, Y. Những gì bạn nên biết về danh sách Python. Vừa phải. 14 tháng 1 năm 2019. //medium.com/@yasufumy/data-structure-dynamic-array-3370cd70888 đã ghé thăm ngày 16 tháng 1 năm 2021.
[2] Laakmann McDowell, G. Cracking Cuộc phỏng vấn mã hóa, Phiên bản thứ 6. 2016. CareerCup, LLC.