Cách tốt hơn để tạo ra một mảng đặt hàng từ priorityQueue trong Java

Question

tôi có thể tất nhiên thực hiện như sau:

 PriorityQueue<Integer> q = new PriorityQueue<Integer>(100, new Comparator<Integer>() { 
      public int compare(Integer x, Integer y) { 
       return Integer.valueOf(x).compareTo(y); 
      } 
     }); 
     ...//add some elements to q 
     int[] arr = new int[q.size()]; 
     int i = 0; 
     while (q.size() != 0) { 
      arr[i++] = q.remove(); 
     } 

Nhưng phương pháp này làm trống hàng đợi mà tôi muốn giữ. Tôi biết tôi có thể đã sắp xếp bằng cách so sánh đó (tất nhiên khi nó không tầm thường như trên) để lấy mảng này, nhưng tôi sẽ phải tạo một mảng đầu tiên, sau đó sao chép các phần tử từ hàng đợi vào mảng, sau đó sắp xếp mảng .

Có cách tiếp cận nào tốt hơn không? Cảm ơn bạn đã giúp đỡ!

Answer 1

Sử dụng LinkedList làm bộ sưu tập trung gian. Hàm khởi tạo của nó thêm các phần tử theo thứ tự được chỉ định bởi bộ sưu tập được cung cấp và phương thức toArray(T[] arr) của nó duy trì thứ tự danh sách.

PriorityQueue<Integer> q = new PriorityQueue<Integer>(100, new Comparator<Integer>() { 
    public int compare(Integer x, Integer y) { 
     return Integer.valueOf(x).compareTo(y); 
    } 
}); 

/* ...elided, add items... */ 

List<Integer> integers = new LinkedList<Integer>(q); 
Integer[] orderedIntegerArray = integers.toArray(new Integer[0]); 

Answer 2

Bạn có thể sử dụng vòng lặp lặp để lặp qua hàng đợi.

for (Iterator<Integer> iterator = q.iterator(); iterator.hasNext();) { 
    arr[i++] = iterator.next(); 
} 

Answer 3

Vì Hàng đợi mở rộng Bộ sưu tập, bạn sẽ có thể lặp lại.

cho (Số nguyên iq: hàng đợi) arr [i ++] = iq;

Hmm, nếu @amit đúng là PriorityQueue đảm bảo lặp lại theo thứ tự, điều này sẽ không hoạt động.

Tuy nhiên, một Chỉnh sửa sau ...

Nhiều người trong chúng biết rằng PriorityQueue không lặp theo thứ tự. Đó là bởi vì PriorityQueue chỉ phân loại một phần các phần tử, nó chủ yếu theo dõi phần tử đầu (ít nhất).

Một đề xuất để giữ nguyên PriorityQueue là tạo bản sao và lấy/rút ra khỏi bản sao. Khác là tạo một List từ các nội dung (vì bạn biết kích thước chính xác, tôi nghĩ một ArrayList là thích hợp nhất) và sắp xếp một cách rõ ràng Danh sách.

Tôi đoán là Danh sách sẽ nhanh hơn. Chúng ta biết rằng nó là O (n log (n)). Bây giờ, các javadocs PriorityQueue nói rằng thêm và loại bỏ là O (log (n)). Và bạn sẽ gọi chúng là N lần, vì vậy, về mặt lý thuyết, PriorityQueue cũng là O (n log (n)). Tuy nhiên, nếu sử dụng PriorityQueue thực sự nhanh hơn một loại cho trường hợp sử dụng phổ biến này, lặp qua danh sách có thứ tự, tôi nghĩ tôi đã thấy nhiều bài viết "mẹo hiệu suất" cho biết "Sử dụng PriorityQueue thay vì Collections.sort(). " Mà tôi chưa có. Tôi đã bỏ lỡ chúng chưa?

Dù sao, OP có thể thử cả hai và báo cáo lại. Nó sẽ là, với tôi, một khám phá hấp dẫn và hữu ích nếu một PriorityQueue nhanh hơn việc phân loại một Danh sách.

