목차
1. Collector 인터페이스 분석&튜닝
Collector 인터페이스는 리듀싱 연산을 어떻게 구현할지 제공하는 메서드 집합으로 구성된다. 기존에 표준 라이브러리를 통해 제공되는 Collector로도 가능하지만 직접 커스텀한 Collector를 만들어 리듀싱 연산을 제공할수도 있다.
소수 분류 문제를 커스텀 Collector 구현으로 성능 개선을 해보자.
Collector 인터페이스 분석
public interface Collector<T, A, R> {
Supplier<A> supplier();
BiConsumer<A, T> accumulator();
BinaryOperator<A> combiner();
Function<A, R> finisher();
Set<Characteristics> characteristics();
}
Java
복사
•
<T, A, R>
◦
T : 수집될 스트림 항목의 제네릭 형식이다.
◦
A: 누적자, 즉 수집 과정에서 중간 결과를 누적하는 객체의 형식이다.
◦
R: 수집 연산 결과 객체의 형식이다.
•
Supplier<A> supplier();
: 비어있는 새로운 결과 컨테이너를 제공하는 Supplier를 반환해야 한다. 즉, 수집 과정에서 빈 누적자 인스턴스를 만드는 파라미터가 없는 함수이다.
public Supplier<List<T>> supplier() {
return () -> new ArrayList<T>();
//return ArrayList::new; //메서드 참조로 제공할 수도 있다.
}
Java
복사
•
BiConsumer<A, T> accumulator();
: 리듀싱 연산을 수행하는 함수를 반환한다. 스트림에서 n번째 요소를 탐색할 때 두 인수, 즉 누적자(스트림의 첫 n-1개 항목을 수집한 상태)와 n번째 요소를 함수에 적용한다. 함수의 반환값은 void로 요소를 탐색하며 적용하는 함수에 의해 누적자 내부상태가 바뀌기에 누적자를 단정할 수 없다.
public BiConsumer<List<T>, T> accumulator() {
return (list, item) -> list.add(item);
//return List::add;
}
Java
복사
•
BinaryOperator<A> combiner();
: 리듀싱 연산에서 사용할 함수를 반환한다. 스트림의 서로 다른 서브 파트를 병렬로 처리할 때 누적자가 이 결과를 어떻게 처리할지 정의한다. 우리가 자주 사용하는 toList의 combiner는 대략적으로 다음과 같이 구현되어 있다.
public BinaryOperator<List<T>> combiner() {
return (list1, list2) -> {
list1.addAll(list2);
return list1;
}
}
Java
복사
•
Function<A, R> finisher();
: 스트림 탐색을 끝내고 누적자 객체를 최종 결과로 변환하며 누적 과정을 끝낼 때 호출할 함수를 반환하는 메서드. 누적자 객체가 이미 최종 결과인 경우도 있는데 이런 경우 항등 함수를 반환하면 된다.
public Function<A, R> finisher(){
return Function.identity();
}
Java
복사
•
Set<Characteristics> characteristics();
: 컬렉션의 연산을 정의하는 Characteristics 형식의 불변 집합을 반환한다. 이 열거 타입은 스트림을 병렬로 리듀스할지, 병렬로 리듀스한다면 어떤 최적화를 선택해야 할 지에 대한 힌트를 제공한다.
◦
UNORDERED
▪
리듀싱 결과가 스트림 요소의 방문 순서 및 누적 순서에 영향을 받지 않는다.
◦
CONCURRENT
▪
다중 스레드에서 accumulator 함수를 동시에 호출할 수 있고 이 컬렉터는 스트림의 병렬 리듀싱을 수행할 수 있다. 컬렉터의 플래그에 UNORDERED를 함께 설정하지 않은 경우 소스가 정렬 되어있지 않은 상황에서만 병렬 리듀싱을 수행할 수 있다.
◦
IDENTITY_FINISH
▪
finisher 메서드가 반환하는 메서드는 단순히 identity를 적용할 뿐이기에 이를 생략할 수 있다. 따라서 리듀싱 과정의 최종 결과로 누적자 객체를 바로 사용할 수 있다. 또한 누적자 A를 결과 R로 안전하게 형변환 할 수 있다.
Custom Collector 구현해서 성능 개선하기
전달해준 숫자를 최대값으로 그 사이의 값 중 소수 목록과 그외 목록을 분류해서 반환해주는 기능을 만든다고 하자. 이 때 별도의 Custom Collector를 구현하지 않고, 이 기능을 구현한다면 대략 이런식으로 작성할 수 있을 것 같다.
public static Map<Boolean, List<Integer>> partitionPrimes(int n) {
return IntStream.rangeClosed(2, n).boxed()
.collect(partitioningBy(Main::isPrime));
}
private static boolean isPrime(Integer candidate) {
int candidateRoot = (int) Math.sqrt((double) candidate);
return IntStream.rangeClosed(2, candidateRoot)
.noneMatch(i -> candidate % i == 0);
}
Java
복사
이 로직에 대한 성능을 테스트해보자.
public static void main(String[] args) {
long fastest = Long.MAX_VALUE;
for (int i = 0; i < 10; i++) {
long start = System.nanoTime();
partitionPrimes(1_000_000);
long duration = (System.nanoTime() - start) / 1_000_000;
if (duration < fastest) {
fastest = duration;
}
}
System.out.println("Fastest execution done in " + fastest + " msecs");
}
Java
복사
실행결과는 우측과 같은데 이러한 소요시간을 더 줄여보고 싶다.
Step 1. 소수로만 나누기
제수(devisor)가 소수가 아니면 소용 없다는 점을 이용해 제수를 현재 숫자 이하에서 발견한 소수로 제한할 수 있다. 그래서 isPrime 메서드가 매개변수로 지금까지 발견한 소수 리스트를 전달해서 개선할 수 있다.
public static boolean isPrime(List<Integer> primes, Integer candidate) {
return primes.stream().noneMatch(i -> candidate % i == 0);
}
Java
복사
여기서 대상 숫자의 제곱근보다 작은 소수만 사용하도록 해 코드를 최적화 할 수 있다. 그리고 소수가 대상의 루트보다 큰 경우 검사를 멈추도록 해야한다. takeWhile 메서드를 이용해 이를 구현하자.
public static boolean isPrime(List<Integer> primes, Integer candidate) {
int candidateRoot = (int) Math.sqrt((double) candidate);
return primes.stream()
.takeWhile(i -> i <= candidateRoot)
.noneMatch(i -> candidate % i == 0);
}
Java
복사
참고: JDK 9 이하라서 takeWhile이 없는 경우 다음과 같이 직접 구현해 사용하면 된다. public static <A> List<A> takeWhile(List<A> list, Predicate<A> p) {
int i = 0;
for (A item : list) {
if(!p.test(item)) {
return list.subList(0, i);
}
i++;
}
return list;
}
public static boolean isPrime(List<Integer> primes, Integer candidate) {
int candidateRoot = (int) Math.sqrt((double) candidate);
return takeWhile(primes, i -> i <= candidateRoot)
.stream()
.noneMatch(i -> candidate % i == 0);
}
Java
복사
Step 2. Custom Collector 구현하기
public class PrimNumberCollector implements Collector<Integer, Map<Boolean, List<Integer>>, Map<Boolean, List<Integer>>> {
/**
* 소수와 비소수를 수집하는 두 개의 리스트를 각각 true, false 키와 빈 리스트로 초기화를 한다.
*/
@Override
public Supplier<Map<Boolean, List<Integer>>> supplier() {
return () -> new HashMap<>() {{
put(true, new ArrayList<>());
put(false, new ArrayList<>());
}};
}
/**
* 스트림의 요소를 수집한다.
* 누적 리스트 acc에서 isPrime 메서드 결과에 따라 소수,비소수 목록을 꺼내 candidate 값을 추가 한다.
*/
@Override
public BiConsumer<Map<Boolean, List<Integer>>, Integer> accumulator() {
return (Map<Boolean, List<Integer>> acc, Integer candidate) ->
acc.get(isPrime(acc.get(true), candidate)).add(candidate);
}
private static boolean isPrime(List<Integer> primes, int candidate) {
int candidateRoot = (int) Math.sqrt((double) candidate);
return primes.stream()
.takeWhile(i -> i <= candidateRoot)
.noneMatch(i -> candidate % i == 0);
}
/**
* 알고리즘이 순차적이기에 실제 병렬로 사용할 수는 없지만, 학습용으로 만든 메서드. 각 스레드에서 만든 누적 결과를 merge하여 반환한다.
*/
@Override
public BinaryOperator<Map<Boolean, List<Integer>>> combiner() {
return (Map<Boolean, List<Integer>> map1, Map<Boolean, List<Integer>> map2)-> {
map1.get(true).addAll(map2.get(true));
map1.get(false).addAll(map2.get(false));
return map1;
};
}
/**
* accumulator의 형식이 컬렉터 결과 형식과 같기에 별도의 변환 과정이 필요 없는 경우 항등 함수를 반환하도록 구현한다.
*/
@Override
public Function<Map<Boolean, List<Integer>>, Map<Boolean, List<Integer>>> finisher() {
return Function.identity();
}
/**
* 알고리즘이 순차적이기에 CONCURRENT, UNORDERED도 아니지만
* IDENTITY_FINISH이기에 하나의 열거 타입을 가지는 셋을 불변 타입으로 만들어 반환한다.
*/
@Override
public Set<Characteristics> characteristics() {
return Collections.unmodifiableSet(EnumSet.of(IDENTITY_FINISH));
}
}
Java
복사
이제 직접 만든 Custom Collector를 이용해서 성능을 비교해보자.
static Map<Boolean, List<Integer>> partitionPrimesWithCustomCollector(int n) {
return IntStream.rangeClosed(2, n).boxed()
.collect(new PrimNumberCollector());
}
public static void main(String[] args) {
long fastest = Long.MAX_VALUE;
for (int i = 0; i < 10; i++) {
long start = System.nanoTime();
partitionPrimesWithCustomCollector(1_000_000);
long duration = (System.nanoTime() - start) / 1_000_000;
if (duration < fastest) {
fastest = duration;
}
}
System.out.println("Fastest execution done in " + fastest + " msecs");
}
Java
복사
결과를 보면 유의미한 성능 향상이 된 것 같다. 직접 구현해보며 Collector에 대한 이해도도 높히고 성능향상이라는 장점까지 같이 가져갈 수 있었다.
참고: 별도의 컬렉터를 만들지 않고 구현하기
static Map<Boolean, List<Integer>> partitionPrimesWithCustomCollectorV2(int n) {
return IntStream.rangeClosed(2, n).boxed()
.collect(
() -> new HashMap<Boolean, List<Integer>>() {{
put(true, new ArrayList<>());
put(false, new ArrayList<>());
}},
(acc, candidate) -> {
acc.get(isPrime(acc.get(true), candidate)).add(candidate);
},
(map1, map2) -> {
map1.get(true).addAll(map2.get(true));
map1.get(false).addAll(map2.get(false));
}
);
}
Java
복사
별도의 클래스를 만드는 것 보다는 간결해보인다. 하지만, 가독성과 재사용이 떨어지기에 상황에 맞춰 사용하면 될 것 같다.
