Triển khai danh sách xâm nhập cho Java?

Question

Có bất kỳ (các lớp danh sách liên kết kép được tích hợp tốt) có sẵn cho Java không? Hay tôi nên tự làm? Boost có nó cho C++: http://beta.boost.org/doc/libs/1_40_0/doc/html/boost/intrusive/list.html.

Danh sách xâm nhập là một thùng chứa (trong trường hợp này) các con trỏ tiếp theo và trước trong phần tử, do đó các hoạt động danh sách điển hình như thay thế và loại bỏ có thể được nhắm mục tiêu trực tiếp vào lớp cơ sở thay vì lớp container. Có một số tình huống nhất định, trong đó danh sách xâm nhập là giải pháp tốt nhất.

Tôi cố gắng đưa ra một ví dụ phù hợp. Giả sử tôi đã liên kết danh sách L list1 và L list2 thuộc sở hữu của các loại khác nhau của các lớp X1 và Y2.

lớp Q (không có gì để làm hoặc không dễ dàng truy cập vào giao diện x1 và Y2 nếu không) cần phải làm i) thay thế, ii) loại bỏ hoạt động cho phần tử e, luôn tồn tại ở đâu đó, trong danh sách1 xor list2 tùy thuộc vào trạng thái thời gian chạy, nhưng thông tin đó không được lưu trữ trực tiếp ở bất kỳ đâu.

Với danh sách intrussive Q chỉ có thể lưu trữ tham chiếu đến phần tử thành phần tử e và nó luôn chỉ đúng vị trí.

Nếu không, bạn phải chọn một số cách giải quyết rõ ràng phức tạp hơn hoặc cách khác. - Lớp trình bao bọc cho phần tử e và các phương thức bổ sung để hoàn thành các hoạt động i và ii. Số

Về cơ bản, câu hỏi vẫn không phải là về hiệu suất mà là sự phức tạp của kiến ​​trúc. Điều này cũng có thể được hiểu là một loại tình huống đối tượng được chia sẻ nơi mà giải pháp IL tránh nhu cầu cập nhật cho mọi khách hàng Lx và Q.

Xin lưu ý rằng tôi không cần thiết phải tương thích với các thùng chứa tiêu chuẩn khác. Chỉ cần thực thi lsit xâm nhập chung với một thao tác lặp, thêm, loại bỏ và tìm được sử dụng với lớp phần tử không xác định.

Cảm ơn.

Answer 1

Tôi không biết bất kỳ triển khai hiện có nào (và không, tôi không xem xét các bộ sưu tập Java bình thường sẽ xâm nhập).

Đó có thể là vì lợi thế lớn duy nhất mà danh sách sẽ có trong Java sẽ là cuộc gọi nhanh remove() khi bạn đã xóa phần tử trong tầm tay (và không có Iterator ở vị trí đó). Phần tử không sao chép-không phải là một đối số hợp lệ trong Java, vì các triển khai Java List chỉ xử lý các tham chiếu (và không bao giờ sao chép toàn bộ đối tượng).

Nhưng bạn có thể dễ dàng viết một mục đích chung List thực hiện đó là xâm nhập bằng cách tạo ra các giao diện cần thiết:

public interface IntrusiveListElement<E extends<IntrusiveListElement<E>> { 
    public void setNext(E next); 
    public E getNext(); 
    public void setPrev(E prev); 
    public E getPrev(); 
} 

public class IntrusiveList<E extends IntrusiveListElement<E>> implements List<E> { 
    // implement your run-of-the-mill double-linked list here 
} 

lớp yếu tố bạn có thể trông như thế này:

public class MyBusinessElement implements IntrusiveListElement<MyBusinessElement> { 
    private MyBusinessElement prev; 
    private MyBusinessElement next; 

    public void setNext(MyBusinessElement next) { 
    this.next = next; 
    } 

     public MyBusinessElement getNext() { 
    return next; 
    } 

    public void setPrev(MyBusinessElement prev) { 
    this.prev = prev; 
    } 

    public MyBusinessElement getPrev() { 
    return prev; 
    } 
} 

Answer 2

Bạn đã xem qua số Deque class chưa? Mỗi javadoc, "Bộ sưu tập tuyến tính hỗ trợ chèn và loại bỏ phần tử ở cả hai đầu. Tên deque là viết tắt của" hàng đợi đôi đã kết thúc "và thường được phát âm là" sàn "." Nó được thực hiện bởi ArrayDeque, LinkedBlockingDeque và LinkedList.

Answer 3

