Cách lấy số lớn nhất từ ​​số lượng lớn các số?

Question

Tôi muốn lấy 100 phần tử lớn nhất từ ​​danh sách ít nhất 100000000 số.

Tôi có thể sắp xếp toàn bộ danh sách và chỉ lấy 100 phần tử cuối cùng từ danh sách được sắp xếp, nhưng điều đó sẽ rất tốn kém cả về bộ nhớ và thời gian.

Có cách nào dễ dàng, có tính cách nhiệt tình để thực hiện việc này không?

Điều tôi muốn có chức năng sau thay vì sắp xếp thuần túy. Thực ra tôi không muốn lãng phí thời gian để sắp xếp các yếu tố mà tôi không quan tâm.

Ví dụ, đây là chức năng tôi muốn có:

getSortedElements(100, lambda x,y:cmp(x,y)) 

Lưu ý yêu cầu này chỉ dành cho quan điểm hiệu suất.

Answer 1

Module heapq trong thư viện chuẩn cung cấp nlargest() chức năng để làm điều này:

top100 = heapq.nlargest(100, iterable [,key]) 

Nó sẽ không sắp xếp toàn bộ danh sách, vì vậy bạn sẽ không lãng phí thời gian vào các yếu tố bạn don' t cần.

Answer 2

Selection algorithms sẽ trợ giúp tại đây.

Một giải pháp rất dễ là tìm phần tử lớn thứ 100, sau đó chạy qua danh sách chọn các phần tử lớn hơn yếu tố này. Điều đó sẽ cung cấp cho bạn 100 yếu tố lớn nhất. Đây là tuyến tính trong độ dài của danh sách; điều này là tốt nhất có thể.

Có nhiều thuật toán phức tạp hơn. Ví dụ: heap rất phù hợp với vấn đề này. Thuật toán dựa trên heap là n log k trong đó n là độ dài của danh sách và k là số phần tử lớn nhất mà bạn muốn chọn.

Có một cuộc thảo luận về điều này problem trên trang Wikipedia để chọn thuật toán.

Chỉnh sửa: Một áp phích khác đã chỉ ra rằng Python có giải pháp tích hợp cho vấn đề này. Rõ ràng đó là dễ dàng hơn nhiều so với cán của riêng bạn, nhưng tôi sẽ giữ bài đăng này trong trường hợp bạn muốn tìm hiểu về cách các thuật toán như vậy làm việc.

Answer 3

Bạn có thể sử dụng cấu trúc dữ liệu Heap. Một đống sẽ không nhất thiết phải được đặt hàng, nhưng nó là một cách khá nhanh để giữ dữ liệu bán theo thứ tự, và nó có lợi ích của các mục nhỏ nhất luôn luôn là yếu tố đầu tiên trong heap.

Một đống có hai thao tác cơ bản sẽ giúp bạn: Thêm và thay thế.

Về cơ bản những gì bạn làm là thêm các mục vào nó cho đến khi bạn nhận được 100 mục (số N đầu của bạn cho mỗi câu hỏi của bạn). Sau đó, bạn thay thế mục đầu tiên bằng mọi mục mới, miễn là mục mới lớn hơn mục đầu tiên.

Bất cứ khi nào bạn thay thế mục đầu tiên bằng thứ gì đó lớn hơn, mã nội bộ trong heap sẽ điều chỉnh nội dung heap để nếu mục mới không nhỏ nhất, nó sẽ bong bóng vào heap và mục nhỏ nhất sẽ " bong bóng xuống "để các yếu tố đầu tiên, sẵn sàng để được thay thế trên đường đi.

Answer 4

Cách tốt nhất để thực hiện việc này là duy trì hàng đợi ưu tiên được sắp xếp theo heap mà bạn bật ra khi nó có 100 mục nhập trong đó.

Trong khi bạn không quan tâm nếu kết quả được sắp xếp thì rõ ràng là bạn sẽ nhận được điều này miễn phí. Để biết bạn có 100 trang web hàng đầu, bạn cần đặt hàng danh sách các số hàng đầu hiện tại theo thứ tự thông qua một số cấu trúc dữ liệu hiệu quả. Cấu trúc đó sẽ biết tối thiểu, tối đa, và vị trí tương đối của mỗi phần tử theo một cách tự nhiên mà bạn có thể khẳng định vị trí của nó bên cạnh hàng xóm của nó.

Như đã được đề cập trong python, bạn sẽ sử dụng heapq. Trong java PriorityQueue: http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

Answer 5

Đây là một giải pháp tôi đã sử dụng mà không phụ thuộc vào các thư viện và rằng sẽ làm việc trong bất kỳ ngôn ngữ lập trình có các mảng:

initialisation:

Make an array of 100 elements and initialise all elements 
with a low value (less than any value in your input list). 

Initialise an integer variable to 0 (or any value in 
[0;99]), say index_minvalue, that will point to the 
current lowest value in the array. 

Initialise a variable, say minvalue, to hold the current 
lowest value in the array. 

Đối với mỗi giá trị, nói current_value, trong danh sách đầu vào:

if current_value > minvalue 

    Replace value in array pointed to by index_minvalue 
    with current_value 

    Find new lowest value in the array and set index_minvalue to 
    its array index. (linear search for this will be OK as the array 
    is quickly filled up with large values) 

    Set minvalue to current_value 

else 
    <don't do anything!> 

minvalue wil l nhanh chóng nhận được một giá trị cao và do đó hầu hết các giá trị trong danh sách đầu vào sẽ chỉ cần được so sánh với minvalue (kết quả của việc so sánh sẽ hầu như là sai).

Answer 6

Đối với thịt bằm thuật toán trong khán giả: bạn có thể làm điều này với một biến thể đơn giản trên thuật toán Tony Hoare của Find:

find(topn, a, i, j) 
    pick a random element x from a[i..j] 
    partition the subarray a[i..j] (just as in Quicksort) 
    into subarrays of elements <x, ==x, >x 
    let k be the position of element x 
    if k == 0 you're finished 
    if k > topn, call find(topn, a, i, k) 
    if k < topn, call find(topn-k, k, j) 

thuật toán này đặt topn yếu tố lớn nhất vào topn yếu tố đầu tiên của mảng a, mà không cần sắp xếp chúng. Tất nhiên, nếu bạn muốn chúng được sắp xếp, hoặc cho sự đơn giản tuyệt đối, một đống là tốt hơn, và gọi hàm thư viện vẫn tốt hơn. Nhưng đó là một thuật toán tuyệt vời.