fxTopBy · fxBottomBy
상위 3개, 가장 싼 5개 — 나머지는 정렬하지 않고, 한 번의 순회로, 이미 정렬된 채로.
강의
순위표를 읽는 흔한 방법은 sortByDesc(f, xs).take(k)입니다.
입력 전체를 정렬하고, k개를 남기고, 나머지는 버립니다.
fxTopBy(k, f, xs)는 같은 k개 원소를
한 번의 순회로 반환하며, 이 순회는
k 크기의 경계만 유지합니다 — 메모리는 입력이 아니라 k에 비례하고, 경계
밖의 원소는 붙잡아 두지 않습니다. fxBottomBy(k, f, xs)는
그 거울상으로, 키가 가장 작은 k개를 작은 것부터
반환합니다.
결과에는 두 번째 순회가 필요 없습니다. 정렬되어
있고 — topBy는 내림차순, bottomBy는
오름차순 — 동점은 먼저 본 원소가 이깁니다. 나중에 온
원소의 키가 경계의 가장 약한 키와 같기만 하면 그것을 밀어내지 못하고,
결과 안의 같은 키들은 입력 순서를 유지합니다.
k <= 0이면 빈 리스트, 입력 길이를 넘는
k는 모든 원소를 정렬해 반환합니다. 키는
sortBy와 똑같이 비교되므로
어떤 Comparable이든 됩니다.
경계는 삽입으로 유지되므로 최악의 경우 O(n·k)입니다. 큰
입력에서 작은 k를 고를 때 쓰는 도구이고,
k가 입력 길이에 가까워지면 정렬하세요. 동기 체인의
fx(xs).topBy(k, f)는 단계라서
Fx를 반환하므로 체인을 계속 이어 갈 수 있습니다. 반면
FxAsync.topBy와 fxTopByAsync 계열은
Future<List>로 체인을 끝내며, 키 함수는 동기
그대로입니다. fxdart 확장 기능입니다(FxTS에는 없습니다) — Python의
heapq.nlargest와 같은 모양입니다.
데모 1 · 순서, 동점과 k
데모 2 · 체인에서, 동기와 비동기
직접 해 보기
연습: 정렬 후 자르는 코드를 호출 하나로 바꿔 보세요.