Ngữ nghĩa của Java là do thiết kế xâm nhập, chúng sử dụng các tham chiếu và không sao chép. Về cơ bản, bạn chỉ muốn tìm danh sách được liên kết tốt nhất mà java có, LinkedList hoặc bất kỳ thứ gì và nó sẽ xâm phạm.

import java.util.LinkedList; 

public class Foo { 

    public static void main(String[] args) { 
    String[] i = new String[1]; 
    i[0] = "FOO"; 
    String[] j = new String[1]; 
    j[0] = "BAZ"; 

    LinkedList<String[]> list = new LinkedList<String[]>(); 

    list.add(i); 
    list.add(j); 

    for (String[] x: list) { 
     System.out.println(x[0]); 
    } 

    i[0] = "ZILCH"; 

    for (String[] x: list) { 
     System.out.println(x[0]); 
    } 
    } 
} 

Đây là đầu ra, lưu ý cách thay đổi i đã thay đổi giá trị trong danh sách.

FOO 
BAZ 
ZILCH 
BAZ 

Answer 4

nếu bạn nhìn vào mã SDK, bạn sẽ thấy LinkedList là danh sách mục nhập lớp riêng tư chứa phần tử tiếp theo và trước đó. Vì vậy, nếu bạn bao gồm MyClass trong danh sách này, một phần tử của danh sách sẽ là một Entry với đối tượng của bạn và các liên kết cho các phần tử tiếp theo và trước đó của danh sách.

Vì vậy, tôi nghĩ rằng nó đang xâm nhập ...

private static class Entry<E> { 
    E element; 
    Entry<E> next; 
    Entry<E> previous; 

    Entry(E element, Entry<E> next, Entry<E> previous) { 
     this.element = element; 
     this.next = next; 
     this.previous = previous; 
    } 
} 

Answer 5

Có bất kỳ (thực hiện tốt) xâm nhập tăng gấp đôi lớp liên kết danh sách (es) có sẵn cho Java?

Tôi không tin rằng bạn sẽ tìm thấy.

sự hiểu biết của tôi về "xâm nhập" là đối tượng ứng dụng được lưu trữ trong các cấu trúc dữ liệu cần phải trực tiếp bao gồm ("xâm nhập") con trỏ/trước tiếp theo trong đối tượng ứng dụng.

Điều này trái ngược với cách tiếp cận "trình bao bọc con trỏ" trong đó nút cấu trúc dữ liệu chứa con trỏ tới đối tượng ứng dụng, do đó không yêu cầu sửa đổi đối tượng ứng dụng. Cách tiếp cận xâm nhập có a number of benefits bao gồm việc tránh hội nghị kép (một lần cho nút và một lần cho con trỏ của nút đến đối tượng ứng dụng) phổ biến cho phương pháp "trình bao bọc con trỏ".

Tôi không tin rằng bạn sẽ tìm thấy thư viện cấu trúc dữ liệu xâm nhập cho Java. Java thiếu C++ - giống như các mẫu và nhiều thừa kế, và nó không dễ dàng hỗ trợ sao chép theo giá trị của toàn bộ một đối tượng. Bởi vì điều này, tôi không nghĩ rằng có một cách để tổng quát thêm các trường thể hiện kế tiếp/prev cho một đối tượng Java.

Ví dụ, do đối tượng áp dụng:

class Foo { 
    int bar; 
} 

bằng cách nào đó bạn cần để có thể thêm bên cạnh các lĩnh vực/trước và phương pháp quản lý danh sách công việc hay một dẫn xuất của nó:

class Foo2 { 
    int bar; 
    Foo2 prev; 
    Foo2 next; 
} 

Một cách để thêm các trường này bằng cách cung cấp một lớp cơ sở với các trường này để các lớp ứng dụng mở rộng - đây là cách tiếp cận của Boost. Tuy nhiên, cách tiếp cận này rất hạn chế trong một ngôn ngữ đơn thừa kế như Java.

Giao diện Java thường là câu trả lời của Java cho nhiều lần kế thừa, ví dụ: một giao diện để yêu cầu các phương thức getNext() và getPrev() của các lớp ứng dụng. Tuy nhiên, nếu bạn cần cấu trúc dữ liệu xâm nhập vì lý do hiệu suất, việc truy cập vào các trường kế tiếp/trước thông qua một phương pháp có thể ảnh hưởng xấu đến các mục tiêu đó.

Generics Java cũng không mở rộng các lớp theo cách cần thiết.

Hoặc tôi có nên tự làm không?

Nếu một lần cho một trường hợp cụ thể cho nhu cầu được đánh giá cẩn thận, hãy tự cuộn. Nếu bạn đang cố gắng để cuộn một chung cho mục đích sử dụng chung, tôi không chắc chắn giá trị của nó.

