fxQuantile · fxQuantileBy
중앙값, p95, 혹은 어떤 백분위수든 — 전부 정렬하지 않고 선형 시간에 찾아냅니다.
강의
백분위수를 읽는 흔한 방법은 사본을 정렬한 뒤 인덱싱하는 것입니다:
sorted[((n - 1) * q).round()]. 위치 하나를 읽으려고
O(n log n)을 쓰는 셈입니다.
fxQuantile(q, xs)는 같은 값을
quickselect로 반환합니다. quickselect는 그 한 위치가
확정될 때까지만 분할하므로 평균 O(n)이며, 세 값의 중앙값
피벗 덕분에 실제로 흔한 모양인 이미 정렬된 입력과 역순 입력도 선형으로
처리됩니다. 입력은 절대 재배열되지 않고, 작업은 사본에서 일어납니다.
순위는 nearest rank 방식입니다. 정렬된 입력의
((n - 1) * q).round() 인덱스에 있는 값입니다. 따라서
q = 0은 최솟값, 1은 최댓값,
0.5는 중앙값이며 — 길이가 짝수이면 가운데 두 값 중 큰
쪽입니다. 보간은 하지 않습니다. 답은 언제나 입력 중 하나입니다. 빈
입력은 null을 반환하고, [0, 1] 범위를 벗어난
q는 ArgumentError를 던집니다.
fxQuantileBy(q, f, xs)는 숫자 키로 순위를 매기고
원소를 반환합니다 — 중앙값 가격이 아니라 중앙값 가격의 상품을.
f는 원소마다 한 번 실행됩니다. 체인에서는
fx(numbers).quantile(q)와
fx(items).quantileBy(q, f)입니다. fxdart 확장 기능입니다(FxTS에는
없습니다).
데모 1 · 중앙값과 백분위수
데모 2 · quantileBy는 원소를 반환
직접 해 보기
연습: 정렬 후 인덱싱하는 코드를 호출 하나로 바꿔 보세요.