[PYTHON] 목록을 정렬하지 않고 정렬되지 않은 목록의 N 번째 항목 찾기

목록을 정렬하지 않고 정렬되지 않은 목록의 N 번째 항목 찾기

이봐. 나는 매우 큰 배열을 가지고 있으며 N 번째로 큰 값을 찾고 싶습니다. 사소한 것은 배열을 정렬 한 다음 N 번째 요소를 가져올 수 있지만 한 요소에만 관심이 있기 때문에 전체 배열을 정렬하는 것보다 더 좋은 방법 일 것입니다.

해결법

1. ==============================

   1.정렬에는 최소한 O (nlogn) 런타임이 필요합니다. 선형 시간에 문제를 해결할 수있는 매우 효율적인 선택 알고리즘이 있습니다.

   정렬에는 최소한 O (nlogn) 런타임이 필요합니다. 선형 시간에 문제를 해결할 수있는 매우 효율적인 선택 알고리즘이 있습니다.

   quicksort (재귀 분할)에 기반을 둔 파티션 기반 선택 (때로는 빠른 선택)은 좋은 해결책입니다 (의사 코드 + 다른 예를위한 링크 참조).

2. ==============================

   2.힙 (heap)은이 연산을위한 최상의 데이터 구조이며, 파이썬은 heapq라고 불리는이 라이브러리를 내장하고 있습니다.

   힙 (heap)은이 연산을위한 최상의 데이터 구조이며, 파이썬은 heapq라고 불리는이 라이브러리를 내장하고 있습니다.

   import heapq
   
   def nth_largest(n, iter):
       return heapq.nlargest(n, iter)[-1]
   

   사용 예 :

   >>> import random
   >>> iter = [random.randint(0,1000) for i in range(100)]
   >>> n = 10
   >>> nth_largest(n, iter)
   920
   

   정렬하여 결과 확인 :

   >>> list(sorted(iter))[-10]
   920
   

3. ==============================

   3.찾은 5 개의 가장 큰 값 (O (n)이 될 것입니다)의 목록을 유지하면서 전체 시퀀스를 반복 할 수 있습니다. 그것은 목록을 정렬하는 것이 더 간단 할 것이라고 나는 말했습니다.

   찾은 5 개의 가장 큰 값 (O (n)이 될 것입니다)의 목록을 유지하면서 전체 시퀀스를 반복 할 수 있습니다. 그것은 목록을 정렬하는 것이 더 간단 할 것이라고 나는 말했습니다.

4. ==============================

   4.간단한 수정 된 퀵 정렬은 실제로 잘 작동합니다. 평균 실행 시간은 N에 비례합니다 (최악의 운 행 시간은 O (N ^ 2) 임에도 불구하고).

   간단한 수정 된 퀵 정렬은 실제로 잘 작동합니다. 평균 실행 시간은 N에 비례합니다 (최악의 운 행 시간은 O (N ^ 2) 임에도 불구하고).

   퀵 소트처럼 진행하십시오. 무작위로 피벗 값을 선택한 다음 값을 스트리밍하여 해당 피벗 값 위 또는 아래에 있는지 확인하고 비교를 기반으로 두 개의 저장소에 넣습니다. 그런 다음 quicksort에서이 두 개의 bin을 재귀 적으로 정렬합니다. 그러나 N 번째로 높은 값 계산을 위해서는 하나의 빈을 정렬하기 만하면됩니다. 각 빈의 모집단은 n 번째로 높은 값을 가진 빈을 알려줍니다. 따라서 예를 들어 125 번째로 높은 값을 원하면 "높은"빈에 75, "낮음"빈에 150을 갖는 두 개의 빈으로 정렬하면 높은 빈을 무시하고 125-75 = 낮은 빈에서만 50 번째로 높은 값.

5. ==============================

   5.Median of Medians 방법을 시도해 볼 수 있습니다. 속도는 O (N)입니다.

   Median of Medians 방법을 시도해 볼 수 있습니다. 속도는 O (N)입니다.

6. ==============================

   6.힙을 사용하십시오. 요소를 그릴 때까지 부분적으로 만 목록을 정렬합니다.

   힙을 사용하십시오. 요소를 그릴 때까지 부분적으로 만 목록을 정렬합니다.

7. ==============================

   7.기본적으로 "상위 N"목록을 생성하고 그 목록의 끝에있는 목록을 선택하려고합니다.

   기본적으로 "상위 N"목록을 생성하고 그 목록의 끝에있는 목록을 선택하려고합니다.

   따라서 배열을 한 번 스캔하여 largeArray 항목이 상위 N 목록의 마지막 항목보다 큰 경우 빈 목록에 삽입 한 다음 마지막 항목을 삭제할 수 있습니다.

   검사가 끝나면 상위 N 목록에서 마지막 항목을 선택하십시오.

   ints 및 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);
       }
   }
   

8. ==============================

   8.사람들이 말했듯이 K 최대 값을 추적하면 목록을 한 번 볼 수 있습니다. K가 크면이 알고리즘은 O (n2)에 가깝습니다.

   사람들이 말했듯이 K 최대 값을 추적하면 목록을 한 번 볼 수 있습니다. K가 크면이 알고리즘은 O (n2)에 가깝습니다.

   그러나 K 번째로 큰 값을 이진 트리로 저장할 수 있으며 연산은 O (n log k)가됩니다.

   위키 피 디아 (Wikipedia)에 따르면, 이것은 최고의 선택 알고리즘이다.

    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)
   

   그것의 복잡성은 O (n)

9. ==============================

   9.이것이 프로덕션 코드에 포함되어 있다면해야 할 한 가지는 데이터 샘플을 테스트하는 것입니다. 예를 들어, 1000 또는 10000 개의 요소 '대형'배열을 고려하고 레시피에서 quickselect 메소드를 코딩 할 수 있습니다.

   이것이 프로덕션 코드에 포함되어 있다면해야 할 한 가지는 데이터 샘플을 테스트하는 것입니다. 예를 들어, 1000 또는 10000 개의 요소 '대형'배열을 고려하고 레시피에서 quickselect 메소드를 코딩 할 수 있습니다.

   정렬 된 컴파일 된 특성과 다소 숨겨진 지속적으로 진화하는 최적화로 인해 중소 규모 데이터 세트 (<1,000,000 개 요소)에 대한 python으로 작성된 quickselect 방법보다 빠릅니다. 또한 배열의 크기를 그 이상으로 늘리면 메모리가 원시 코드에서보다 효율적으로 처리되고 이점이 계속 유지 될 수 있습니다.

   따라서 quickselect가 O (n) vs sorted의 O (nlogn) 일지라도 각 n 요소를 처리하는 실제 기계 코드 명령어의 수를 고려하지 않고 파이프 라이닝에 미치는 영향, 프로세서 캐시 사용 및 기타 작성자와 정렬 자의 관리자가 파이썬 코드를 굽습니다.

from https://stackoverflow.com/questions/1034846/finding-nth-item-of-unsorted-list-without-sorting-the-list by cc-by-sa and MIT license