Xin chào. Tôi có một mảng rất lớn và tôi muốn tìm giá trị lớn nhất thứ N. Trivially tôi có thể sắp xếp các mảng và sau đó lấy phần tử thứ N nhưng tôi chỉ quan tâm đến một phần tử vì vậy có lẽ một cách tốt hơn so với phân loại toàn bộ mảng ...Tìm mục thứ N của danh sách chưa phân loại mà không cần sắp xếp danh sách
Sorting sẽ đòi hỏi O (nlogn) thời gian chạy ở mức tối thiểu - Có rất hiệu quả selection algorithms mà có thể giải quyết vấn đề của bạn trong thời gian tuyến tính.
Partition-based selection (đôi khi Quick select), dựa trên ý tưởng quicksort (phân hoạch đệ quy), là giải pháp tốt (xem liên kết cho mã giả + Another example).
Sử dụng heapsort. Nó chỉ đơn đặt hàng một phần danh sách cho đến khi bạn rút ra các yếu tố.
Cố gắng tìm phần tử n/2 - Yêu cầu O (nlogn)! – Dario
Bạn có thể lặp lại toàn bộ chuỗi duy trì danh sách 5 giá trị lớn nhất bạn tìm thấy (đây sẽ là O (n)). Điều đó đang được nói rằng tôi nghĩ rằng nó sẽ chỉ đơn giản hơn để sắp xếp danh sách.
Nhưng khi nó không phải là thứ năm nhưng yếu tố thứ n, bạn sẽ có O (n²) mà thậm chí còn tệ hơn là phân loại. – Dario
Tôi cho rằng bạn muốn giữ một danh sách N giá trị lớn nhất. Nhưng N không thể quá lớn trong trường hợp đó. –
Bạn về cơ bản muốn tạo danh sách "top-N" và chọn danh sách ở cuối danh sách đó.
Vì vậy, bạn có thể quét mảng một lần và chèn vào danh sách trống khi mục LargeArray lớn hơn mục cuối cùng của danh sách trên cùng N, sau đó thả mục cuối cùng.
Sau khi bạn quét xong, hãy chọn mục cuối cùng trong danh sách N trên cùng của bạn.
Một ví dụ cho ints và N = 5:
int[] top5 = new int[5]();
top5[0] = top5[1] = top5[2] = top5[3] = top5[4] = 0x80000000; // or your min value
for(int i = 0; i < largeArray.length; i++) {
if(largeArray[i] > top5[4]) {
// insert into top5:
top5[4] = largeArray[i];
// resort:
quickSort(top5);
}
}
Như mọi người đã nói, bạn có thể đi bộ danh sách sau khi theo dõi K giá trị lớn nhất. Nếu K lớn, thuật toán này sẽ gần với O (n).
Tuy nhiên, bạn có thể lưu trữ giá trị lớn nhất Kth của bạn dưới dạng cây nhị phân và thao tác trở thành O (n log k).
Theo Wikipedia, đây là thuật toán lựa chọn tốt nhất:
function findFirstK(list, left, right, k)
if right > left
select pivotIndex between left and right
pivotNewIndex := partition(list, left, right, pivotIndex)
if pivotNewIndex > k // new condition
findFirstK(list, left, pivotNewIndex-1, k)
if pivotNewIndex < k
findFirstK(list, pivotNewIndex+1, right, k)
phức tạp của nó là O (n)
Một quicksort sửa đổi đơn giản hoạt động rất tốt trong thực tế. Nó có thời gian chạy trung bình tỷ lệ thuận với N (mặc dù trường hợp xấu nhất thời gian chạy may mắn là O (N^2)).
Tiến hành như một quicksort. Chọn một giá trị pivot ngẫu nhiên, sau đó truyền qua các giá trị của bạn và xem liệu chúng có nằm trên hay dưới giá trị trục xoay đó và đặt chúng thành hai thùng dựa trên so sánh đó. Trong quicksort bạn sau đó đệ quy sắp xếp mỗi trong hai thùng. Nhưng đối với tính toán giá trị cao nhất N-th, bạn chỉ cần sắp xếp MỘT trong các thùng .. dân số của mỗi thùng cho bạn biết bin nào chứa giá trị cao nhất thứ n của bạn. Vì vậy, ví dụ nếu bạn muốn giá trị cao nhất 125, và bạn sắp xếp thành hai thùng có 75 trong thùng "cao" và 150 trong thùng "thấp", bạn có thể bỏ qua thùng cao và chỉ tiến hành tìm 125-75 = 50 giá trị cao nhất trong thùng rác một mình.
Heap là cấu trúc dữ liệu tốt nhất cho hoạt động này và Python có một thư viện tích hợp tuyệt vời để thực hiện điều này, được gọi là heapq.
import heapq
def nth_largest(n, iter):
return heapq.nlargest(n, iter)[-1]
Ví dụ Cách sử dụng:
>>> import random
>>> iter = [random.randint(0,1000) for i in range(100)]
>>> n = 10
>>> nth_largest(n, iter)
920
kết quả Xác nhận bằng cách phân loại:
>>> list(sorted(iter))[-10]
920
Điều này hoạt động tốt (thời gian tuyến tính) nếu bạn muốn (các) mục lớn nhất hoặc nhỏ nhất thứ n, trong đó n là hằng số. Nếu n là một nửa độ dài của danh sách (tức là bạn muốn có trung vị), thì đây vẫn là thời gian O (nlogn). – mgold
Đây không phải là một giải pháp tại chỗ, Quickselect sẽ không thêm O (n) bộ nhớ bổ sung như giải pháp này sẽ. Vì vậy, đối với mảng rất lớn như câu hỏi hỏi, điều này có lẽ sẽ không hiệu quả nhất. – db1234
Bạn có thể thử các trung bình của phương pháp trung vị - tốc độ của nó là O (N).
Một điều bạn nên làm nếu điều này nằm trong mã sản xuất là thử nghiệm với các mẫu dữ liệu của bạn. Ví dụ: Ví dụ, bạn có thể xem xét 1000 hoặc 10000 mảng 'lớn' và mã hóa phương thức chọn nhanh từ công thức. Bản chất đã biên soạn được sắp xếp và tối ưu hóa phần nào ẩn và không ngừng phát triển của nó, làm cho nó nhanh hơn so với một phương pháp chọn nhanh bằng cách sử dụng phương pháp chọn nhanh trên các bộ dữ liệu nhỏ đến vừa (< 1.000.000 yếu tố). Ngoài ra, bạn có thể thấy khi bạn tăng kích thước của mảng vượt quá số lượng đó, bộ nhớ được xử lý hiệu quả hơn trong mã gốc và lợi ích vẫn tiếp tục. Vì vậy, ngay cả khi quickselect là O (n) so với O được sắp xếp (nlogn), điều đó không tính đến việc có bao nhiêu mã máy thực sự xử lý từng phần tử n, bất kỳ tác động nào lên pipelining, sử dụng bộ nhớ cache của bộ xử lý và những thứ khác mà người tạo và người bảo trì được sắp xếp sẽ nướng vào mã python.
Liên kết đẹp. Tôi tin rằng điều này là tốt nhất. –
Thật không may, liên kết "Một ví dụ khác" bây giờ dẫn đến một trang web được bảo vệ tại MIT, rằng bạn phải có quyền truy cập. – Beel
[NumPy có tích hợp này] (http://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.partition.html), mặc dù nó là loại phụ thuộc kỳ lạ để kéo vào nếu bạn ' không sử dụng chức năng ndarray của nó. – user2357112