fxTopBy · fxBottomBy

상위 3개, 가장 싼 5개 — 나머지는 정렬하지 않고, 한 번의 순회로, 이미 정렬된 채로.

List<A> fxTopBy<A>(int k, Object? Function(A a) f, Iterable<A> iterable) List<A> fxBottomBy<A>(int k, Object? Function(A a) f, Iterable<A> iterable) Future<List<A>> fxTopByAsync<A>(int k, Object? Function(A a) f, FxAsyncIterable<A> iterable) Future<List<A>> fxBottomByAsync<A>(int k, Object? Function(A a) f, FxAsyncIterable<A> iterable) Fx<T> Fx<T>.topBy(int k, Object? Function(T a) f) // chain (sync) Fx<T> Fx<T>.bottomBy(int k, Object? Function(T a) f) // chain (sync) Future<List<T>> FxAsync<T>.topBy(int k, Object? Function(T a) f) // chain (async) Future<List<T>> FxAsync<T>.bottomBy(int k, Object? Function(T a) f) // chain (async)

강의

순위표를 읽는 흔한 방법은 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 · 체인에서, 동기와 비동기

직접 해 보기

연습: 정렬 후 자르는 코드를 호출 하나로 바꿔 보세요.

관련 항목: sortByDesc — 전체 순서가 필요할 때 · maxBy · minBy — k가 1일 때 · quantile — 앞쪽 k개가 아니라 한 위치