어떻게 한 번에 발전기로 백분위 수와 랭크를 계산할 수 있습니까?

Question

빌딩 오프 및 이전 질문 : Computing stats on generators in single pass. Python

앞서 언급했듯이 생성기에서 통계를 계산하는 것은 단일 패스에서 매우 빠르고 메모리 효율적입니다. 90 번째 백분위 수와 같은 복잡한 통계 및 순위 속성과 n 번째 작은 것은 종종 표준 편차 및 평균보다 더 복잡한 작업이 필요합니다 (위에서 해결). 이러한 접근법은 데이터를 목록에 넣거나 여러 패스를 계산하는 것이 매우 느리게 진행되는지도/축소 작업 및 대규모 데이터 세트로 작업 할 때 매우 중요합니다.

다음은 순위 순서에 따라 데이터를 찾는 O (n) 퀵 소트 스타일 알고리즘입니다. 중간 값, 백분위 수, 사 분위수 및 십진수를 찾는 데 유용합니다. 데이터가 이미 정렬 될 때 data [n]과 같습니다. 그러나 분할/피벗 될 수있는 목록의 모든 데이터가 필요합니다.

어떻게 생성기로 한 번에 중간 값, 백분위 수, 4 분위수 및 십진수를 계산할 수 있습니까?

전체 목록

import random 

def select(data, n): 
    "Find the nth rank ordered element (the least value has rank 0)." 
    data = list(data) 
    if not 0 <= n < len(data): 
     raise ValueError('not enough elements for the given rank') 
    while True: 
     pivot = random.choice(data) 
     pcount = 0 
     under, over = [], [] 
     uappend, oappend = under.append, over.append 
     for elem in data: 
      if elem < pivot: 
       uappend(elem) 
      elif elem > pivot: 
       oappend(elem) 
      else: 
       pcount += 1 
     if n < len(under): 
      data = under 
     elif n < len(under) + pcount: 
      return pivot 
     else: 
      data = over 
      n -= len(under) + pcount 

Answer 1

당신은 데이터의 큰 부분을 저장해야됩니다 필요가있는 퀵 스타일 알고리즘. 그것을 완전히 저장하기 위해 돈을 벌 수있는 지점까지. 대략적인 알고리즘을 기꺼이 받아 들일 수있는 경우가 아니라면 (데이터가 독립적이라는 것을 알 때 매우 유용 할 수 있습니다).

는 다음과 같은 데이터 세트의 중간을 찾아야 고려 :

0 1 2 3 4 5 6 7 8 9 -1 -2 -3 -4 -5 -6 -7 -8 -9 

평균 분명히 0입니다. 그러나 처음 10 개의 요소 만 보았다면, 그 당시의 최악의 추측입니다! 따라서 n 요소 스트림의 중앙값을 찾으려면 최소한 n/2 개의 후보 요소를 메모리에 유지해야합니다. 그리고 총 크기 n을 모르는 경우 모두 유지해야합니다!

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

가 중간 9을 산출 : - (9)가 후보 적이 없었다 동안, 당신은 또한 요소 (5)를 기억해야

0 _ 1 _ 2 _ 3 _ 4 _ 4 _ 3 _ 2 _ 1 _ 0 

: 여기

모든 홀수 크기의 상황에 대한 중간 값이다 . 일련의 크기가 n 인 모든 요소에 대해이 요소가 중간 값인 연속 크기의 O (2 * n) 계열을 찾을 수 있습니다. 그러나 분명히이 시리즈는 무작위/독립 적이 지 않습니다.

관련 방법에 대한 개요는 "On-line" (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?을 참조하십시오.