Mục Java hiệu quả 17: Làm thế nào có thể ghi đè removeRange() cải thiện hiệu suất?

Question

Trong cuốn sách Java hiệu quả của Joshua Bloch, có một cuộc thảo luận về cách một lớp có thể cung cấp "phương pháp được bảo vệ được lựa chọn một cách khôn ngoan" như móc vào các hoạt động bên trong của nó.
Tác giả sau đó trích dẫn các tài liệu trong AbstractList.removeRange():

Phương pháp này được gọi bởi các hoạt động clear trong danh sách này và danh sách con của nó. Việc ghi đè phương pháp này để tận dụng lợi thế của nội bộ của việc triển khai danh sách có thể cải thiện đáng kể hiệu suất của hoạt động clear trên danh sách này và các đối tượng con của nó.

Câu hỏi của tôi là, cách ghi đè phương pháp này có thể cải thiện hiệu suất (đơn giản là không ghi đè lên hiệu suất)? Bất cứ ai có thể đưa ra một ví dụ về điều này?

Answer 1

Hãy lấy một ví dụ cụ thể - giả sử rằng triển khai của bạn được hỗ trợ bởi mảng động (ví dụ: cách hoạt động của ArrayList). Bây giờ, giả sử bạn muốn loại bỏ các phần tử trong phạm vi [bắt đầu, kết thúc). Việc triển khai mặc định của removeRange hoạt động bằng cách đưa một trình lặp đến vị trí start, sau đó gọi số remove() số lần thích hợp.

Mỗi lần remove() được gọi, triển khai mảng động phải trộn tất cả các phần tử tại vị trí start + 1 và chuyển tiếp lại một điểm để lấp đầy khoảng trống còn lại trong phần tử đã xóa. Điều này có khả năng mất thời gian O (n), bởi vì tất cả các phần tử mảng có thể cần phải xáo trộn. Điều này có nghĩa rằng nếu bạn đang xóa tổng số các phần tử k khỏi danh sách, cách tiếp cận ngây thơ sẽ mất thời gian O (kn), vì bạn đang làm O (n) công việc k lần.

Bây giờ hãy xem xét một cách tiếp cận tốt hơn nhiều: sao chép các phần tử ở vị trí end vị trí start, sau đó yếu tố end + 1 vị trí start + 1, vv cho đến khi tất cả các yếu tố này được sao chép. Điều này đòi hỏi bạn chỉ thực hiện tổng số công việc O (n), bởi vì mọi phần tử được di chuyển nhiều nhất một lần. So với cách tiếp cận O (kn) được đưa ra bởi thuật toán ngây thơ, đây là một cải tiến hiệu suất rất lớn. Do đó, việc ghi đè removeRange để sử dụng thuật toán hiệu quả hơn này có thể tăng hiệu suất đáng kể.

Hy vọng điều này sẽ hữu ích!

Answer 2

Như quy định tại javadocs của phương pháp:

thi này được một iterator danh sách vị trí trước khi fromIndex, và lặp đi lặp lại các cuộc gọi ListIterator.next tiếp theo ListIterator.remove cho đến khi toàn bộ phạm vi đã được gỡ bỏ.

Vì lớp trừu tượng này không biết về nội bộ của lớp con, nó dựa trên thuật toán chung này sẽ chạy theo thời gian tỷ lệ thuận với số mục bị xóa.

Nếu, ví dụ: bạn đã triển khai một lớp con lưu trữ các phần tử dưới dạng danh sách được liên kết. Sau đó, bạn có thể tận dụng lợi thế của thực tế này và ghi đè phương pháp này để sử dụng một thuật toán danh sách liên kết cụ thể (di chuyển con trỏ đến fromIndex để trỏ đến toIndex) chạy trong thời gian không đổi. Do đó, bạn đã cải thiện hiệu suất vì bạn đã tận dụng lợi thế của nội bộ.

Answer 3

Đơn giản bằng cách ghi đè phương pháp này, bạn có thể sử dụng thuật toán chung này theo yêu cầu của bạn như các vấn đề lập chỉ mục của bạn. Vì nó là một phương thức được bảo vệ trong AbstractList và cũng trong ArrayList và việc thực hiện nó có hoạt động như các cuộc gọi lặp lại để remove() cần mỗi lần dịch chuyển tất cả các phần tử có sẵn ở phía bên phải của phần tử bị loại bỏ bởi một chỉ mục. Rõ ràng nó không hiệu quả, vì vậy bạn có thể làm cho nó hoạt động tốt hơn.