Tại sao Java ArrayLists không co tự động

Question

Thời gian dài trước đây, tôi đã xem một bài giảng video từ Princeton Coursera MOOC: Giới thiệu về các thuật toán, có thể được tìm thấy here. Nó giải thích chi phí thay đổi kích thước cấu trúc giống như ArrayList trong khi thêm hoặc xóa các phần tử khỏi cấu trúc đó. Nó chỉ ra rằng nếu chúng tôi muốn cung cấp thay đổi kích thước cho cấu trúc dữ liệu của chúng tôi, chúng tôi sẽ đi từ O(n) đến amortized O(n) cho các hoạt động add và remove.

Tôi đã sử dụng Java ArrayList trong một vài năm. Tôi đã luôn luôn chắc chắn rằng họ phát triển và thu nhỏ tự động. Chỉ gần đây, với sự ngạc nhiên lớn của tôi, tôi đã được chứng minh là sai trong this post. Java ArrayList s không co lại (mặc dù, tất nhiên chúng phát triển) một cách tự động.

Dưới đây là những câu hỏi của tôi:

1. Theo tôi cung cấp bị thu hẹp trong ArrayList s không thực hiện bất kỳ tác hại như việc thực hiện đã là amortized O(n). Tại sao những người tạo Java không đưa tính năng này vào thiết kế?

2. Tôi biết rằng các cấu trúc dữ liệu khác như HashMap cũng không tự động thu nhỏ. Có cấu trúc dữ liệu nào khác trong Java được xây dựng trên các mảng hỗ trợ thu hẹp tự động không?

3. Xu hướng bằng các ngôn ngữ khác là gì? Làm thế nào để tự động thu hẹp trông giống như trong trường hợp danh sách, từ điển, bản đồ, bộ trong Python/C# vv. Nếu chúng đi theo hướng ngược lại với Java, thì câu hỏi của tôi là: tại sao?

Answer 1

Nhận xét đã bao gồm hầu hết những gì bạn đang yêu cầu. Dưới đây một số suy nghĩ về câu hỏi của bạn:

1. Khi tạo một cấu trúc giống như ArrayList trong Java, các nhà phát triển đưa ra quyết định nào đó liên quan đến thời gian chạy/hiệu suất. Họ rõ ràng đã quyết định loại trừ thu hẹp từ các hoạt động "bình thường" để tránh thời gian chạy bổ sung, cần thiết.

2. Câu hỏi đặt ra là lý do bạn muốn thu nhỏ tự động. Các ArrayList không phát triển nhiều (yếu tố là khoảng 1,5; newCapacity = oldCapacity + (oldCapacity >> 1), để được chính xác). Có lẽ bạn cũng chèn ở giữa và không chỉ phụ thêm vào cuối. Sau đó, LinkedList (không dựa trên một mảng -> không cần thu hẹp) có thể tốt hơn. Nó thực sự phụ thuộc vào trường hợp sử dụng của bạn. Nếu bạn nghĩ rằng bạn thực sự cần tất cả mọi thứ một ArrayList hiện, nhưng nó phải co lại khi loại bỏ các yếu tố (tôi nghi ngờ bạn thực sự cần điều này), chỉ cần mở rộng ArrayList và ghi đè lên các phương pháp. Nhưng hãy cẩn thận! Nếu bạn co lại ở mọi lần xóa, bạn sẽ quay lại tại O(n).

3. C# List và C++ vector hành xử giống nhau liên quan đến việc thu hẹp danh sách khi xóa các phần tử. Nhưng các yếu tố tự phát triển khác nhau. Ngay cả một số triển khai Java cũng sử dụng các yếu tố khác nhau.