thuật toán tối ưu cho trở về giá trị k đầu từ một mảng có độ dài N

Question

Tôi có một mảng của n nổi, và tôi muốn trả lại k đầu (trong trường hợp của tôi n ~ 100, k ~ 10)

Is có một con đường giải pháp tối ưu đã biết cho vấn đề này?

Ai đó có thể cung cấp thuật toán C?

EDIT: thực sự có hai vấn đề ở đây: được sắp xếp và không phân loại. Tôi quan tâm đến unsorted, mà nên được nhanh hơn!

Answer 1

Phương pháp 1

Kể từ khi k là nhỏ, bạn có thể sử dụng phương pháp giải đấu để tìm ra thứ k lớn nhất. Phương pháp này được mô tả trong Nghệ thuật lập trình của Knuth, Tập 3, Trang 212.

Đầu tiên tạo giải đấu trên các phần tử n-k + 2. Một cái gì đó giống như một giải đấu quần vợt loại trực tiếp. Đầu tiên bạn chia thành các cặp và so sánh các thành viên của các cặp (như thể hai người đó đã chơi một trận đấu và một người thua). Sau đó, những người chiến thắng, bạn chia thành cặp một lần nữa và như vậy, cho đến khi bạn có một người chiến thắng. Bạn có thể xem nó như một cái cây, với người chiến thắng ở trên cùng.

Điều này có nghĩa là n-k + 1 so sánh chính xác.

Bây giờ, người chiến thắng của các n-k + 2 này không thể là phần tử lớn thứ k của bạn. Hãy xem xét con đường của nó P lên giải đấu.

Trong số k-2 còn lại bây giờ hãy chọn một, và theo đó, đường dẫn P sẽ cung cấp cho bạn một điểm mới lớn nhất. Về cơ bản bạn sắp xếp làm lại giải đấu với người chiến thắng trước đó được thay thế bằng một trong các yếu tố k-2. Hãy để P là con đường của người chiến thắng mới. Bây giờ hãy chọn một cái khác từ k-3 và đi theo con đường mới và vân vân.

Cuối cùng sau khi bạn thải ra k-2, thay thế lớn nhất bằng -infinity và lớn nhất của giải đấu sẽ là k lớn nhất. Các yếu tố bạn đã bỏ đi là các yếu tố k-1 hàng đầu.

Điều này chiếm tối đa n - k + (k-1) [log (n-k+2)] so sánh để tìm k hàng đầu. Nó sử dụng O (n) bộ nhớ mặc dù.

Xét về số lần so sánh, điều này có thể sẽ đánh bại mọi thuật toán lựa chọn.

Phương pháp 2

Là một thay thế, bạn có thể duy trì một min-đống yếu tố k.

Đầu tiên chèn phần tử k. Sau đó, đối với mỗi phần tử của mảng, nếu nó nhỏ hơn phần tử min của heap, hãy vứt nó đi. Nếu không, xóa-min của heap và chèn phần tử từ mảng.

Cuối cùng, heap sẽ chứa các phần tử k trên cùng. Điều này sẽ mất O(n log k) so sánh.

Tất nhiên, nếu n nhỏ, chỉ cần phân loại mảng phải đủ tốt. Mã sẽ đơn giản hơn.

Answer 2

Hãy xem thuật toán quicksort một phần được thảo luận vào cuối "Efficient selection and partial sorting based on quicksort".

Answer 3

Bạn có thể thực hiện việc này trong O(n) bằng cách sử dụng selection algorithm. Tìm phần tử lớn nhất thứ k với thuật toán phân vùng, sau đó tất cả các phần tử sau khi nó sẽ lớn hơn nó, và đó là số k hàng đầu của bạn.

Nếu bạn cần những đầu trang k theo thứ tự được sắp xếp, bạn có thể sắp xếp chúng theo số O(k log k).

Answer 4

Câu trả lời ngắn gọn: không.

Câu trả lời dài hơn: có, một số giải pháp tối ưu không tương thích lẫn nhau được biết. Nó phụ thuộc vào n, k và các thuộc tính của mảng mà bạn có thể đảm bảo.

Nếu bạn không biết gì về mảng, độ phức tạp thấp hơn rõ ràng là O (n), vì tất cả các phần tử của mảng nguồn phải được kiểm tra xem chúng có nằm trong top 10. Nếu bạn biết gì về nguồn mảng cho phép các phần tử được bỏ qua một cách an toàn, bạn nên sử dụng kiến ​​thức đó.

