로드-커팅 문제(Cutting Stock Problem)
로드-커팅 문제(Cutting Stock Problem) : 주어진 장작을 다양한 크기로 잘라 최대한의 이익이 나도록 하는 문제.
도매로 장작을 구입해서 소매로 판매하는 회사에 근무한다고 가정해보자. 이 회사는 장작을 다양한 크기로 잘라서 최대한의 이익을 얻는다. 각각 서로 다른 길이를 갖고 있는 장작의 가격은 수시로 변경되며 따라서 주어진 크기의 장작에 대해 최대한의 이익을 구하는 프로그램을을 작성해야 한다.
단순한 재귀 호출을 사용한 해결
5인치의 장작이 있다면 그 길이에 대한 가격을 찾을 수 있다. 이 예제에서 5인치 장작의 가격은 2달러 이다, 하지만 4인치도 2달러 이기 때문에 이 경우에는 5인치를 5인치와 1인치로 자르는 방법이 더 좋다. 이 방법을 사용하면 n의 길이에 대한 수익을 구할 수 있으며, 그 방법은 해당 길이를 가능한 2n-1로 자르는 것이 가장 큰 수익을 얻을 수 있다.
주어진 길이 n에 대해서 max(no cut, cut(1, n-1), cut(2, n-2), ....)와 같이 계산할 수 있다.
이를 코드로 작성하면 아래와 같이 작성 할 수 있다.
이 메서드는 특정 길이의 수익을 찾는데 주어진 길이에 추가 하여 다른 길이의 수익을 재귀적으로 찾게 된다. 최종적으로는 그 중에 최대 수익을 구하도록 되어 있다.
final List<Integer> priceValues = Arrays.asList(1, 2, 4, 2, 2, 2, 1, 8, 9, 15);public int maxProfit(final int length) {
int profit = (length <= prices.size()) ? prices.get(length - 1) : 0;
for (int i = 1; i < length ; i++) {
final int currentProfit = maxProfit(i) + maxProfit(length - i);
if (currentProfit > profit) profit = currentProfit;
}
return profit;
}
이를 수행해 보면 length 값이 증가할 수록 복잡도가 O(2^(n-1) ) 와 같이 지수 형태로 증가 하기 때문이고, 다양한 길이에 대한 반복된 연산을 계속 수행한다.
이를 개선하기 위해 재귀 연산을 재활용하는 메모이제이션 기법을 사용한다.
메모이제이션을 사용하면 처음으로 연산하는 경우에만 연산을 실행하고, 이전에 한 번이라도 연산을 한 적이 있다면 과거의 연산 결과를 사용한다.
자바 8 람다의 힘 책에서는 이를 람다로 풀었었었는데, 이를 람다가 아닌 일반 해쉬 맵을 사용한다면..
private final Map<Integer, Integer> store = new HashMap<>();
public int maxProfit(final int length) {
int profit = (length <= prices.size()) ? prices.get(length - 1) : 0;
if (store.get(length) != null) {
return store.get(length);
} else {
for (int i = 1; i < length ; i++) {
final int currentProfit = maxProfit(i) + maxProfit(length - i);
if (currentProfit > profit) profit = currentProfit;
}
store.put(length, profit);
return profit;
}
}
위 같은 방법으로 이미 호출됬던 재귀 호출에 대한 값을 hashmap에 저장해 둠으로써 연산 속도를 엄청나게 올릴 수 있다.
기존 방법으로 할 경우 22를 값으로 줄 경우 무려 40초가 걸리는데, 맵을 사용하는 방법으로 변경하면 1초도 안걸린다.
이걸 Java 8 람다 스타일로 좀 바꿔 보면 아래 처럼 작성할 수 있다.
.computeIfAbsent는 map에 추가된 메서드로 키에 해당하는 값이 있으면 그 값을 리턴해주고 없으면 새로운 값을 할당한 다음 그것을 리턴해준다.
public int maxProfit(final int length) {
return store.computeIfAbsent(length, (key) -> {
int profit = (length <= prices.size()) ? prices.get(length - 1) : 0;
for (int i = 1; i < length; i++) {
final int currentProfit = maxProfit(i) + maxProfit(length - i);
if (currentProfit > profit) profit = currentProfit;
}
store.put(length, profit);
return profit;
}
);
}
여기서 느낄 수 있었던 것은 재귀 함수를 작성해서 문제를 해결한다. 라는 생각까지만 하지말고 이를 좀 더 머리를 써보면(여기서는 맵을 사용한 메모이제이션) 좀 더 성능이 좋은 코드를 작성할 수 있다는 것이다.
따로 알고리즘 공부를 하진 않지만 기존 알고리즘에 이런 메모이제이션 기법을 도입하는 것은 참신한 기법인듯.
프로그래밍 경험치가 +1 되는 기분이 들었다.
Java 8 Stream API PART 2.
원본 : Part 2. Processing Data with Java SE 8 Streams
==================================================================================
다양한 기능들을 조합하여 좀 더 다양한 데이터 처리 쿼리를 만들기.
이전 문서에서 스트림을 사용하여 컬렉션 데이터 처리를 데이터베이스의 쿼리처럼 처리하는것을 살펴 보았다.
머
리를 식힐겸 스트림 API를 사용하여 거래금액이 비싼 내역들의 합을 구하는 코드인 Listing 1을 보자. 중간
작업(filter, map)을 통해 파이프라인을 세팅하고 종료 작업(reduce)을 통해 코드를 실행시키는 과정을 아래
Figure 1을 통해 볼 수 있다.
Listing 1.
int sumExpensive = transactions.stream() .filter(t -> t.getValue() > 1000) .map(Transaction::getValue) .reduce(0, Integer::sum);
Figure 1
flatMap, collect 두 기능에 대해서 알아보자.
이 두 기능은 복잡한 형태의 질의를 하는데 유용하게 쓰인다. 예를 들어 flatMap과 collect를 조합하여 Listing2 처럼 스트림에서 중복이 제거된 각 알파벳의 카운트를 가진 맵을 만들 수 있다.
이 두 기능에 대해서 더 자세히 살펴보고 설명할 예정이니 처음 보는 형태의 코드를 보고 걱정할 필요는 없다
Listing 2
import static java.util.function.Function.identity; import static java.util.stream.Collectors.*; Stream<String> words = Stream.of("Java", "Magazine", "is", "the", "best"); Map<String, Long> letterToCount = words.map(w -> w.split("")) .flatMap(Arrays::stream) .collect(groupingBy(identity(), counting()));
Listing2 의 결과를 출력해보면 Listing3과 같이 표시된다.
이제부터 flatMap과 collect가 어떻게 동작하는지 알아보자
Listing 3
[a:4, b:1, e:3, g:1, h:1, i:2, ..]
flatMap Operation
만약 파일에서 고유한 단어를 찾는다고 생각해보자. 이를 어떻게 구현할 것인가?
Files.lines()를 통해 한줄씩 읽은 다음 map() 기능을 사용해서 단어들을 잘라낸 다음에 distinct()를 사용해 중복을 제거 하면 된다. 이를 코드로 작성해보면 Listing 4처럼 될 것이다.
Listing 4
Files.lines(Paths.get("stuff.txt")) .map(line -> line.split("\\s+")) // Stream<String[]> .distinct() // Stream<String[]> .forEach(System.out::println);
하지만 이 코드는 원하는 대로 동작 하지 않는다. 이 코드를 실행시켜보면 아래와 같은 결과를 얻을 것이다.
[Ljava.lang.String;@7cca494b [Ljava.lang.String;@7ba4f24f
처음 작성한 위 코드는 스트림들을 String으로 출력하고 있다. 무슨일이 발생한걸까?
이 방식의 문제점은 람다 표현식에서 map으로 전달되는 형태가 String 배열(String[]) 이기 때문이다.
이 결과를 보면 우리가 원하는 형태는 문자들로 구성된 Stream<String>인데 map()을 사용했을때 리턴하는 스트림은 Stream<String[]>이 된다.
이는 flatMap을 사용하면 간단히 해결할 수 있다. 이 방법을 한단계씩 적용해보자.
코드를 작성하기 위해서 단어의 스트림 대신 배열 스트림이 필요하다. Arrays.stream() 메서드를 통해 배열을 스트림으로 만들 수 있다.
Listing 5
String[] arrayOfWords = {"Java", "Magazine"}; Stream<String> streamOfwords = Arrays.stream(arrayOfWords);
이처럼 배열을 스트림으로 변환하는 내용을 Listing 6 처럼 추가해보자.
이 방법도 스트림의 스트림목록 형태(Stream<Stream<String>>)로 되어 있어서 잘 동작하지 않는다.
처음엔 매 라인을 단어들의 배열로 바꾸도록 하였고, 그 다음 이 배열들을 Arrays.stream()을 사용해서 stream으로 변경했다.
Listing 6
Files.lines(Paths.get("stuff.txt")) .map(line -> line.split("\\s+")) // Stream<String[]> .map(Arrays::stream) // Stream<Stream<String>> .distinct() // Stream<Stream<String>> .forEach(System.out::println);
Listing 7 처럼 flatMap을 사용하도록 하여 잘 동작하게 할 수 있다. 이는 map(Arrays::stream)을 사용한것 처럼 각각 분리된 스트림들을 생성하고 이를 하나의 스트림으로 변경한다.
Listing 7
Files.lines(Paths.get("stuff.txt")) .map(line -> line.split("\\s+")) // Stream<String[]> .flatMap(Arrays::stream) // Stream<String> .distinct() // Stream<String> .forEach(System.out::println);
Figure 2 에서는 flatMap 메서드의 동작방식을 설명하고 있다.
Figure 2
간단하게 말하면 flatMap은 각각 다른 값을 가진 스트림들을 하나의 스트림으로 생성해 준다.
flatMap은 자주 사용되는 패턴으로 Optional이나 CompletableFuture를 사용할때 다시 보게 될 것이다.
collect Operation
이젠 colllect 메서드에 대해서 더 상세히 알아보자. 이전 문서에서 봤던 collect의 사용방법은 작업을 처리한 후 다른 스트림을 리턴하거나 다른 값(boolean, int, Optional)을 리턴하는 것이었다.
collect 메서드는 종료 작업이긴 하지만 stream을 list로 변경할 경우는 약간 다르다. 예를 들어 아래 listing 8의 코드 처럼 거래 금액이 큰 거래내역의 id 목록을 가져오는것 처럼 list를 리턴한다.
Listing 8
import static java.util.stream.Collectors.*; List<Integer> expensiveTransactionsIds = transactions.stream() .filter(t -> t.getValue() > 1000)
.map(Transaction::getId) .collect(toList());
collect 메서드에 전달된 인자의 타입은 java.util.stream.Collector다. Collector 오브젝트가 하는일은 무엇일까? 이것은 본질적으로 최종 리턴값으로 되어야할 것에 대해 설명을 한다고 보면 된다.
팩토리 메서드인 Collectors.toList()는 스트림을 리스트 형태로 변경하여 반환한다. 다른 형태의 내장 Collectors도 여러가지가 존재 한다.
스트림을 다른 컬렉션 형태로 변경하기.
toSet()을 사용하면 스트림을 Set(중복이 제거된)으로 변경 가능하다. Listing 9의 코드는 거래내역중에 도시 목록을 중복이 제거된 Set 형태로 반환한다.
Listing 9
Set<String> cities = transactions.stream() .filter(t -> t.getValue() > 1000) .map(Transaction::getCity) .collect(toSet());
위 코드를 보면 Set이 어떤 타입인지는 보장하지 않지만 toCollection() 메서드를 사용해서 타입을 지정할 수 있다.
아래 Listing 10의 코드 처럼 toCollecte에다가 HashSet을 지정할 수 있다.
Listing 10
Set<String> cities = transactions.stream() .filter(t -> t.getValue() > 1000) .map(Transaction::getCity) .collect(toCollection(HashSet::new));
위 기능은 collect를 사용해서 할 수 있는 것들중에 작은 부분일 뿐이다.
아래 예제처럼 몇가지 기능을 더 사용할 수 있다.
- 화폐에 따른 거래 내역을 그룹핑하여 합을 구하기 (Map<Currency, Integer>)
- 거래 내역을 두 개로 분리 : 비싼 내역과 그렇지 않은 내역(Map<Boolean, List<Transaction>)
- 다양한 뎁스로 그룹핑, 도시 형태로 먼저 그룹핑 하고 그 안에 비싼 내역과 그렇지 않은 내역으로 또 그룹핑(Map<String, Map<Boolean, List<Transaction>>)
계속 해서 Steam API와 collectors 들을 사용해서 다양한 질의를 생성하는것에 대해 살펴보자
가
장 먼저 볼 것은 스트림을 "summarizes" 하는 것이고(평균값 계산, 최대 및 최소값 추출) 그 다음은 간단한 그룹핑을
살펴보고 마지막으로 collectors 들을 조합하여 멀티레벨 그룹핑 같은 다양한 질의문을 만들어보자.
Summarizing
몇가지 간단한 예제들을 가지고 워밍업을 해보자.
이전 문서에서 숫자들의 목록을 가지고 최대, 최소 및 평균을 reduce 메소드를 사용해서 구해봤었다. 이것들을 미리 정의 되어 있는 collectors 들이다.
만약 숫자들의 갯수들 가져오고 싶으면 Listing 11의 코드처럼 counting()을 사용하면 된다.
Listing 11
long howManyTransactions = transactions.stream().collect(counting());
summingDouble(), summingInt(), summingLong() 같은 메서드를 사용해서 스트림에 포함된 Double, Int, long 과 같은 엘리먼트들의 합계를 구할 수 있다.
아래 Listing 12의 코드는 모든 거래 내역의 합계를 구한다.
Listing 12
int totalValue = transactions.stream()
.collect(summingInt(Transaction::getValue));
위와 비슷하게 averagingDouble(), averagingInt(), averagingLong()일 사용해서 평균값을 구할 수 있다.
maxBy(), minBy()를 사용해서 최대값과 최소값을 구할 수도 있다.
위 두 메서드는 Figure 3처럼 Comparator형태의 인자를 필요로 한다.
Figure 3
Listing 14의 코드 처럼 스태틱 메서드인 comparing() 메서드는 전달된 함수를 가지고 Comparator 객체를 생성한다. 이 함수에서 추출된 값을 사용해서 스트림의 값들을 비교하게 된다.
아래 코드에서는 가장 높은 값을 찾는 코드이다.
Listing 14
Optional<Transaction> highestTransaction = transactions.stream() .collect(maxBy(comparing(Transaction::getValue)));
reducing() 메서드 처럼 모든 엘리먼트들에 대해 정해진 작업을 반복적으로 수행하는 것도 있다.
Listing 15의 코드는 reducing() 메서드를 사용해서 합계를 구하는 코드이다.
Listing 15
int totalValue = transactions.stream().collect(reducing( 0, Transaction::getValue, Integer::sum));
recuding() 메서드는 3개의 인자를 가진다
- 초기화 값(stream이 비어있으면 이겂을 리턴) : 여기서는 0
- 스트림에서 반복적으로 수행할 함수 : 여기서는 getValue를 통해 값을 추출
- 위에서 구한 값을 조합 하는 코드 : 여기서는 값을 계속 더한다.
"이전에 reduce(), max(), min()을 통해서 위 기능을 사용했었는데 왜 이제와서 이걸 보여주지?' 라는 의문이 들 것이다.
위의 기본 기능이외에 collectors를 조합하여 더 복잡한 질의문(합계를 그룹핑 하는)을 생성하는것을 볼것인데 이 내장 collector에 대해서 알아 두는 것이 좋다.
Grouping
대부분의 데이터베이스들이 Group By 같은 명령어를 통해서 데이터 그룹핑을 지원한다.
만약 화폐에 따라 거내 내역을 그룹핑할 필요가 있을때 이를 이전 방법으로 작성한다면 아래 코드처럼 고통스러운 코드를 작성해야 될 것이다.
Listing 16
Map<Currency, List<Transaction>> transactionsByCurrencies = new HashMap<>(); for(Transaction transaction : transactions) { Currency currency = transaction.getCurrency(); List<Transaction> transactionsForCurrency = transactionsByCurrencies.get(currency); if (transactionsForCurrency == null) { transactionsForCurrency = new ArrayList<>(); transactionsByCurrencies.put(currency, transactionsForCurrency); } transactionsForCurrency.add(transaction); }
위 코드를 보면 먼저 거래내역을 저장할 Map을 생성한 후 거래내역에 대해 반복 작업을 수행해서 currency를 추출 한 다음 Map에 currency가 존재 하지 않으면 새로 만들어서 넣어 주는 작업을 하고 있다.
사실 currency에 따라 거래내역을 그룹핑 하는것을 원할 뿐인데 상당히 복잡한 코드로 작성되어 있다.
이를 개선하기 위해서는 groupingBy()메서드를 사용하면 되는데 이를 사용해서 간결한 코드로 위 내용을 작성할 수 있다.
Listing 17의 코드는 이전 코드와 동일한 역할을 하고 훨씬더 이해하기 쉽게 작성되어 있다.
Listing 17
Map<Currency, List<Transaction>> transactionsByCurrencies = transactions.stream().collect(groupingBy(Transaction::getCurrency));
팩토리 메서드인 groupingBy()는 그룹핑 하는데 키로 사용할 값을 추출하는 함수를 인자로 받아서 사용한다. 이를 classification function(분류함수)이라고 한다.
이 예제에서는 transaction의 currency로 그룹핑을 하기 위해서 메소드 참조(Transaction::getCurrency)를 파라미터로 전달한다.
Figure 4에서는 이를 그림으로 설명하고 있다.
Figure 4
Partitioning
groupingBy()의 특별한 케이스인 partitioningBy()라는 팩토리 메서드도 존재 한다. 이것은 predicate타입을 인자로 받으며 predicate에 만족하는 엘리먼트들을 그룹핑해서 리턴한다.
바꿔 말하면 거래내역들을 분류해서 그룹핑 할 수 있다(Map<Boolean, List<Transaction>)
예
를 들어 만약 거래내역을 두가지 그룹으로 나누고 싶다면(고가, 저가) Listing 18의 코드처럼
partitioningBy()를 사용하면 된다. 람다 표현식인 t -> t.getValue() > 1000 을 기준으로
거래 내역을 구분하게 된다.
Listing 18
Map<Boolean, List<Transaction>> partitionedTransactions = transactions.stream().collect(partitioningBy( t -> t.getValue() > 1000));
Composing collectors.
SQL을 자주 사용해봐서 익숙 하다면 GROUP BY와 함께 COUNT()와 SUM()을 사용해본 경험이 있을 것이다. 이 기능과 비슷한것을 Stream API를 통해서 할 수 있다.
groupingBy() 두번째 인자로 대상 을 넣어 주면 된다.
추
상적인 설명으로는 이해가 잘 않으니까 간단한 예제를 살펴보자. Map을 만들어서 도시별로 거래내역의 합계를 구한다고 해보자.
Listing 19의 코드 처럼 groupingBy 의 첫번째 인자로 getCity()를 줘서 키를 지정하면 도시를 키로 가지고
있고 값으로 List<Transaction>을 가지고 있는 Map을 리턴할 것이다.
Listing 19
Map<String, Integer> cityToSum = transactions.stream().collect(groupingBy( Transaction::getCity, summingInt(Transaction::getValue)));
만약 도시별 거래금액의 합계를 구하기 위해서는 summingInt라는 추가적인 컬렉터를 세팅해줘야된다. 이 코드의 실행 결과로 Map<String, Integer>를 형태로 각 도시별 거래금액의 합계를 구할 수 있다.
groupingBy(Transaction::getCity> 형태로 사용할 수도 있고 groupingBy<Stransaction::getCity, toList()) 형태로도 사용할 수 있다.
각 도시의 가장 높은 거래 금액을 가지고 있는 Map을 생성한다고 해보자.
아래 Lisinting 20의 코드처럼 이전에 봣던 maxBy 컬렉터를 사용하면 쉽게 구현할 수 있다.
Listing 20
Map<String, Optional<Transaction>> cityToHighestTransaction = transactions.stream().collect(groupingBy( Transaction::getCity, maxBy(comparing(Transaction::getValue))));
스트림 API는 다양한 기능을 제공하고 SQL처럼 동작하는 쿼리를 간결하게 작성할 수 있다.
마지막으로 조금 더 복잡한 예를 살펴보자. groupingBy()의 인자로 다른 컬렉터를 받아서 다양한 작업을 할 수 있다.
이것은 groupingBy()도 collector이기 때문이다. 멀티레벨 그룹핑을 할때 groupingBy collector를 전달함으로써 이를 구현할 수 잇다.
Listing 21의 코드는 거래 내역을 도시별로 그룹핑하고 하위 그룹은 통화별 거래내역의 평균을 가지도록 하는 코드이다.
Listing 21
Map<String, Map<Currency, Double>> cityByCurrencyToAverage = transactions.stream()
.collect(groupingBy(Transaction::getCity, groupingBy(Transaction::getCurrency, averagingInt(Transaction::getValue))));
Figure 5는 이름 그림으로 설명한 것이다.
지금까지 본 모든 collector 들은 java.util.stream.Collector 인터페이스를 구현한 것이다. 만약 자신만의 collector를 구현하고 싶으면 이 인터페이스를 상속 받아서 만들 면 된다.
결론
이 문서에서는 Stream API의 두가지 쓸만한 기능인 flatMap과 collect에 대해서 살펴봤다. 이를 사용해서 데이터 처리 작업을 간결한 코드로 할 수 있었다.
특 히 collect 메서드는 summarizing, grouping, partitioning을 쉽게 만들 수 있고 이를 서로 조합해서 "각 도시의 통화별 거래내역의 합계를 가지고 있는 두 단계 깊이의 Map 처럼 유용한 쿼리를 만들 수도 있다.
이 문서에 collector들에 대해 전부 알아보지는 않았기 때문에 다른 Collectors들(mapping(), joining(), collecting AndThen()) 같은 것들도 살펴보면 쓸만할 것이다.
Java 8 Optional.
Java 8에서 추가된 기능인 Optional에 대해서 간단하게 소개된 글이 있어서 공유 합니다.
(http://java.dzone.com/articles/java-8-optional-avoid-null-and)
언제 어디서나 우리를 괴롭히던 Null 과 NPE를 물리칠 수 있다는 군요! +ㅅ+
참고 : java8-optional
함수형 프로그래밍 : 위키설명
Java 8 Optional - Null 및 NullPointerException 둘다 회피하고 코드를 예쁘게 짜기.
Null 과 NPE(NullPointerException), 이를 회피하는 방법에 대한 문서들을 여러방법으로 소개되고 있다. 이런 방법들 보다 Java 8에서 제공하는 Optinal 기능을 사용하면 쉽고, 안전하고, 아름다운 코드로 작성할 수 있다. 이 문서는 다른 옵션 값들이나 유틸리티코드 사용 없이 이를 구현하는 방법을 소개한다.
이전 방법
아래 코드를 살펴보자
1.
String unsafeTypeDirName = project.getApplicationType().getTypeDirName();
2.
System.out.println(unsafeTypeDirName);
01.
// 안전하지만 지저분하고 코드가 누락될 수도 있다
02.
if
(project !=
null
) {
03.
ApplicationType applicationType = project.getApplicationType();
04.
if
(applicationType !=
null
) {
05.
String typeDirName = applicationType.getTypeDirName();
06.
if
(typeDirName !=
null
) {
07.
System.out.println(typeDirName);
08.
}
09.
}
10.
}
01.
02.
Optional<Project> optionalProject = Optional.ofNullable(project);
03.
04.
// 안전하고 Java 8을 사용했지만 지저분하고 여전히 코드가 누락될 가능성이 있다
05.
if
(optionalProject.isPresent()) {
06.
ApplicationType applicationType = optionalProject.get().getApplicationType();
07.
Optional<ApplicationType> optionalApplicationType = Optional.ofNullable(applicationType);
08.
if
(optionalApplicationType.isPresent()) {
09.
String typeDirName = optionalApplicationType.get().getTypeDirName();
10.
Optional<String> optionalTypeDirName = Optional.ofNullable(typeDirName);
11.
if
(optionalTypeDirName.isPresent()) {
12.
System.out.println(optionalTypeDirName);
13.
}
14.
}
1.
// 안전하고 깔끔하다
2.
Optional<String> optionalTypeDirName = optionalProject
3.
.map(project -> project.getApplicationType())
4.
.map(applicationType -> applicationType.getTypeDirName());
5.
optionalTypeDirName.ifPresent(typeDirName -> System.out.println(typeDirName));
1.
// 안전하고 여전히 깔끔하다
2.
Optional<String> optionalTypeDirName2 = optionalProject
3.
.map(Project::getApplicationType)
4.
.map(ApplicationType::getTypeDirName);
5.
optionalTypeDirName2.ifPresent(System.out::println);
자바 컬렉션 프레임워크 인터뷰 질문 40개
http://www.javacodegeeks.com/2013/02/40-java-collections-interview-questions-and-answers.html
저기 있는거 번역..
맨날 HashMap하고 ArrayList 만 쓰다 보면, 컬렉션 프레임워크가 뭔지 잊어 버릴때가...-_ -;;
======================================================================================================================
컬렉션 프레임워크를 사용함으로써 얻을 수 있는 이점들을 아래와 같다.
- 별도로 컬렉션 클래스를 구현하는 것보다 구현되있는것을 사용함으로써 코딩 시간을 감소 시킬 수 있다.
- 컬렉션 프레임워크들은 잘 테스트 되고 검증되어있기때문에 코드 품질을 보장한다.
- JDK에 포함된 컬렉션 프레임워크들을 사용하여 코드 유지보수 시간을 감소 시킬 수 있다.
- 재사용 가능하고 상호 운용성이 보장 된다.
- Collection 은 가장 기본이 되는 인터페이스이다. 자바는 이 인터페이스를 직접 구현한 클래스는 아무것도 제공하지 않는다.
- Set 은 중복을 허용하지 않는 집합이다.
- List 는 중복을 허용하고 정렬이 가능한 컬렉션이다. 인덱스를 통해 아무런 엘리먼트나 접근할 수 있고, 길이 조정이 가능한 배열과 비슷하다고 할 수 있다.
- Map 은 키/값을 가지고 있는 오브젝트다. 키값은 중복되어선 안되고 하나의 키 값은 하나의 값에 매핑된다.
- Set과 List에 Iterator를 사용할 수 있지만 ListIterator에는 List만 가능하다.
- Iterator 는 앞쪽으로 탐색을 하지만 ListITerator는 양방향 순회가 가능한다.
- ListIterator는 Iterator 인터페이스를 상속받았고 추가적으로 Add, 엘리먼트 교체, 현제 index의 이전, 다음 엘리먼트 가져오기 등 많은 추가 기능을 제공한다.
01 | List<String> strList = new ArrayList<>(); |
02 | //using for-each loop |
03 | for (String obj : strList){ |
04 | System.out.println(obj); |
05 | } |
06 | //using iterator |
07 | Iterator<String> it = strList.iterator(); |
08 | while (it.hasNext()){ |
09 | String obj = it.next(); |
10 | System.out.println(obj); |
11 | } |
- If
o1.equals(o2)
, theno1.hashCode() == o2.hashCode()
should always betrue
. - If
o1.hashCode() == o2.hashCode
is true, it doesn’t mean thato1.equals(o2)
will betrue
.
- 만약 클래스가 equals()를 overrides 했다면 hashCode() 역시 override 해야 한다.
- 18번에 언급된 기본 구현 규칙을 따라야 한다.
- equals() 메서드가 사용되지 않으면 hashCode()도 사용하지 않아야 한다.
- 가장 좋은 방법은 key 클래스를 불변(immutable)으로 만드것이다. 이렇게 하면 hashCode()값은 캐시되어 빠른 성능을 가진다. 또한 불변 클랙스는는 hashCode() 및 equals()의 값이 변하지 않기 때문에 해당 값이 변해서 생기는 문제들을 해결할 수 있다. 예를 들어 아래 HashMap의 key 로 사용될 MyKey 클래스를 살펴봐라.
01 | //MyKey name argument passed is used for equals() and hashCode() |
02 | MyKey key = new MyKey( 'Pankaj' ); //assume hashCode=1234 |
03 | myHashMap.put(key, 'Value' ); |
04 |
05 | // Below code will change the key hashCode() and equals() |
06 | // but it's location is not changed. |
07 | key.setName( 'Amit' ); //assume new hashCode=7890 |
08 |
09 | //below will return null, because HashMap will try to look for key |
10 | //in the same index as it was stored but since key is mutated, |
11 | //there will be no match and it will return null. |
12 |
|
- Set keySet(): 맵에 존재하는 Key 값들을 Set으로 보여준다. 이 set들은 맵과 연결되어 있으며 맵을 바꾸거나 set을 바꾸면 값이 수정 된다. 만약 키 Set을 사용하는중에 map이 변경 되면 Set을 반복할때 나오는 결과값은 undefined 되게 된다. Set은 엘리먼트들을 지울 수 있고 이에 대응하는 값은 맵에서 삭제 된다.(remove, Set.remove, removeAll, retaionAll, clear) add 나 addAll같은 기능은 제공하지 않는다.
- Collection values() : 맵에 존재하는 Value 들을 컬렉션 형태로 보여준다. 이것 역시 맵과 연동되어 있으며 collection을 수정 하면 map의 값이 수정된다.
- Set<Map.Entry<K, V>> entrySet() : 맵의 entry 들을 Set 형태로 보여준다.
- HashMap은 키/값에 null을 허용하는 반면 Hashtable은 이를 허용하지 않는다.
- Hashtable은 synchronized (synchronized) 되어 있지만 HashMap 은 그렇지 않다. 그래서 HashMap 은 단일 스레드 환경에서 더 좋은 퍼포먼스를 보여준다. 반면, Hashtable은 멀티 스레드 환경에 적합하다.
- LinkedHashMap 은 자바 1.4에서 HashMap의 서브클래스로 소개되었다. 그렇기 때문에 iteration 의 순서를 보장받고 싶다면, HashMap에서 LinkedHashMap으로쉽게 변경 가능하다. 그러나 Hashtable 에서는 그럴 수 없으므로 iteration 순서를 예측할 수 없다.
- HashMap은 iterator 키 셋을 제공하므로 fail-fast (12 참고) 기능을 사용하나 Hashtable은 Enumeration 키를 사용하므로 이런 기능을 제공하지 못한다.
- Hashtable은 legacy 클래스로 취급을 받기 때문에 만약 Map에서 iteration을 하는 도중에 수정가능한 Map을 사용하고 싶다면 ConcurrentHashMap을 사용하면 된다.
- 인덱스 기반이고 내부적으로 배열로 백업 할 수 있다.
- 엘리먼트들을 추가한 순서를 가지고 있고 이 순서를 가져 올 수도 있다.
- iterator를 구현하였으므로 fail-fast 방식이다.
- null 값을 가질 수 있고 인덱스 번호를 사용해 랜덤으로 접근 할 수 있다.
- Vector는 synchronized 되어 있지만 ArrayList는 그렇지 않다. 만약 iterating 중에 엘리먼트를 수정 하고 싶다면 CopyOnWriteArrayList를 사용하면 된다.
- ArrayList는 synchronized에 따른 간접비용이 아무것도 없기 때문에 Vector보다 빠르다.
- ArrayList가 좀 더 다재다능 한데 Collection Utility 클래스에서 제공하는 기능으로 synchronized를 시키거나 읽기 전용 리스트를 만들수도 있다.
- 리스트의 크기가 고정되어 있고 값을 저장하거나 탐색 용도로만 쓸 경우
- primitive 타입일 경우
- 만약 다차원 배열을 사용할 경우 [][] 배열을 사용하는게 List<List<>>를 쓰는것보다 쉽다.
- ArrayList는 인덱스 기반의 Array로 구성되어 있어서 랜덤 엑세스를 할 경우 O(1)의 속도를 가진다. LinkedList는 데이터들이 이전, 다음 노드 처럼 서로 연결된 node로 구성되어 있다. 인덱스 번호를 사용해서 엘리먼트에 접근 하더라도 내부적으로는 노드들을 순차적으로 순회하며 엘리먼트를 찾는다. LinkedList 의 속도는 O(n)으로 ArrayList 보다 느리다.
- 엘리먼트의 추가 및 삭제는 LinkedList가 ArrayList보다 빠른데 엘리먼트를 추가 및 삭제하는 중에 array를 리사이즈 하거나 인덱스를 업데이트를 할 일이 없기 때문이다.
- LinkedList의 엘리먼트들은 이전, 다음 엘리먼트들에 대한 정보를 가지고 있기 때문에 LinkedList가 ArrayList보다 더 많은 메모리를 소비한다.
Comparator
인터페이스를 사용하면 되는데 Comparable.compareTo(Object o)는 하나의 필드만 가지고 정렬을 수행하기 때문에 정렬에 필요한 오브젝트들 선텍할 수 있다. Comparator 인터페이스는 두개의 파라미터를 가지고 있는 compare(Object o1, Object o2)
메서드를 제공하는데 이 메서드는 만약 첫번째 변수가 두번째 변수보다 작으면 음수를 리턴하고 만약 두 값이 같으면 0, 더 크면 양수를 리턴한다.Collections.unmodifiableCollection(Collection c)
메서드를 사용해서 읽기전용 커렉션을 생성할 수 있고 만약 컬렉션을 수정할려는 시도가 생기면 UnsupportedOperationException을 발생 시킨다.- 예1 : ArrayList get(index i)는 엘리먼트의 숫자에 영향을 받지 않고 동일한 성능을 보여주기 때문에 Big-O 표기법으료 표시하면 O(1)으로 표기 할 수잇다.
- 예2 : 배열이나 리스트에 대한 선형 탐색은 엘리먼트를 찾는데 엘리먼트들의 숫자에 영향을 받기 때문에 O(n)으로 표시한다.
- 필요에 따라 상황에 맞는 컬렉션을 선택해야 된다. 예를 들어 사이즈가 고정되어 있으면 ArrayList보다 Array를 사용할 수 있다. 만약 맵에 삽입된 순서되로 iterate를 하고 싶으면 TreeMap을 사용하는것이 좋다. 중복을 허용하고 싶으 않으면 Set을 사용하면 된다.
- 몇몇 컬렉션 클래스들을 초기 용량을 지정할 수 있다. 만약 저장할 엘리먼트들의 사이즈를 알 경우에 초기 용량을 지정함으로써 rehashing이나 resizing이 일어나는것을 회피할 수 있다.
- 코드를 작성할때 구현 클래스가 아닌 인터페이스를 기반으로 작성해야 나중에 구현체를 변경할때 코드를 재작성하는 수고를 줄일수 있다.
- 런타임에 발생할 수 있는 ClassCastException을 회피할려면 항상 제너릭스를 사용해서 type-safety 한 상태를 유지하라
- 맵에 키를 사용할때 JDK에서 재공하는 immutable 클래스를 사용하여 사용자 클래스에서 hashCode()와 equals() 구현할 필요가 없게 하라
- 읽기전용 및 동기화, 빈 컬렉션등을 만들때는 자신만의 구현으로 생성하지 말고 Collections에서 제공하는 유틸리티 클래스를 사용하라. 이는 코드 재사용성을 높여주고 안정적이며 유지보수 비용을 줄여 준다.
Java 언어로 배우는 리팩토링 입문.
리팩토링 중에서 자주 쓰이는 것들을 간단한 예제와 함께 잘 정리해 두었다.
아주 쉽게 읽을수 있었던 책.
주요 내용은
- 매직넘버를 심볼릭 정수로 치환하기 : 소스에 '100'이라고 쓰여져 있다면.
- 제어 플래그의 삭제 : 제어 플래그 때문에 코드를 읽기 힘들다면.
- assertion의 도입 : '이것이 성립될 것' 이라고 하는 주석이 있으면.
- NULL 오브젝트 도입 : Null 체크가 너무 많다면.
- 메소드의 추출 : 코드가 너무 길어 읽기 힘들다면.
- 클래스의 추출 : 클래스의 책임이 너무 많다면.
- 타입코드를 클래스로 치환하기 : 오브젝트 식별에 int가 사용되고 있다면.
- 타입코드를 서브클래스로 치환하기 : 타입코드마다 동작이 다르다면.
- 타입코드를 State/Strategy로 치환하기 : 타입코드마다 동작이 다르다면.
- 오류 코드를 예외로 치환하기 : 오류 처리가 어지럽게 흩어져 있다면.
- 생성자를 Factory Method로 치환하기 : 클래스명이 new로 하드코딩 되어 있다면.
- 관찰되는 데이터의 복제 : 모델과 뷰가 혼재되어 있다면.
- 상속을 위임으로 치환하기 : IS-A관계가 아님에도 불구하고 상속하고 있다면.
- 위임의 은폐 : 위임 클래스까지 보인다면.
- 상속의 분할 : 상속이 얽혀 있다면.
아.. 보면서 내가 짰던 프로그램을 생각해보니..
리팩토링 해야할 것들이 ... ㄷㄷㄷㄷ
주말엔 소스 리팩토링좀 하자 ;ㅁ ;
System.arraycopy();
배열 카피하는 메소드.
arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
Copies an array from the specified source array, beginning at the specified position, to the specified position of the destination array.
요런다... 무슨말인고 하니..
src 의 srcPos 부터 desPos의 length 길이 만큼 dest 배열에다가 복사한다는 뜻.
요즘 만드는 것.
구현중인 프로그램
요즘 한창 SWT를 사용해서 개발중인 이미지 검색 프로그램.
이미지 색인 및 검색은 lire 라는 라이브러리가 있어서 손쉽게 할 수 있었다.
이것을 이미지 잘라서 검색, 캠으로 찍어서 검색 등 기능을 추가 하는 중이고.
병해충 이미지 검색을 위해 만든 것이기 때문에 검색 결과를 병해충 정보를 담은 xml 파일과 연동 시켜 주는것도 하고 있다.
대략 이번달 까지 마무리 했으면 하는소망이 있다.
10일도 안남았구나 -_-;;
힘내자.
Read-Write Lock 패턴
별명 : Reader Writer, Reader/Writer Lock, Readers/Writer Lock
문맥 : 복수의 쓰레드가 인스턴스를 공유하고 있어 인스턴스의 상태를 참조하는 것뿐인 쓰레드(Reader)와 변경하는 쓰레드(Writer)가 존재하고 있다고 합시다.
문제 : 쓰레드 간에 배타 제어를 하지 않으면 안정성을 잃게 됩니다. 그러나 Single Threaded Execution 패턴을 사용하면 스루풋이 떨어져 버립니다.
해결법 : 우선 『Reader를 제어하는 락』과 『Writer를 제어하는 락』을 나누어 이 두종류의락을 제공하는 ReadWriteLock을 도입해 봅시다. ReadWriteLock은『Writer 끼리 』및 『Reader와 Writer』의 배타 제어를 합니다. 『Reader 끼리』는 충돌해도 안정성에 영향을 주지 않기 때문에 배타 제어는 하지 않습니다. 이것으로 안정성을 잃어 버리지 않고 스루픗을 향상 시킬 수 있습니다. 이것이 Read-Write Lock 패턴이니다.
구현 : 자바에서는 finally를 사용하면 락의 해제를 잊어버리는 것을 방지할 수 있습니다.
관련 : Read-Write Lock 패턴의 ReadWriteLock이 배타 제어를 실현하는 부분에서는 Guarded Suspension 패턴을 사용합니다.
Writer가 전혀 존재하지 않을 때에는 Immutable 패턴을 사용합니다.
Producer-Consumer 패턴
문맥 : 어떤 쓰레드(Producer)에서 다른 쓰레드(Consumer)에 데이터를 넘겨준다고 합시다.
문제 : Producer 와 Consumer의 처리 속도가 다르면 늦은 쪽이 빠른쪽의 다리를 잡아끌어서 스루풋이 떨어진다. 또 Producer가 데이터를 쓸 때 동시에 Consumer가 데이터를 읽으려고 하면 안정성이 떨어진다.
해결법
Producer와 Consumer의 사이에 중간 지점이 되는 Channel을 준비합시다. 그리고 Channel에 복수의 데이터를 보유시킵니다. 그렇게 하면 Producer와 Consumer의 처리 속도 차를 완화할 수 있습니다. 또 Channel중에서 쓰레드의 배타 제어를 하면 데이터의 안정성도 잃어버리지 않습니다. 이것으로 스루풋을 떨어뜨리지 않고 더군다나 복수 쓰레드 간에 안전하게 데이터를 주고받을 수 있습니다.
이것이 Producer-Consumer 패턴입니다.
관련
Channel이 데이터를 안전하게 주고받는 부분에서는 Guarded Suspension 패턴을 사용합니다.
Future 패턴에서 반환값을 건넬 때에는 Producer-Consumer 패턴을 사용합니다.
Worker Thread 패턴으로 요구를 건넬 때에는 Producer-Consumer 패턴을 사용합니다.
ps. 쓰레드간에 직접 주고받는 통신을 하지 않고, 중간에 연결 고리를 두어서 그곳을 통해 거래를 하는 방식..