hành vi tiệm cận của phương pháp Scala

Question

Có nơi nào đó tôi có thể tìm ra dự kiến ​​thời gian và gian phức tạp của các hoạt động trên các bộ sưu tập như HashSet, TreeSet, Danh sách và vân vân?

Có phải người ta chỉ muốn biết những điều này từ các thuộc tính của chính các loại dữ liệu trừu tượng?

Tôi biết về Performance characteristics for Scala collections, nhưng điều này chỉ đề cập đến một số thao tác rất cơ bản. Có lẽ phần còn lại của các hoạt động cho các bộ sưu tập này được xây dựng hoàn toàn từ một bộ cơ sở nhỏ, nhưng sau đó, có vẻ như tôi chỉ mong đợi để biết rằng họ đã thực hiện chúng theo cách này?

Answer 1

Đặc điểm hiệu suất của các phương pháp khác thực sự khó khẳng định.Hãy xem xét những điều sau đây:

• Những phương pháp này được thực hiện tất cả dựa trên foreach hoặc iterator, và ở mức độ thường rất cao trong hệ thống phân cấp. Ví dụ: map được thực hiện trên collection.TraversableLike. Để thêm sự xúc phạm đến thương tích, việc triển khai phương pháp nào được sử dụng phụ thuộc vào sự tuyến tính của thừa kế lớp. Điều này cũng áp dụng cho bất kỳ phương pháp nào được gọi là người trợ giúp. Nó đã xảy ra trước khi những thay đổi ở đây gây ra các vấn đề hiệu suất không lường trước được. Vì foreach và iterator đều là O(n), mọi hiệu suất được cải thiện phụ thuộc vào chuyên môn theo các phương pháp khác, chẳng hạn như size và slice.
• Đối với nhiều người trong số họ, có thêm sự phụ thuộc vào đặc điểm hiệu suất của trình tạo được cung cấp, tùy thuộc vào trang web cuộc gọi thay vì trang định nghĩa.

Vì vậy, kết quả là nơi mà phương pháp được xác định - và được ghi lại - không có đủ thông tin để nêu rõ các đặc tính hiệu suất của nó và có thể không chỉ phụ thuộc vào các phương pháp khác được kế thừa bộ sưu tập, nhưng ngay cả bởi các đặc tính hiệu suất của một đối tượng, Builder, thu được từ CanBuildFrom, được truyền tại trang web gọi.

Tốt nhất, mọi tài liệu như vậy sẽ được mô tả theo các phương pháp khác. Điều đó không có nghĩa là nó không đáng giá, nhưng nó không dễ dàng thực hiện - và các nhiệm vụ khó khăn đối với các dự án nguồn mở phụ thuộc vào tình nguyện viên, những người thường làm việc theo những gì họ thích, chứ không phải những gì cần thiết.

Answer 2

Hướng dẫn cho các phương pháp khác nên - chỉ cần nghĩ triển khai hiệu quả sẽ như thế nào.

Hầu hết các hoạt động hàng loạt khác trên bộ sưu tập (hoạt động xử lý từng phần tử trong bộ sưu tập) là O(n), vì vậy chúng không được đề cập ở đó. Ví dụ như filter, map, foreach, indexOf, reverse, find ...

Phương pháp trở về vòng lặp hoặc suối như combinations và permutations thường O(1).

Phương pháp liên quan đến 2 bộ sưu tập thường là O(max(n, m)) hoặc O(min(n, m)). Đây là những zip, zipAll, sameElements, corresponds ...

Phương pháp union, diff, và intersect là O(n + m).

Biến thể sắp xếp, một cách tự nhiên, O(nlogn). groupBy là O(nlogn) trong quá trình triển khai hiện tại. indexOfSlice sử dụng thuật toán KMP và là O(m + n), trong đó m và n là độ dài của chuỗi.

Các phương pháp như +:, :+ hoặc patch thường O(n) là tốt, trừ khi bạn đang đối phó với một trường hợp cụ thể của một bộ sưu tập bất biến mà các hoạt động trong câu hỏi là hiệu quả hơn - ví dụ, thêm vào trước một thành phần trên chức năng List hoặc thêm một phần tử vào một số Vector.

Phương pháp toX thường là O(n), vì chúng phải lặp lại tất cả các phần tử và tạo bộ sưu tập mới. Ngoại lệ là toStream tạo bộ sưu tập một cách uể oải - vì vậy, nó là O(1). Ngoài ra, bất cứ khi nào X là loại bộ sưu tập toX chỉ trả về this, là O(1).

Việc triển khai Iterator phải có các hoạt động O(1) (khấu hao) next và hasNext. Việc tạo Iterator phải là trường hợp xấu nhất O(logn), nhưng O(1) trong hầu hết các trường hợp.