Hướng dẫn python list dynamic array - danh sách mảng động python

Trong khoa học máy tính, một mảng động, mảng có thể phát triển, mảng có thể thay đổi, bảng động, mảng có thể thay đổi hoặc danh sách mảng là một truy cập ngẫu nhiên, cấu trúc dữ liệu danh sách kích thước thay đổi cho phép các yếu tố được thêm hoặc loại bỏ. Nó được cung cấp với các thư viện tiêu chuẩn trong nhiều ngôn ngữ lập trình chính hiện đại. Các mảng động khắc phục giới hạn các mảng tĩnh, có khả năng cố định cần được chỉ định khi phân bổ.dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream programming languages. Dynamic arrays overcome a limit of static arrays, which have a fixed capacity that needs to be specified at allocation.

Một số giá trị được chèn vào cuối một mảng động bằng cách sử dụng mở rộng hình học. Các tế bào màu xám cho thấy không gian dành riêng cho việc mở rộng. Hầu hết các chèn là nhanh (thời gian không đổi), trong khi một số người chậm do nhu cầu phân bổ lại (θ (n) thời gian, được dán nhãn với rùa). Kích thước logic và công suất của mảng cuối cùng được hiển thị.

Một mảng động không giống như một mảng được phân bổ động, đó là một mảng có kích thước được cố định khi mảng được phân bổ, mặc dù một mảng động có thể sử dụng một mảng có kích thước cố định như một đầu sau. [1]

Một mảng động đơn giản có thể được xây dựng bằng cách phân bổ một mảng có kích thước cố định, thường lớn hơn số lượng các phần tử cần thiết ngay lập tức. Các yếu tố của mảng động được lưu trữ liên tục khi bắt đầu mảng bên dưới và các vị trí còn lại vào cuối mảng bên dưới được bảo lưu hoặc không sử dụng. Các phần tử có thể được thêm vào cuối một mảng động trong thời gian không đổi bằng cách sử dụng không gian dành riêng, cho đến khi không gian này được tiêu thụ hoàn toàn. Khi tất cả không gian được tiêu thụ và một yếu tố bổ sung sẽ được thêm vào, thì mảng kích thước cố định cơ bản cần được tăng lên về kích thước. Thông thường thay đổi kích thước là đắt tiền vì nó liên quan đến việc phân bổ một mảng cơ bản mới và sao chép từng phần tử từ mảng gốc. Các phần tử có thể được loại bỏ từ cuối một mảng động trong thời gian không đổi, vì không cần thay đổi kích thước. Số lượng các phần tử được sử dụng bởi nội dung mảng động là kích thước hoặc kích thước logic của nó, trong khi kích thước của mảng cơ bản được gọi là dung lượng hoặc kích thước vật lý của mảng động, là kích thước tối đa có thể mà không cần di dời dữ liệu. [2]

Một mảng có kích thước cố định sẽ đủ trong các ứng dụng trong đó kích thước logic tối đa được cố định (ví dụ: theo thông số kỹ thuật) hoặc có thể được tính toán trước khi mảng được phân bổ. Một mảng động có thể được ưa thích nếu:

• Kích thước logic tối đa chưa được biết hoặc khó tính toán, trước khi mảng được phân bổ
• Nó được coi là một kích thước logic tối đa được đưa ra bởi một đặc điểm kỹ thuật có khả năng thay đổi
• Chi phí khấu hao để thay đổi kích thước một mảng động không ảnh hưởng đáng kể đến hiệu suất hoặc khả năng đáp ứng

Để tránh phát sinh chi phí thay đổi kích thước nhiều lần, các mảng động thay đổi kích thước bằng một lượng lớn, chẳng hạn như tăng gấp đôi kích thước và sử dụng không gian dành riêng để mở rộng trong tương lai. Hoạt động của việc thêm một phần tử vào phần cuối có thể hoạt động như sau:

Chức năng chèn (dynarray A, phần tử e) if (a.size == a.capacity) // Thay đổi kích thước A thành hai lần dung lượng hiện tại của nó: A.Capacity A.Capacity * 2 // (sao chép nội dung vào vị trí bộ nhớ mới tại đây ) A [a.size] e a.size a.size + 1

