목록에서 주어진 수의 가장 높은 값 추출하기

Question

웹 페이지에 고정 된 수의 항목을 각각의 무게 (Integer으로 표시)로 표시하려고합니다. 이러한 항목이있는 List는 거의 모든 크기가 될 수 있습니다.

첫 번째 해결책은 Collections.sort()을 수행하고 List을 통해 항목을 하나씩 가져 오는 것입니다. 상위 8 개 항목을 준비하는 데 사용할 수 있지만 좀 더 우아한 해결책이 있습니까?

Answer 1

그냥 Collections.sort(..)으로 이동하십시오. 그것은 충분히 효율적입니다.

이 알고리즘은 n log (n) 성능을 보장합니다.

당신 은 당신이 목록의 일부 독특한 특성을 알고있는 경우 콘크리트의 경우에 대한 보다 효율적으로 뭔가를 구현하기 위해 시도 할 수 있지만,이 정당화 될 수 없다. 또한 데이터베이스에서 목록을 가져 오는 경우 예를 들어 코드 대신 LIMIT &을 주문할 수 있습니다.

Answer 2

max-heap을 사용할 수 있습니다.

데이터가 데이터베이스에서 비롯된 경우 해당 열에 인덱스를 넣고 ORDER BY 및 TOP 또는 LIMIT을 사용하여 표시해야하는 레코드 만 가져옵니다.

Answer 3

또는 priority queue.

Answer 4

아니요. Java의 내장 메소드를 사용하지 마십시오.

목록에서 가장 높은 (또는 가장 낮은) N 개의 항목을 O(n*log(n)) 작업보다 빨리 가져 오는 영리한 방법이 있지만이 솔루션을 직접 코딩해야합니다. 항목 수가 비교적 적게 남아있는 경우 (2 백 개가 넘지 않음) Collections.sort()을 사용하여 정렬 한 다음 상위 N 개의 숫자를 가져 오는 것이 IMO로가는 길입니다. dollar를 사용

Answer 5

: 당신이 Collections.sort()를 사용하여 sort()한다 달러를 사용하지 않고

List<Integer> topTen = $(list).sort().slice(10).toList(); 

, 다음 list.sublist(0, n)를 사용하여 처음 n 항목을 얻을.

Answer 6

이러한 상위 N 개를 추출 할 항목 목록은 크기가 같을 수 있으므로 크기가 클 수 있다고 생각하기 때문에 위의 간단한 대답을 늘릴 수 있습니다 (합리적인 크기의 입력)은 여기에서 작업의 대부분을 제안함으로써 상위 N을 찾는다. 그런 다음 N을 정렬하면 사소하다. 즉 :

Queue<Integer> topN = new PriorityQueue<Integer>(n); 
for (Integer item : input) { 
    if (topN.size() < n) { 
    topN.add(item);   
    } else if (item > topN.peek()) { 
    topN.add(item);   
    topN.poll(); 
    } 
} 

List<Integer> result = new ArrayList<Integer>(n); 
result.addAll(topN); 
Collections.sort(result, Collections.reverseOrder()); 

여기서 힙 (최소 힙)은 최소한 크기가 제한되어 있습니다. 모든 항목에서 힙을 만들 필요가 없습니다.

Answer 7

옵션은 :

1. 길을 따라 발견 된 상위 N 가중치를 유지하는 선형 검색합니다. 어떤 이유에서든 목록 표시가 빠르게 변경되는 등 페이지를 표시 할 때 정렬 결과를 다시 사용할 수 없으면 길이가 긴 목록을 정렬하는 것보다 빠릅니다.

   업데이트 : 선형 검색이 필연적으로 정렬보다 낫습니다. 더 나은 선택 알고리즘을 위해서는 Wikipedia 기사 "Selection_algorithm - Selecting k smallest or largest elements"을 참조하십시오.

2. 수동으로 List (원래 하나 또는 평행 한 것)을 가중치 순으로 정렬하십시오. Collections.binarySearch()과 같은 메서드를 사용하여 각 새 항목을 삽입 할 위치를 결정할 수 있습니다.

3. 각 수정 후 Collections.sort() 호출하여 가중치 순 소트 List (원래의 또는 평행 한)을 유지

   가 배치 변형, 또는 단지 디스플레이하기 전에 (가능하게는 이미 정렬리스트를 정렬 피하기 위해 변경 플래그를 유지).

4. 정렬 된 체중 순서를 유지하는 데이터 구조를 사용하십시오 : priority queue, tree set 등 자신 만의 데이터 구조를 만들 수도 있습니다.

5. 상위 N 개 항목의 두 번째 (가능하면 가중치가 정렬 된) 데이터 구조를 수동으로 유지 관리합니다. 이 데이터 구조는 원본 데이터 구조가 수정 될 때마다 업데이트됩니다. 원본 목록과이 "상위 N 캐시"를 함께 묶는 자체 데이터 구조를 만들 수 있습니다.

Answer 8

얼마나 많은가에 달려 있습니다. n을 총 키 수로 표시하고 m을 표시 할 숫자로 정의 할 수 있습니다. 다음으로 가장 높은 번호의 배열 매번 스캔 O(nlogn)
: - m에 N 사이의 관계는 무엇인가 O(n*m)
그래서 질문은
전체 일을 정렬?
m < log n 인 경우 스캔이 더 효율적입니다.
그렇지 않으면 m >= log n입니다. 이는 정렬이 더 좋습니다. (왜냐하면 m = log n의 엣지의 경우 실제로는 문제가되지 않기 때문에 정렬은 항상 좋은 배열을 정렬하는 이점을 제공합니다.

Answer 9

목록의 크기가 N이고 검색 할 항목 수가 K 개이면 목록에서 Heapify를 호출해야합니다.이 목록은 목록 (배열 등 색인 가능해야 함)을 우선 순위 대기열로 변환합니다 (heapify 함수 참조

). 힙 (최대 항목)의 상단에있는 항목을 가져 오는 것은 O (Ng N) 시간이 걸리므로 전체 시간은

O (N + k lg N)

k가 N보다 훨씬 작은 것으로 가정 할 때 O (N lg N)보다 우수합니다.

Answer 10

정렬 된 배열을 유지하거나 다른 데이터 구조를 사용하는 것은 불가능합니다. O 시간은 큰 배열을 정렬하는 것과 비슷하지만 실제로는 더 효율적입니다.

small_array = big_array.slice(number_of_items_to_find); 
small_array.sort(); 
least_found_value = small_array.get(0).value; 

for (item in big_array) { // needs to skip first few items 
    if (item.value > least_found_value) { 
    small_array.remove(0); 
    small_array.insert_sorted(item); 
    least_found_value = small_array.get(0).value; 
    } 
} 

small_array는 Object [] 일 수 있으며 배열을 실제로 제거하고 삽입하는 대신 스와핑으로 내부 루프를 수행 할 수 있습니다.