Tôi đã thực hiện một số thử nghiệm trên 1 triệu số nguyên ngẫu nhiên. ArrayList được sắp xếp nhanh gấp 2 lần so với việc thoát khỏi PriorityQueue trên máy tính để bàn cũ 7 năm của tôi, JDK6. Mã sau.

public class StackOverflow2 { 

    ArrayList<Integer> generateRandomList(int count, int seed) { 
     ArrayList<Integer> list = new ArrayList<Integer>(count); 
     Random random = new Random(); 
     random.setSeed(seed); 
     for (int i=0; i<count; i++) 
     list.add(Integer.valueOf(random.nextInt())); 

     return list; 
    } 

    long usePriorityQueue(ArrayList<Integer> inList) { 
     long total = 0; 
     long start = System.currentTimeMillis(); 

     PriorityQueue<Integer> pq = new PriorityQueue<Integer>(inList); 
     while (!pq.isEmpty()) { 
     total += pq.remove(); // do something so HotSpot doesn't optimize this away... 
     } 

     long totaltime = System.currentTimeMillis() - start; 
     System.out.println("usePriorityQueue totaltime = " + totaltime); 
     return total; 
    } 

    long useArrayList(ArrayList<Integer> inList) { 
     long total = 0; 
     long start = System.currentTimeMillis(); 

     ArrayList<Integer> list = new ArrayList<Integer>(inList); 
     Collections.sort(list); 
     for (Integer iii : list) { 
     total += iii; // do something 
     } 

     long totaltime = System.currentTimeMillis() - start; 
     System.out.println("useArrayList totaltime = " + totaltime); 
     return total; 
    } 

    public static void main(String[] args) { 
     StackOverflow2 so2 = new StackOverflow2(); 
     ArrayList<Integer> randoms = so2.generateRandomList(1000000, 123456); 

     for (int i=0; i<10; i++) { 
     long upq = so2.usePriorityQueue(randoms); 
     long ual = so2.useArrayList(randoms); 
     } 

    } 
} 

Answer 4

Nếu bạn muốn mã thiếu, bạn luôn có thể chỉ cần sử dụng toArray() và sort:

Integer[] arr = q.toArray(new Integer[1]); 
Arrays.sort(arr,q.comparator()); 

EDIT: Bạn sẽ cần phải gửi sánh cùng để sắp xếp() nếu bạn không sử dụng thứ tự tự nhiên [cố định dòng thứ hai trong mẫu mã]

Answer 5

Bạn có thể sử dụng ArrayList và sau đó sử dụng tìm kiếm nhị phân để tìm vị trí đặt mục. Do đó, việc chèn được đặt hàng

private List<Integer> items = new ArrayList<Integer>();    

while (q.size() != 0) { 
    int index = Collections.binarySearch(items, q.remove()); 
    if (index >= 0) { 
     index++; 
    } else { 
     index = -(index + 1); 
    } 
    items.add(index, q.remove); 
} 

Answer 6

Bạn không thể bỏ trống bản sao của hàng đợi ban đầu?

PriorityQueue<Integer> temp = new PriorityQueue<Integer>(q); 
int[] arr = new int[ q.size() ]; 

int i = 0; 
while (!temp.isEmpty()) { 
    arr[ i ] = temp.remove().intValue(); 
    i++; 
} 

Cũng giống như bạn đã làm, nhưng trên hàng đợi mới. Tôi nghĩ rằng chi phí sao chép hàng đợi ưu tiên là O(n). Hoặc ít nhất cũng nên. Làm trống hàng đợi là O(n log n), vì vậy chi phí cuối cùng là O(n log n), cũng giống như nhận được một mảng rồi sắp xếp nó.

Answer 7

Từ Javadocs cho PriorityQueue:

này lớp và iterator của mình thực hiện tất cả các phương pháp tùy chọn của các giao diện Collection và Iterator. Các Iterator được cung cấp trong phương pháp iterator() không được đảm bảo để đi qua các yếu tố của hàng đợi ưu tiên theo bất kỳ thứ tự cụ thể nào. Nếu bạn cần truyền tải theo thứ tự, hãy xem xét sử dụng Arrays.sort(pq.toArray()).

Tạo mảng, sau đó sắp xếp. Đó là cách được quy định.