Gần đây, tôi đã ngạc nhiên bởi thực tế là một số bộ sưu tập Java không có thời gian hoạt động liên tục của phương thức size().Sự phức tạp không mong đợi của các phương thức phổ biến (kích thước) trong khung công tác Bộ sưu tập Java?
Trong khi tôi biết rằng việc triển khai đồng thời các bộ sưu tập đã thực hiện một số thỏa hiệp như một sự cân bằng để đạt được đồng thời (kích thước là O (n) trong ConcurrentLinkedQueue, ConcurrentSkipListSet, LinkedTransferQueue, v.v.) tin tốt là tài liệu này được ghi lại chính xác trong tài liệu API .
Điều tôi quan tâm là hiệu suất của kích thước phương thức trên các lượt xem được trả về bởi một số phương thức của các bộ sưu tập. Ví dụ: TreeSet.tailSet trả về chế độ xem phần của bộ sao lưu có phần tử lớn hơn hoặc bằng fromElement. Điều làm tôi ngạc nhiên là kích thước gọi trên SortedSet trả về là tuyến tính đúng lúc, đó là O (n). Ít nhất đó là những gì tôi quản lý để khai thác từ mã nguồn của OpenJDK: Trong TreeSet được thực hiện như wrapper trên TreeMap, và trong vòng một TreeMap, có lớp EntrySetView có phương pháp kích thước như sau:
abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
private transient int size = -1, sizeModCount;
public int size() {
if (fromStart && toEnd)
return m.size();
if (size == -1 || sizeModCount != m.modCount) {
sizeModCount = m.modCount;
size = 0;
Iterator i = iterator();
while (i.hasNext()) {
size++;
i.next();
}
}
return size;
}
....
}
Điều này có nghĩa rằng kích thước thời gian đầu tiên được gọi là O (n) và sau đó nó được lưu trữ miễn là bản đồ sao lưu không được sửa đổi. Tôi không thể tìm thấy thông tin này trong tài liệu API. Triển khai hiệu quả hơn sẽ là O (log n) với sự cân bằng bộ nhớ trong bộ nhớ đệm của các kích thước subtree. Kể từ khi sự cân bằng như vậy đang được thực hiện để tránh trùng lặp mã (TreeSet như wrapper trên TreeMap), tôi không thấy lý do tại sao họ không nên được thực hiện vì lý do hiệu suất. Tôi không biết có phải là một tài liệu chi tiết và đầy đủ về hiệu suất của nhiều hoạt động như vậy, đặc biệt là những hoạt động hoàn toàn bất ngờ không? Không.
tôi sẽ nghĩ rằng Javadocs bao gồm thông tin đó. – Thilo
Câu hỏi thú vị (+1). Tôi không thể giúp đỡ về phía trước tài liệu (tôi đã không nhìn thấy sự phức tạp một cách rõ ràng tài liệu). Tuy nhiên, cá nhân tôi thấy hành vi của 'tailSet()' hoàn toàn trực quan. Tôi nghĩ sẽ ngạc nhiên hơn nếu mọi người phải trả tiền phạt cho bộ nhớ để một trường hợp sử dụng cận biên có hiệu suất tốt hơn. – NPE
@NPE Bạn có đồng ý với hình phạt về bộ nhớ mà tất cả chúng ta đều có từ mọi Bộ được thực hiện như một trình bao bọc cho Bản đồ chỉ dành cho các nhà phát triển JDK không phải triển khai cùng một tính năng hai lần không? :) Tôi nghĩ rằng tôi đã làm cho nó khá rõ ràng rằng vấn đề của tôi là với tài liệu và không thực hiện chính nó. Điều gì làm tôi bối rối là TreeMap.size là O (1), TreeMap.tailSet là O (log N) và không có thông tin cho TreeMap.tailSet(). Size() và tôi biết nó có thể là O (log n) và Trên). – mario