Hàng đợi nhanh trong Java

Question

Tôi đang tìm kiếm triển khai nhanh queue trong Java. Tôi thấy rằng LinkedList triển khai giao diện Queue, nhưng nó sẽ chỉ nhanh như một quyền LinkedList? Có cách nào để có hàng đợi nhanh hơn, đặc biệt là đối với add (tôi chỉ cần poll, add và kiểm tra empty). Xuống dòng Tôi cũng có thể cần PriorityQueue nhưng chưa.

Answer 1

Tôi thấy rằng LinkedList thực hiện giao diện Hàng đợi, nhưng nó sẽ chỉ nhanh bằng quyền LinkedList?

Nhãn cầu mã nguồn, LinkedList là O (1) cho các hoạt động Queue.add, Queue.poll và Queue.peek.

Tôi hy vọng điều đó đủ nhanh.

Answer 2

Nếu có nhiều chuỗi sẽ truy cập vào hàng đợi thì hãy cân nhắc sử dụng ArrayBlockingQueue. Nếu không, hãy xem ArrayDeque. Từ ArrayDeque API:

Lớp này có khả năng là nhanh hơn so với stack khi được sử dụng như một chồng, và nhanh hơn hơn LinkedList khi được sử dụng như một hàng đợi.

Cụ thể một thực hiện hàng đợi mảng dựa trên làm giảm sự cần thiết phải thay đổi kích thước các mảng tiềm ẩn nếu các mảng hiện có đủ năng lực, do đó làm cho bổ sung vào hàng đợi thường nhanh hơn so với LinkedList. Lưu ý rằng ArrayBlockingQueue là một triển khai bị ràng buộc trong khi ArrayDeque sẽ thay đổi kích thước theo yêu cầu.

Mặt trái là LinkedList thường sẽ cung cấp một đại diện nhỏ gọn hơn nhiều, đặc biệt trong trường hợp hàng đợi của bạn tăng lên và co lại theo số lượng lớn. Ví dụ: nếu bạn đã thêm 10.000.000 phần tử vào một số ArrayDeque và sau đó xóa 9,999,999 phần tử, mảng cơ bản sẽ vẫn có độ dài 10.000.000 trong khi một LinkedList sẽ không gặp phải vấn đề này.

Thực tế, đối với quyền truy cập một luồng vào hàng đợi không bị chặn, tôi có xu hướng ưu tiên LinkedList. Tôi tưởng tượng sự khác biệt hiệu suất là rất cẩu thả, bạn sẽ không nhận thấy sự khác biệt anyway.

Answer 3

Nếu hiệu suất của danh sách được liên kết thực sự là vấn đề, thay thế sẽ là triển khai "hàng đợi hình tròn" trong một mảng, tức là hàng đợi nơi bắt đầu và điểm kết thúc khi mục nhập được thêm và xóa. Tôi có thể cung cấp thêm chi tiết nếu bạn quan tâm. Khi tôi đang sử dụng các ngôn ngữ không có thư viện sưu tập, đây là cách tôi luôn triển khai hàng đợi bởi vì nó dễ viết hơn một danh sách liên kết và nó nhanh hơn. Nhưng với các bộ sưu tập tích hợp, nỗ lực viết và gỡ lỗi bộ sưu tập của riêng tôi cho một trường hợp đặc biệt không đáng lo ngại 99% thời gian: Khi nó đã được viết, thực tế là tôi có thể viết nó theo cách khác nhanh hơn tôi có thể viết lại nó theo cách Java làm là một thực tế không liên quan. Và bất kỳ lợi ích hiệu suất nào cũng có thể quá nhỏ để có thể gây ra rắc rối. Tôi phụ loại hiện có bộ sưu tập để có được hành vi đặc biệt tôi cần bây giờ và sau đó, nhưng tôi khó ép để nghĩ về thời gian qua mà tôi đã viết một từ đầu.

Answer 4

Bạn có thể muốn xem http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list giới thiệu GapList. Việc triển khai danh sách mới này kết hợp các điểm mạnh của cả hai ArrayList và LinkedList.

Do đó, thực hiện giao diện Deque, nhưng cũng có thể được đặt trước như đã đề cập ở trên ArrayDeque. Ngoài ra, bạn cũng có được tất cả các khả năng của giao diện List miễn phí.

Answer 5

Bắt đầu với việc thực thi Hàng đợi xoay thực sự đơn giản với thái độ "C/C++ như" và kích thước cố định.

class SimpleQueue<E> 
{ 

int index = 0; 
int head = 0; 
int size = 100; 
int counter = 0; 
E[] data ; 


@SuppressWarnings("unchecked") 
SimpleQueue() 
{ 
    data = (E[]) new Object[size]; 
} 

public void add(E e) 
{ 
    data[index]=e; 
    index=(index+1)%size; 
    counter++; 
} 

public E poll() 
{ 
    E value = data[head]; 
    head=(head+1)%size; 
    counter--; 
    return value; 
} 

public boolean empty() 
{ return counter==0; } 

//Test 
public static void main(String[] args) 
{ 
    SimpleQueue<Integer> s = new SimpleQueue<Integer>(); 

    System.out.println(s.empty()); 

    for(int i=0; i< 10; i++) 
     s.add(i); 

    System.out.println(s.empty()); 

    for(int i=0; i<10; i++) 
     System.out.print(s.poll()+","); 

    System.out.println("\n"+s.empty()); 

} 
} 

Sau đó cải thiện.