Điều gì hiệu quả hơn: Liệt kê <T> .Thêm() hoặc System.Array.Resize()?

Question

Tôi đang cố gắng xác định khi nào hiệu quả hơn đối với List<T>.Add() so với sử dụng phương pháp Array.Resize().

Tài liệu cho Array.Resize cho biết nó tạo bản sao của toàn bộ mảng và đặt nó vào một đối tượng mới. Vật thể cũ sẽ phải bị loại bỏ. Đối tượng cũ này cư trú ở đâu? Trên ngăn xếp hoặc đống?

Tôi không biết cách List.Add() hoạt động.

Có ai biết phương thức List.Add so với phương pháp Array.Resize tĩnh không?

Tôi quan tâm đến việc sử dụng bộ nhớ (và dọn dẹp) và điều gì tốt hơn cho 300 loại giá trị, so với 20.000 loại giá trị.

Đối với những gì đáng giá, tôi đang lên kế hoạch chạy mã này trên một trong các hương vị được nhúng của .NET. Có khả năng là .NET Gadgeteer

Answer 1

Bạn nên sử dụng List<T>.

Sử dụng Array.Resize sẽ buộc bạn phải mở rộng mảng riêng biệt mỗi khi bạn thêm một mục, làm cho mã của bạn nhiều hơn chậm hơn. (vì mảng không thể có dung lượng dự phòng)

A List<T> được hỗ trợ bởi một mảng, nhưng giữ khả năng dự phòng để đưa các mục vào.
Tất cả những gì cần làm để thêm mục là đặt thành phần trong mảng và tăng bộ đếm nội bộ size nội bộ của nó.
Khi mảng đầy, danh sách sẽ tăng gấp đôi dung lượng của nó, cho phép các mục trong tương lai được thêm vào dễ dàng một lần nữa.

Answer 2

.NET Micro Framework không hỗ trợ Generics, vì vậy tôi sẽ sử dụng một mảng, sao chép và phá hủy nó khi cần thiết.

tôi có thể so sánh perfmance đó vào danh sách liên kết trải được đề cập trong powertools thư viện ở đây: Any implementation of an Unrolled Linked List in C#?

Answer 3

.NET Micro Framework không (chưa) Generics hỗ trợ. Bạn bị giới hạn đối với các bộ sưu tập động.

Một điều cần xem xét khi chọn phương pháp tiếp cận của bạn là mã được quản lý trên vi điều khiển rất, rất chậm. Nhiều hoạt động trong các đối tượng .NET Micro Framework được quản lý thực sự chỉ cần gọi vào mã nguồn gốc để thực hiện công việc. Điều này nhanh hơn nhiều. Ví dụ: so sánh sao chép phần tử mảng theo phần tử trong vòng lặp for so với gọi hàm Array.Copy(), bản chất thực hiện tương tự nhưng trong mã gốc.

Nếu có thể, hãy sử dụng các tiện ích mở rộng gốc này để có hiệu suất tốt hơn. Ngoài ra, hãy xem xét xem MicroLinq project trên CodePlex. Có một dự án phụ dành riêng cho các bộ sưu tập nâng cao trên NETMF (cũng có sẵn như là một NuGet package). Mã này có sẵn miễn phí và được cấp phép công khai cho bất kỳ mục đích nào. (Full exposure: Tôi là dev của dự án đó.)

Nếu bạn có thể thoát khỏi việc phân bổ một mảng lớn và theo dõi vị trí tối đa mà dữ liệu thực đã được lưu, đây sẽ là nhanh nhất nhưng yêu cầu nhiều công việc/suy nghĩ đưa vào thiết kế và lấy đi thời gian từ việc xây dựng những thứ tuyệt vời.

Answer 4

Danh sách sẽ chỉ nhanh hơn nếu bạn thay đổi kích thước mảng thường xuyên, ví dụ: mỗi khi bạn thêm một mục. Tuy nhiên, nếu bạn thay đổi kích cỡ mỗi vài khung, Danh sách và các mảng dựng sẵn phải tương đương, có lẽ mảng vẫn nhanh hơn.

Answer 5

Tôi đã xem Danh sách triển khai sau khi giải mã và thấy rằng nó sử dụng Array.Resize() cho mảng nội bộ. Nhưng nó quản lý các yếu tố truy cập và sử dụng chiều dài của mảng như dung lượng và thay đổi kích thước mảng với một số không gian thêm khi bạn gọi Add(). Vì vậy, tôi đoán bạn có thể phát triển chiến lược phân bổ tối ưu hơn Danh sách cho trường hợp của bạn. Nhưng bạn sẽ phải quản lý các yếu tố truy cập theo cách thủ công. Ngoài ra, bạn sẽ loại bỏ các chỉ mục trên không khi truy cập các phần tử mảng, vì các bộ chỉ mục bên trong Danh sách chỉ là các phương thức yêu cầu các phần tử mảng bên trong. Tôi nghĩ rằng nó là giá trị để thay thế Danh sách theo mảng với thay đổi kích thước bằng tay nếu nó là nút cổ chai mà thôi.