개시하다

이어 "리스트와 배열 등에 대해 이른바 자바로 탑-k selection을 효율적으로 구현하는 방법에 대해 1년에 2∼3차례 정도 빈도가 고민된다"며 "무슨 좋은 탑-k selection 시행이 있나.
(도쿄도/34세/남성)
나는 프로그램을 쓰는 과정에서 여러 가지 장소에서 반드시 top-k selection을 해야 하는 상황을 자주 만날 수 있다고 생각한다.물론 RDBMS를 이용하면 ORDER BY sort_column LIMIT k 쉽게 탑-k selection이 가능하지만, RDBMS 외에 탑-k selection을 해야 하는 상황(1년에 2∼3번이면 개인 차이가 크다)은 인생에서 1∼2번 겪을 수 있다.
그러나 최근에는 Guava: Google Core Libraries for Java에 이것top-k selection 설치이 있다는 것을 알았기 때문에 이 실시가 도대체 사용할 수 있고 성능이 얼마나 높은지 궁금해서 기준을 만들어 봤다.그렇다면 성능은 어떨까.

Guva의 top-k selection 설치

이번에 기준 대상인 구바의 top-k selection 알고리즘은 다음과 같이 시행됐다.

List의 크기와 top-k의k를 비교하고, kList의 절반보다 큰 시간Arrays.sort()(즉TimSort))을, top-k

를 구한다.

kInteger.MAX_VALUE / 2 이상이면 Collections.sort()(이것도 TimSort)top-k

상기 어느 하나에도 적용되지 않는 상황에서List에서 얻은Iterator에 대해 다음과 같은 알고리즘으로 top-k를 구한다.

k * 2 크기 버퍼 및

버퍼가 가득 차면quickselect를 사용하여 버퍼를 감소시킵니다

마지막Arrays.sort()

기준 조건

jmh로 측정

처리량 비교Collections.sort() 및 Ordering#leastOf()

Collections.sort() TimSort

설치

비교 조건을 대체적으로 동일하게 하기 위해 Collections.sort() top-k selection을 실시할 때 정렬 후 top-k 부품만 추출하고 새로운 Arrey List를 생성할 때까지 처리를 측정 대상으로 한다

List의 사이즈는 203205120의 3가지 유형

을 시험해 보세요.

Top-k의k(선택한 개수)는List 사이즈에 대한 비례에 따라 계산한다

시험 5가지 비례가 0.05,0.1,0.20.40.8인 모델

다음은 기준 프로그램입니다.

import com.google.common.collect.Ordering;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.infra.Blackhole;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

@State(Scope.Benchmark)
public class GuavaOrderingBenchmark {
    @Param({"0.05", "0.1", "0.2", "0.4", "0.8"})
    public double sortingRatio;

    @Param({"20", "320", "5120"})
    public int size;

    private int k;
    private List<Double> data;

    @Setup
    public void prepare() {
        k = (int) (size * sortingRatio);

        Random r = new Random(12345L);
        data = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            data.add(r.nextDouble());
        }
    }

    @Benchmark
    public void collectionsSort(Blackhole bh) {
        bh.consume(leastK(data, k));
    }

    @Benchmark
    public void guavaOrdering(Blackhole bh) {
        bh.consume(Ordering.natural().leastOf(data, k));
    }

    private List<Double> leastK(List<Double> data, int k) {
        Collections.sort(data);
        return new ArrayList<>(data.subList(0, k));
    }
}

기준 결과

도표로 기준 결과를 봅시다.처리량을 나타내며 로드가 길수록 성능이 좋다는 뜻이다.



어떤 결과를 보든지 간단히Collections.sort() 정렬한 후 top-k selection을 하는 것이 좋다.결과가 너무 뜻밖이어서 나는 매우 놀랐다.구바는 무슨.

총결산

예상한 결과(최고는 구바)를 얻지 못했고, 과도한 구바 참패 상황으로 추가로 기준 획득의 기력을 잃었다.아마 초대형 리스트의 경우 아주 작은k 아래 구바 설치를 이용하면 성능이 더 좋지 않을까.아마