엄청난 양의 숫자 중에서 가장 큰 숫자를 얻는 방법은 무엇입니까?

Question

최소 1000000 개의 숫자 목록에서 최대 100 개의 요소를 가져오고 싶습니다.

전체 목록을 정렬하고 정렬 된 목록의 마지막 100 개 요소 만 가져올 수 있지만 메모리와 시간면에서 매우 비쌉니다.

이 작업을 수행하는 기존의 쉬운 방법이 있습니까?

내가 원하는 것은 순수한 정렬 대신 함수를 따르는 것입니다. 실제로 나는 신경 쓰지 않는 요소를 정렬하는데 낭비하는 시간을 원하지 않습니다.

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

주이 요구 사항은 성능 관점입니다 :

는 예를 들어, 내가 가진하고자하는 기능입니다.

Answer 1

표준 라이브러리의 heapq 모듈은이 작업을 수행 할 수있는 nlargest() 함수를 제공합니다 :

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

당신이 '돈 요소에 시간을 낭비하지 않도록 그것은, 전체 목록을 정렬하지 않습니다 필요 없어.

Answer 2

Selection algorithms이 도움이 될 것입니다.

가장 쉬운 해결책은 100 번째로 큰 요소를 찾은 다음이 요소보다 큰 요소를 선택하여 목록을 실행하는 것입니다. 그것은 당신에게 100 개의 가장 큰 요소를 줄 것입니다. 목록의 길이는 선형입니다. 이것은 최선의 방법입니다.

더 복잡한 알고리즘이 있습니다. 예를 들어 heap은이 문제에 매우 적합합니다. 힙 기반 알고리즘은 n log k입니다. 여기서 n은 목록의 길이이고 k은 선택하려는 가장 큰 요소의 수입니다.

위키 피 디아 페이지에서 problem에 대한 토론이 있습니다.

편집 : 다른 포스터는 파이썬에이 문제에 대한 해결책이 있음을 지적했습니다. 분명히 자신의 것보다 훨씬 쉽습니다. 그러나이 알고리즘이 어떻게 작동하는지 알고 싶다면이 포스트를 보관 해 두십시오.

Answer 3

힙 데이터 구조를 사용할 수 있습니다. 힙을 반드시 정렬 할 필요는 없지만 반 순서 데이터를 유지하는 것은 상당히 빠르며, 가장 작은 항목이 항상 힙의 첫 번째 요소가된다는 이점이 있습니다.

힙에는 추가 및 바꾸기와 같은 두 가지 기본 작업이 있습니다.

기본적으로 100 항목 (질문 당 상위 N 번호)이 될 때까지 항목을 추가하는 것입니다. 그런 다음 새 항목이 첫 번째 항목보다 큰 경우 첫 번째 항목을 모든 새 항목으로 바꿉니다.

첫 번째 항목을 더 큰 것으로 바꿀 때마다 힙의 내부 코드가 힙 내용을 조정하여 새 항목이 가장 작지 않은 경우 힙에 거품이 생기고 가장 작은 항목이 " 버블 다운 (bubble down) "을하여 첫 번째 요소로 보내고, 그 과정에서 교체 할 준비가되었습니다.

Answer 4

이 작업을 수행하는 가장 좋은 방법은 힙 정렬 된 우선 순위 큐를 유지하는 것입니다.

결과가 정렬되는지는 상관 없지만 직관적으로 분명하므로 무료로 얻을 수 있습니다. 상위 100 대를 보유하고 있음을 알기 위해서는 몇 가지 효율적인 데이터 구조를 통해 현재 최상위 숫자 목록을 순서대로 정렬해야합니다. 이 구조는 각 요소의 최소값, 최대 값 및 상대 위치를 자연스럽게 알 수 있으므로 이웃 옆에 위치 할 수 있습니다.

파이썬에서 언급했듯이 heapq를 사용합니다. 자바 PriorityQueue 인에서 : 여기 http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

Answer 5

내가 도서관의 독립이 사용하고있는 솔루션이며, 그 배열이 모든 프로그래밍 언어에서 작동합니다 :

초기화 : 각각에 대해

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. 

을 값을 말하면 입력 목록에서 current_value라고 말합니다.

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 빨리 높은 값을 얻을 수 있으므로 입력 목록에있는 대부분의 값 은 min 값 과 비교하면됩니다 (비교 결과는 대부분 false입니다). 관객의 알고리즘 싫은 사람을 위해

Answer 6

: 당신이 토니 호어의 알고리즘 Find에 간단한 변화와 함께이 작업을 수행 할 수 있습니다이 알고리즘은 배열 a, 의 첫 번째 topn 요소로 가장 큰 topn 요소를두고

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) 

그들을 정렬하지 않고. 물론, 당신이 그것들을 정렬하기를 원한다면, 또는 단순한 단순성을 위해서, 힙이 더 좋으며, 라이브러리 함수를 호출하는 것이 더 좋다. 하지만 멋진 알고리즘입니다.