Java - Tìm kiếm thứ gì đó nhanh hơn PriorityQueue

Question

Tôi đang sử dụng java trên một lượng lớn dữ liệu.

[i cố gắng đơn giản hóa vấn đề càng nhiều càng tốt]

Thật sự tôi có một lớp học nhỏ (Element) có chứa một KEY int và một trọng lượng gấp đôi (với thu khí & setters).

Tôi đã đọc rất nhiều các đối tượng này từ một tệp và tôi phải có được các đối tượng M tốt nhất (trọng lượng nhất).

Thực ra tôi đang sử dụng PriorityQueue với một Trình So sánh được viết để so sánh hai Phần tử và nó hoạt động nhưng quá chậm.

Bạn có biết (tôi biết bạn làm) cách nào nhanh hơn để làm điều đó không?

Cảm ơn bạn

Answer 1

Hàng đợi ưu tiên dựa trên heap là cấu trúc dữ liệu tốt cho vấn đề này. Cũng giống như kiểm tra tính chính xác, xác minh rằng bạn đang sử dụng hàng đợi chính xác.

Nếu bạn muốn các vật có trọng lượng cao nhất, hãy sử dụng min -queue — trong đó phần trên cùng của heap là mục nhỏ nhất. Thêm mọi mục vào một hàng đợi tối đa và kiểm tra các mục M hàng đầu khi hoàn thành không hiệu quả.

Đối với mỗi mục, nếu có ít hơn M mục trong hàng đợi, hãy thêm mục hiện tại. Nếu không, hãy nhìn vào đỉnh của đống. Nếu nó nhỏ hơn mục hiện tại, hãy loại bỏ nó và thêm mục hiện tại để thay thế. Nếu không, hãy hủy mục hiện tại. Khi tất cả các mục đã được xử lý, hàng đợi sẽ chứa các mục có trọng số cao nhất là M.

Một số heap có API tắt để thay thế đỉnh của heap, nhưng Java Queue thì không. Mặc dù vậy, độ phức tạp lớn-O là như nhau.

Answer 2

Nếu M là nhỏ phù hợp, thì sắp xếp tất cả các thành phần có thể lãng phí nhiều thời gian tính toán. Bạn chỉ có thể đặt các đối tượng M đầu tiên vào hàng đợi ưu tiên (ví dụ: phần tử heap, phần tử tối thiểu ở trên cùng) và sau đó lặp qua các phần tử còn lại: mỗi lần một phần tử lớn hơn đỉnh của phần tử, xóa đầu và đẩy mới yếu tố vào heap. Ngoài ra, bạn có thể lặp lại toàn bộ mảng một lần để tìm giá trị ngưỡng thống kê mà bạn có thể chắc chắn có nhiều hơn M đối tượng có giá trị lớn hơn (sẽ yêu cầu một số giả định liên quan đến các giá trị, vd: nếu chúng là phân phối chuẩn). Sau đó, bạn có thể giới hạn sắp xếp cho tất cả các phần tử có giá trị lớn hơn.

Answer 3

@Tnay: Bạn có một điểm không thực hiện so sánh. Thật không may, mã ví dụ của bạn vẫn thực hiện. Điều này giải quyết vấn đề:

public int compare(ListElement i, ListElement j) { 
    return i.getValue() - j.getValue(); 
} 

Bên cạnh đó, không phải bạn, cũng không Biggs so sánh phương pháp là đúng đúng, vì họ không bao giờ trở về 0. Điều này có thể là một vấn đề với một số thuật toán phân loại, đó là một lỗi rất khó khăn, vì nó sẽ chỉ xuất hiện nếu bạn chuyển sang triển khai khác.

Từ the Java docs:

Các implementor phải đảm bảo rằng sgn (so sánh (x, y)) == -sgn (so sánh (y, x)) với mọi x và y.

Điều này có thể hoặc không thể thực hiện tăng tốc liên tục đáng kể. Nếu bạn kết hợp điều này với giải pháp của erickson, nó có thể sẽ khó làm nhanh hơn (tùy thuộc vào kích thước của M). Nếu M là rất lớn, giải pháp hiệu quả nhất có lẽ là sắp xếp tất cả các phần tử bằng cách sử dụng qsort dựng sẵn của Java trên một mảng và cắt bỏ một đầu của mảng ở cuối.

Answer 4

Ngoài thuật toán "peek at the top of the heap" được đề xuất, thuật toán này cung cấp cho bạn độ phức tạp O (n log m) để nhận được nhiều mục hàng đầu, sau đây là hai giải pháp khác.

Giải pháp 1: Sử dụng vùng đệm Fibonacci.

Việc triển khai PriorityQueue của JDK là một đống nhị phân cân bằng. Bạn sẽ có thể ép thêm hiệu suất từ ​​việc thực hiện Fibonacci heap. Nó sẽ có thời gian chèn không đổi được khấu hao, trong khi chèn vào một đống nhị phân có độ phức tạp Ω (log n) theo kích thước của vùng heap. Nếu bạn làm điều đó cho mọi phần tử, thì bạn đang ở Ω (n log n). Việc tìm kiếm trên cùng của n mục bằng cách sử dụng một đống heap có độ phức tạp O (n + m log n). Kết hợp điều này với gợi ý để chỉ bao giờ chèn các phần tử m vào heap, và bạn có O (n + m log m), gần với thời gian tuyến tính như bạn sẽ nhận được.

Giải pháp 2: Traverse danh sách M lần.

Bạn sẽ có thể lấy phần tử lớn thứ k trong một bộ trong thời gian O (n). Chỉ cần đọc mọi thứ vào danh sách và thực hiện như sau:

kthLargest(k, xs) 
    Pick a random pivot element p from the list 
    (the first one will do if your list is already random). 
    Go over the set once and group it into two lists. 
    Left: smaller than p. 
    Right: Larger or equal to p. 
    If the Right list is shorter than k, return kthLargest(k - right.size, Left) 
    If the Right list is longer than k, return kthLargest(k, right) 
    Otherwise, return p. 

Điều đó cho bạn thời gian O (n). Chạy thời gian đó m, bạn sẽ có thể nhận được các đối tượng top-m trong bộ của bạn trong thời gian O (nm), mà sẽ được nghiêm ngặt ít hơn n log n cho đủ lớn n và đủ nhỏ m. Ví dụ, nhận được top-10 trên một triệu mục sẽ mất một nửa miễn là sử dụng hàng đợi ưu tiên heap nhị phân, tất cả những thứ khác bằng nhau.