Khi các yếu tố N được chèn vào, năng lực tạo thành một tiến trình hình học. Mở rộng mảng theo bất kỳ tỷ lệ không đổi nào A đảm bảo rằng việc chèn n phần tử mất thời gian o (n) tổng thể, có nghĩa là mỗi lần chèn mất thời gian không đổi. Nhiều mảng động cũng phân phối một số lưu trữ cơ bản nếu kích thước của nó giảm xuống dưới một ngưỡng nhất định, chẳng hạn như 30% công suất. Ngưỡng này phải hoàn toàn nhỏ hơn 1/a để cung cấp độ trễ (cung cấp một dải ổn định để tránh tăng trưởng và thu hẹp nhiều lần) và hỗ trợ các chuỗi chèn và loại bỏ hỗn hợp với chi phí không đổi được khấu hao.

Mảng động là một ví dụ phổ biến khi giảng dạy phân tích khấu hao. [3] [4]

Yếu tố tăng trưởng cho mảng động phụ thuộc vào một số yếu tố bao gồm sự đánh đổi không gian thời gian và thuật toán được sử dụng trong chính bộ phân phối bộ nhớ. Đối với yếu tố tăng trưởng A, thời gian trung bình trên mỗi hoạt động chèn là khoảng a/(a1), trong khi số lượng tế bào lãng phí được giới hạn ở trên bởi (a1) n [cần có trích dẫn]. Nếu bộ phân bổ bộ nhớ sử dụng thuật toán phân bổ phù hợp đầu tiên, thì các giá trị yếu tố tăng trưởng như a = 2 có thể khiến mở rộng mảng động để hết bộ nhớ mặc dù có thể có một lượng bộ nhớ đáng kể. [5] Đã có nhiều cuộc thảo luận về các giá trị yếu tố tăng trưởng lý tưởng, bao gồm các đề xuất cho tỷ lệ vàng cũng như giá trị 1.5. [6] Tuy nhiên, nhiều sách giáo khoa sử dụng A = 2 cho mục đích đơn giản và phân tích. [3] [4]

Dưới đây là các yếu tố tăng trưởng được sử dụng bởi một số triển khai phổ biến:

Mảng động có hiệu suất tương tự như một mảng, với việc bổ sung các hoạt động mới để thêm và xóa các phần tử:

• Nhận hoặc đặt giá trị tại một chỉ mục cụ thể (thời gian không đổi)
• Lặp lại các yếu tố theo thứ tự (thời gian tuyến tính, hiệu suất bộ đệm tốt)
• Chèn hoặc xóa một phần tử ở giữa mảng (thời gian tuyến tính)
• Chèn hoặc xóa một phần tử ở cuối mảng (thời gian khấu hao không đổi)

Các mảng động được hưởng lợi từ nhiều lợi thế của các mảng, bao gồm địa phương tốt của việc sử dụng bộ đệm dữ liệu và tham chiếu tốt, độ nén (sử dụng bộ nhớ thấp) và truy cập ngẫu nhiên. Họ thường chỉ có một chi phí bổ sung cố định nhỏ để lưu trữ thông tin về kích thước và công suất. Điều này làm cho các mảng động trở thành một công cụ hấp dẫn để xây dựng các cấu trúc dữ liệu thân thiện với bộ đệm. Tuy nhiên, trong các ngôn ngữ như Python hoặc Java thực thi ngữ nghĩa tham chiếu, mảng động thường sẽ không lưu trữ dữ liệu thực tế, mà là nó sẽ lưu trữ các tham chiếu đến dữ liệu nằm trong các lĩnh vực bộ nhớ khác. Trong trường hợp này, việc truy cập các mục trong mảng tuần tự sẽ thực sự liên quan đến việc truy cập vào nhiều khu vực không liên tục của bộ nhớ, do đó, nhiều lợi thế của sự thân thiện với bộ đệm của cấu trúc dữ liệu này bị mất.

