Khi nào bạn biết khi nào nên sử dụng TreeSet hoặc LinkedList?

Question

Ưu điểm của mỗi cấu trúc là gì?

Trong chương trình của tôi, tôi sẽ được thực hiện các bước sau và tôi đã tự hỏi mà cấu trúc dữ liệu trên tôi nên sử dụng:

1. Chụp trong một mảng không được phân loại và thêm chúng vào một structure1 được sắp xếp.
2. Vượt qua thông qua dữ liệu được sắp xếp và loại bỏ một trong những quyền
3. Thêm dữ liệu (không bao giờ loại bỏ) và trở về cấu trúc đó là một mảng

Answer 1

Nếu bạn muốn giữ nó được sắp xếp và nó gắn-chủ yếu, TreeSet với một So sánh là đặt cược tốt nhất của bạn. JVM sẽ phải duyệt qua LinkedList ngay từ đầu để quyết định vị trí đặt một mục. LinkedList = O (n) cho bất kỳ hoạt động nào, TreeSet = O (log (n)) cho các công cụ cơ bản.

Answer 2

Khi nào bạn biết khi nào nên sử dụng TreeSet hoặc LinkedList? Những lợi thế của mỗi cấu trúc là gì?

Nói chung, bạn quyết định loại bộ sưu tập dựa trên các thuộc tính cấu trúc và hiệu suất mà bạn cần. Ví dụ, một TreeSet là một Set, và do đó không cho phép các bản sao và không giữ thứ tự chèn của các phần tử. Ngược lại, LinkedList là một List và do đó cho phép trùng lặp và duy trì thứ tự chèn. Về phía hiệu suất, TreeSet cung cấp cho bạn O(logN) cách chèn và xóa, trong khi LinkedList cho phép chèn O(1) ở đầu hoặc cuối và chèn O(N) vào vị trí hoặc xóa đã chọn.

Chi tiết được ghi rõ trong lớp và giao diện javadocs tương ứng, nhưng một bản tóm tắt hữu ích có thể được tìm thấy trong Java Collections Cheatsheet.

Trong thực tế, việc lựa chọn loại bộ sưu tập được kết nối mật thiết với thiết kế thuật toán. Cả hai cần phải được thực hiện song song. (Không nên quyết định rằng thuật toán của bạn yêu cầu một bộ sưu tập với các thuộc tính X, Y và Z, và sau đó phát hiện ra rằng không có loại bộ sưu tập nào tồn tại.)

Trong trường hợp sử dụng của bạn, có vẻ như TreeSet sẽ phù hợp hơn . Không có cách nào hiệu quả (tức là tốt hơn O(N^2)) để sắp xếp một LinkedList lớn không liên quan đến việc chuyển nó thành một số cấu trúc dữ liệu khác để thực hiện sắp xếp. Không có cách hiệu quả (tức là tốt hơn O(N)) để chèn phần tử vào đúng vị trí trong Danh sách liên kết được sắp xếp trước đó. Phần thứ ba (sao chép vào một mảng) hoạt động tốt như nhau với một LinkedList hoặc TreeSet; nó là một hoạt động O(N) trong cả hai trường hợp.

[Tôi giả định rằng các bộ sưu tập đủ lớn mà O độ phức tạp lớn dự đoán hiệu suất thực tế một cách chính xác ...]

Answer 3

TreeSet:

TreeSet sử dụng Red-Black cây nằm bên dưới. Vì vậy, các thiết lập có thể được coi là một dynamic search tree. Khi bạn cần một cấu trúc được vận hành đọc/ghi thường xuyên và cũng nên giữ trật tự, TreeSet là một lựa chọn tốt.

Answer 4

Sức mạnh chính hãng và lợi thế của TreeSet nằm trong giao diện nó nhận ra - NavigableSet

Tại sao nó nên mạnh mẽ và trong trường hợp này?

điều hướng giao diện Set thêm ví dụ những 3 phương pháp tốt đẹp:

headSet(E toElement, boolean inclusive) 
    tailSet(E fromElement, boolean inclusive) 
    subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) 

Những phương pháp này cho phép tổ chức giải thuật tìm kiếm hiệu quả (rất nhanh).

Ví dụ: chúng ta cần phải tìm tất cả các tên đó bắt đầu với Milla và kết thúc bằng Wladimir:

TreeSet<String> authors = new TreeSet<String>(); 
    authors.add("Andreas Gryphius"); 
    authors.add("Fjodor Michailowitsch Dostojewski"); 
    authors.add("Alexander Puschkin"); 
    authors.add("Ruslana Lyzhichko"); 
    authors.add("Wladimir Klitschko"); 
    authors.add("Andrij Schewtschenko"); 
    authors.add("Wayne Gretzky"); 
    authors.add("Johann Jakob Christoffel"); 
    authors.add("Milla Jovovich"); 
    authors.add("Taras Schewtschenko"); 
    System.out.println(authors.subSet("Milla", "Wladimir")); 

đầu ra:

[Milla Jovovich, Ruslana Lyzhichko, Taras Schewtschenko, Wayne Gretzky] 

TreeSet không đi qua tất cả các yếu tố, nó tìm thấy elemen đầu tiên và cuối cùng và trả về một Bộ sưu tập mới với tất cả các phần tử trong phạm vi.