Một cách tiếp cận thực sự thô sẽ được tùy chỉnh mở rộng các lớp ứng dụng để thêm các lĩnh vực cần thiết:

class Foo3 extends Foo { 
    Foo3 prev; 
    Foo3 next; 
} 

và sử dụng cut-n-dán tái sử dụng để thêm các phương pháp quản lý danh sách.Tuy nhiên, tôi sẽ khuyên bạn nên không bằng cách sử dụng phương pháp này.

Soapbox

Bạn không nêu lý do tại sao bạn cần một cấu trúc dữ liệu xâm nhập. Có lẽ bạn có lý do hợp lệ để cần một, nhưng thật khó để tưởng tượng chúng. Java phụ thuộc rất nhiều vào việc sử dụng các con trỏ đối tượng và cố gắng tránh chúng như thế này sẽ rất khó khăn.

tôi trân trọng đề nghị bạn xem xét:

• được bạn cố gắng để sớm tối ưu hóa,
• được bạn thêm sự phức tạp không cần thiết vì lợi ích ít
• nếu tốc độ và quản lý bộ nhớ được tối quan trọng, bạn đang sử dụng quyền ngôn ngữ?

Answer 6

Bạn hy vọng gì để đạt được bằng cách sử dụng một danh sách xâm nhập? Tôi khó có thể nghĩ được những lợi thế sẽ là gì. Được rồi, có một hiệu quả tầm thường mà bạn chỉ có một đối tượng thay vì hai đối với mỗi nút. Nhưng giá của điều này là một mất mát lớn về tính linh hoạt và độ tin cậy. Ví dụ, bây giờ bạn không thể có cùng một đối tượng trong hai danh sách cùng một lúc. Điều gì sẽ xảy ra nếu người gọi truy xuất một cá thể của một thành viên trong danh sách và cố gắng thay đổi một trong các con trỏ? Những gì nó một người gọi nhân bản một nút và không cập nhật các con trỏ? Vv

Dave Ray làm cho điểm đó với một danh sách xâm nhập bạn có thể xóa một nút trong thời gian không đổi vì bạn đã có con trỏ và không cần phải tìm lại mục đó. Đúng, nhưng điều đó giả định rằng bạn đã lưu một nút điều khiển cho nút đó ở đâu đó và hiện đang quay lại nó. Với lớp Java LinkedList khá nhiều cách duy nhất để truy cập các phần tử là duyệt qua danh sách bằng một Iterator hoặc để tìm kiếm một đối tượng cụ thể. Nếu bạn đi qua với một Iterator, Iterator.remove sẽ loại bỏ trong thời gian không đổi. Vì vậy, nó chỉ khi bạn tìm kiếm, tìm kiếm, và sau đó quyết định loại bỏ rằng bạn phải trả tiền phạt này. Tôi nghĩ rằng nó sẽ là một cải tiến về việc thực hiện LinkedList nếu họ lưu trữ một con trỏ đến đối tượng cuối cùng được tìm thấy để cải thiện hiệu suất vào chính xác thời điểm này. Tôi đoán là họ không phải vì nó sẽ làm cho việc loại bỏ không xác định: Bạn có thể có cùng một đối tượng trong danh sách nhiều lần - hoặc theo đúng nghĩa đen hoặc hai đối tượng so sánh bằng nhau - và hợp đồng xóa hiện tại nói rằng nó luôn luôn loại bỏ sự xuất hiện đầu tiên. Nếu có một con trỏ được lưu trong bộ nhớ cache, sẽ rất khó để nói đây là lần đầu tiên, thứ hai hay thứ 42.

Ồ, để thực sự trả lời câu hỏi của bạn: Không, tôi không biết về triển khai nguồn mở ở đó. Nhưng sau đó nếu tôi cần hương vị của riêng tôi về một danh sách liên kết, tôi nghĩ rằng tôi sẽ chỉ cuộn của riêng tôi. Có lẽ nếu Java tiêu chuẩn không đáp ứng nhu cầu của bạn, điều đó phải có nghĩa là bạn có một số nhu cầu khá chuyên biệt. Trong trường hợp tìm kiếm một triển khai off-the-shelf xảy ra để đáp ứng nhu cầu chuyên ngành của bạn âm thanh như rất nhiều rắc rối, và bạn chắc chắn có thể thực hiện nó trong, những gì, một hoặc hai ngày làm việc? Bạn có thể dành nhiều thời gian tìm kiếm một sản phẩm phù hợp hơn là nó sẽ làm để chỉ cần làm điều đó. Có thể bạn đã dành nhiều thời gian hơn để đọc các câu trả lời cho bài đăng này hơn là nó sẽ đưa bạn viết nó.