So với các danh sách được liên kết, các mảng động có lập chỉ mục nhanh hơn (thời gian không đổi so với thời gian tuyến tính) và thường lặp nhanh hơn do địa phương được cải thiện tham chiếu; Tuy nhiên, các mảng động yêu cầu thời gian tuyến tính để chèn hoặc xóa tại một vị trí tùy ý, vì tất cả các yếu tố sau phải được di chuyển, trong khi các danh sách được liên kết có thể thực hiện điều này trong thời gian không đổi. Nhược điểm này được giảm thiểu bởi bộ đệm khoảng cách và các biến thể vectơ theo tầng được thảo luận trong các biến thể dưới đây. Ngoài ra, trong một vùng bộ nhớ phân mảnh cao, có thể tốn kém hoặc không thể tìm thấy không gian tiếp giáp cho một mảng động lớn, trong khi các danh sách được liên kết không yêu cầu toàn bộ cấu trúc dữ liệu được lưu trữ một cách tiếp tục.

Một cây cân bằng có thể lưu trữ một danh sách trong khi cung cấp tất cả các hoạt động của cả hai mảng động và danh sách được liên kết hiệu quả một cách hợp lý, nhưng cả hai lần chèn ở cuối và lặp qua danh sách chậm hơn so với một mảng động, trên lý thuyết và trong thực tế, do không phải do không Lưu trữ liền kề và truyền tải/thao tác trên cây.

Bộ đệm khoảng cách tương tự như các mảng động nhưng cho phép các hoạt động chèn và xóa hiệu quả được phân cụm gần cùng một vị trí tùy ý. Một số triển khai deque sử dụng các deques mảng, cho phép chèn/loại bỏ thời gian không đổi ở cả hai đầu, thay vì chỉ một đầu.

Goodrich [16] đã trình bày một thuật toán mảng động được gọi là các vectơ cấp cung cấp hiệu suất O (N1/K) để chèn và xóa từ bất cứ đâu trong mảng và O (k) GET và SET, trong đó K 2 là một tham số không đổi.

Cây mảng băm (HAT) là một thuật toán mảng động được xuất bản bởi Sitarski vào năm 1996. [17] Cây mảng băm lãng phí thứ tự đặt hàng N1/2 dung lượng lưu trữ, trong đó n là số lượng các phần tử trong mảng. Thuật toán có hiệu suất được khấu hao O (1) khi nối một loạt các đối tượng vào cuối cây mảng băm.

Trong một bài báo năm 1999, [18] Brodnik et al. Mô tả một cấu trúc dữ liệu mảng động được xếp theo cấp, chỉ lãng phí không gian N1/2 cho các phần tử N tại bất kỳ thời điểm nào và chúng chứng minh một giới hạn dưới cho thấy rằng bất kỳ mảng động nào cũng phải lãng phí nhiều không gian này nếu các hoạt động duy trì thời gian được khấu hao. Ngoài ra, họ trình bày một biến thể trong đó phát triển và thu hẹp bộ đệm không chỉ được khấu hao mà còn là thời gian không đổi trong trường hợp xấu nhất.

Bagwell (2002) [19] đã trình bày thuật toán VList, có thể được điều chỉnh để thực hiện một mảng động.

STD :: Vector và Rust's Std :: VEC :: VEC là việc triển khai các mảng động, cũng như các lớp ArrayList [20] được cung cấp với API Java và khung .NET. [21]

Lớp danh sách chung được cung cấp với phiên bản 2.0 của .NET Framework cũng được triển khai với các mảng động. Lệnh của SmallTalk là một mảng động với chỉ số khởi động và chỉ số cuối động, làm cho việc loại bỏ phần tử đầu tiên O (1).

Việc thực hiện danh sách Danh sách Danh sách của Python là một mảng động, mô hình tăng trưởng của nó là: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... [22]

Delphi và D thực hiện các mảng động ở cốt lõi của ngôn ngữ.

ADA của ADA.Containers.vector Gói chung Gói chung cung cấp triển khai mảng động cho một kiểu con nhất định.

Nhiều ngôn ngữ kịch bản như Perl và Ruby cung cấp các mảng động như một loại dữ liệu nguyên thủy tích hợp.

Một số khung đa nền tảng cung cấp các triển khai mảng động cho C, bao gồm CFarray và CfMutableArray trong Core Foundation, và Garray và GPtrarray trong GLIB.

Lisp thông thường cung cấp một hỗ trợ thô sơ cho các vectơ có thể thay đổi được bằng cách cho phép định cấu hình loại mảng tích hợp dưới dạng có thể điều chỉnh và vị trí chèn bằng con trỏ điền.