Tương tự mức độ phức tạp trên là O (n.log (n)) vì bạn luôn có thể chọn tìm câu trả lời bằng cách sắp xếp mảng (O (n.log (n)) và trả về 10 mục đầu tiên (O (1))

Tìm kiếm tuyến tính so sánh từng mục với giá cao nhất thứ mười cho đến nay và chèn vào vị trí phù hợp trong danh sách các mặt hàng được tìm thấy cao nhất nếu cần có độ phức tạp tương tự và các trường hợp tốt nhất và có trường hợp xấu nhất là O (kn) tốt hơn đáng kể so với O (n-bình phương) .Đối với các kích thước bạn ước tính tôi mong đợi phương pháp này hoạt động tốt.

Nếu n lớn hơn nhiều (~ 10000) và k được tăng theo cùng tỷ lệ ly đáng giá khi triển khai thuật toán quickselect. Quickselect thực hiện tốt hơn các yếu tố bạn muốn. Tuy nhiên, nếu k không tăng theo tỷ lệ với n, bạn nên gắn với tìm kiếm tuyến tính. Quickselect & bạn bè sửa đổi mảng ban đầu, vì vậy ít phù hợp hơn nếu bạn không thể thực hiện điều này tại chỗ vì bạn cần có nhiều dung lượng lưu trữ hơn và rất nhiều sao chép mà độ phức tạp của thuật toán không bao gồm.

Nếu n là rất lớn (~ 1e20), bạn sẽ muốn tìm k lớn nhất từ ​​mỗi một số phân vùng của mảng đầu vào và sau đó tìm k lớn nhất từ ​​tổng các kết quả đó, sao cho bạn không cố gắng phân tích nhiều dữ liệu hơn bạn có thể vừa với bộ nhớ tại một thời điểm và để cho phép hoạt động được song song hiệu quả.

Answer 5

nếu bạn có một GPU ưa thích, tôi có thể cho bạn biết cách tính toán số lượng lớn k lớn nhất trong tất cả các trường hợp cùng một lúc, vì vậy hãy trải đều trên một kết cấu "chiều cao" của họ là vị trí dọc theo kết cấu.

Nhưng lưu ý bạn phải đoán phạm vi có thể chấp nhận hoặc biết phạm vi hoặc bạn sẽ không lan sang chi tiết tối đa mà bạn có thể có.

bạn sao chép các vị trí. (bạn sẽ nhận được một 2, nếu có 2 trên đó, 10 nếu có 10 trên nó.) trên tất cả các trường hợp. (chỉ cần nói tất cả của nó trên một kết cấu 8192x8192, 64x64 của những "chiều cao" hộp.) Và bạn cũng bỏ qua các khe với 0 đếm.

sau đó thực hiện phân cấp bổ sung, ngoại trừ bạn làm giống như cây nhị phân, bạn chỉ coi như thứ nguyên 1, vì vậy hãy lấy 2 số trước đó và thêm chúng lại với nhau và tiếp tục thực hiện nó cho mọi nhị phân.

sau đó chúng tôi sử dụng các mips này (đã thu thập số lượng) để khám phá vị trí gần đúng của k, sử dụng tất cả các mips trong quá trình, làm điều này trên một chuỗi cuối cùng, bạn sẽ lấy khối lớn ra khỏi nó, sau đó sử dụng từ từ các mips chi tiết hơn để tìm giá trị mỗi pixel, mà k ngồi tại.

nó có ý nghĩa hơn để làm điều này, nếu nó đã được tất cả instanced một lần nữa, sau đó một sợi của nó cho mỗi khám phá ngưỡng. (chỉ cần nói rằng bạn đang chạy ANN 128x128 lần cùng một lúc, (bất dịch bất dịch ai?) thì nó có ý nghĩa hoàn hảo.

và đạt được chiều cao ngưỡng cho số đó, nhưng gần đúng của nó ... để bạn nhận được xấp xỉ k Bạn có thể thực hiện thêm một ít công việc để có được k chính xác, nhưng trong một kết hợp tương tự, nhưng nếu bạn có thể loại bỏ nó là gần đúng, giống như nếu nó nhận được kích hoạt ~ k hàng đầu, thì bạn có thể Sau đó, đừng lo lắng về nó

Answer 6

Sau đây là một giải pháp thanh lịch dựa trên nền Java với độ phức tạp O (nlogK), nó không hiệu quả nhất nhưng tôi nghĩ nó đủ dễ hiểu. Bạn có thể thay đổi Integer thành Float nếu bạn muốn có một phao giải pháp dựa

import java.util.Arrays; 
import java.util.PriorityQueue; 

public class FindKLargest { 

public static void find(int[] A, int k) { 

    PriorityQueue<Integer> pq = new PriorityQueue<>(k);// Min heap because the element has to be greater 
                 // than the smallest element in the heap in order 
                 // to be qualified to be a member of top k elements. 
    for (int i = 0; i < A.length; i++) { 
     if (i < k) // add until heap is filled with k elements. 
      pq.add(A[i]); 
     else if (pq.peek() < A[i]) { // check if it's bigger than the 
             // smallest element in the heap. 
      pq.poll(); 
      pq.add(A[i]); 
     } 
    } 
    int[] topK = new int[pq.size()]; 
    int index = 0; 
    while (index != k) 
     topK[index++] = pq.poll(); 
    System.out.println(Arrays.toString(topK)); 
} 

public static void main(String[] args) { 
    int[] arr = { 1, -2, -3, -4, -5 }; 
    find(arr, 4); 
} 

}