mặc định Loại bộ sưu tập

Question

Giả sử bạn cần lưu trữ/truy xuất các mục trong một Collection, không quan tâm đến việc đặt hàng và các bản sao được cho phép, loại Collection để bạn sử dụng?

Theo mặc định, tôi đã luôn sử dụng ArrayList, nhưng tôi nhớ đọc/nghe ở đâu đó rằng việc triển khai Queue có thể là lựa chọn tốt hơn. A List cho phép các mục được thêm/lấy/xóa tại các vị trí tùy ý, phát sinh hình phạt. Là một Queue không cung cấp cơ sở này, nó nên trong lý thuyết được nhanh hơn khi cơ sở này là không cần thiết.

Tôi nhận thấy rằng tất cả các cuộc thảo luận về hiệu suất có phần vô nghĩa, điều duy nhất thực sự quan trọng là đo lường. Tuy nhiên, tôi quan tâm để biết những gì người khác sử dụng cho một Collection, khi họ không quan tâm đến việc đặt hàng, và các bản sao được cho phép, và tại sao?

Answer 1

Theo mặc định, tôi có xu hướng thích LinkedList đến ArrayList. Rõ ràng, tôi sử dụng chúng không thông qua giao diện List, mà là thông qua giao diện Collection.

Theo thời gian, tôi đã thực sự phát hiện ra rằng khi tôi cần một bộ sưu tập chung chung, nó ít nhiều để đưa một số thứ vào, sau đó lặp lại nó. Nếu tôi cần hành vi tiến hóa hơn (nói truy cập ngẫu nhiên, phân loại hoặc kiểm tra tính duy nhất), thì tôi có thể thay đổi việc triển khai đã sử dụng, nhưng trước đó tôi sẽ thay đổi giao diện được sử dụng cho phù hợp nhất. Bằng cách này, tôi có thể đảm bảo tính năng được cung cấp trước khi tập trung vào tối ưu hóa và triển khai.

Answer 2

ArrayList cơ bản chứa một mảng bên trong (đó là lý do tại sao nó được gọi là ArrayList). Và các hoạt động như addd/remove tại các vị trí tùy ý được thực hiện một cách đơn giản, vì vậy nếu bạn không sử dụng chúng - không có hại cho hiệu suất.

Answer 3

Nếu đặt hàng và bản sao không phải là một vấn đề và trường hợp chỉ để lưu trữ,

tôi sử dụng ArrayList, Vì nó thực hiện tất cả các hoạt động danh sách. Không bao giờ cảm thấy bất kỳ vấn đề hiệu suất với các hoạt động này (Không bao giờ ảnh hưởng đến các dự án của tôi). Trên thực tế sử dụng các hoạt động này có cách sử dụng đơn giản & Tôi không cần quan tâm đến cách thức quản lý nội bộ của nó.

Chỉ khi nhiều chủ đề sẽ truy cập danh sách này, tôi sử dụng Vector vì phương pháp của nó được đồng bộ hóa.

Ngoài ra ArrayList và Vector là các bộ sưu tập mà bạn tìm hiểu trước :).

Answer 4

"Nó phụ thuộc". Câu hỏi bạn thực sự cần trả lời đầu tiên là "Tôi muốn sử dụng bộ sưu tập để làm gì?"

Nếu bạn thường chèn/xóa các mục trên một trong các đầu (bắt đầu, kết thúc), Queue sẽ tốt hơn ArrayList. Tuy nhiên, trong nhiều trường hợp, bạn tạo một Bộ sưu tập để chỉ đọc từ đó. Trong trường hợp này, ArrayList hiệu quả hơn nhiều: Vì nó được thực hiện như một mảng, bạn có thể lặp lại nó khá hiệu quả (tương tự áp dụng cho một LinkedList). Tuy nhiên, LinkedList sử dụng các tham chiếu để liên kết các mục đơn lẻ với nhau. Vì vậy, nếu bạn không cần loại bỏ ngẫu nhiên các mục (ở giữa), ArrayList là tốt hơn: An ArrayList sẽ sử dụng ít bộ nhớ hơn vì các mục không cần bộ nhớ để tham chiếu đến mục tiếp theo/trước.

Nói tóm lại:

ArrayList = tốt nếu bạn chèn một lần và đọc thường xuyên (truy cập ngẫu nhiên hoặc tuần tự)

LinkedList = tốt nếu bạn chèn/xóa thường tại các vị trí ngẫu nhiên và chỉ đọc tuần tự

ArrayDeque (chỉ java6) = tốt nếu bạn chèn/xóa lúc bắt đầu/kết thúc và đọc ngẫu nhiên hoặc tuần tự

Answer 5

Tùy thuộc vào những gì bạn biết.

Nếu tôi không có đầu mối, tôi có xu hướng đi cho một danh sách liên kết, vì hình phạt để thêm/xóa ở cuối là không đổi. Nếu tôi có một ý tưởng thô về kích thước tối đa của nó, tôi đi cho một arraylist với dung lượng quy định, bởi vì nó là nhanh hơn nếu ước tính là tốt. Nếu tôi thực sự biết kích thước chính xác tôi có xu hướng đi cho một mảng bình thường; mặc dù đó không thực sự là một loại bộ sưu tập.

Answer 6

Tôi nhận thấy rằng tất cả các cuộc thảo luận về hiệu suất có phần vô nghĩa, điều duy nhất thực sự quan trọng là đo lường.

Điều đó không nhất thiết phải đúng.

Nếu bạn biết cách ứng dụng hoạt động cho biết bạn rằng một số bộ sưu tập nhất định sẽ rất lớn, thì bạn nên chọn đúng loại bộ sưu tập. Tuy nhiên, loại bộ sưu tập phù hợp phụ thuộc vào chủ yếu là về cách các bộ sưu tập sẽ được sử dụng; tức là trên các thuật toán.

Ví dụ, nếu ứng dụng của bạn có thể bị chi phối bởi việc kiểm tra xem một bộ sưu tập giữ một đối tượng nhất định, thực tế là Collection.contains(Object) là O(N) cho cả LinkedList<T> và ArrayList<T>sức có nghĩa là không phải là một loại bộ sưu tập phù hợp. Thay vào đó, có thể bạn nên đại diện cho bộ sưu tập là HashMap<T, Integer>, trong đó Integer đại diện cho số lần xuất hiện của một số T trong "bộ sưu tập". Điều đó sẽ cung cấp cho bạn thử nghiệm và loại bỏ O(1), với chi phí thêm chi phí không gian và chậm hơn (mặc dù vẫn còn O(1)).

Nhưng điều cần nhấn mạnh là nếu bạn có khả năng xử lý các bộ sưu tập thực sự lớn, sẽ không có thứ gì như kiểu bộ sưu tập "mặc định". Bạn cần phải suy nghĩ về bộ sưu tập trong bối cảnh của các thuật toán. (Và mặt trái là nếu các bộ sưu tập luôn nhỏ, nó có thể tạo ra sự khác biệt nhỏ cho loại bộ sưu tập bạn chọn.)