Java Puzzlers - Scraping the Bottom of the Barrel (Google I/O 2011)

포털을 돌아다니던 중에 재밌는 Java 요소를 발견했습니다. 바로 Google I/O 2011에 있었던 Java Puzzler라는 것인데요. 

이 영상에서는 발표자 JOSH BLOCH, JEREMY MANSON 두 사람이 6가지의 Java 프로그래밍 언어의 퍼즐을 발표합니다.

먼저 그 첫 번째, Time for a Change,

영상에 나온 소스대로 입력했을 때, 거스름 돈은 얼마입니까? 라는 문제지요. 여기서 가장 중요한 것은, 자료형이 double이라는 것입니다. 

거스름돈은 0.8999999999999999가 나옵니다. 왜 그럴까요?

Java에서 double 연산은 정확한 값을 제공해주지 않는다며, big decimal을 사용하라고 권장합니다. 따라서 Big Decimal을 사용해 다시 한 번 연산을 해보도록 합시다.

1. A change is Gonna Come

자 이번엔, BigDecimal 클래스를 사용해서 소스를 다시 한 번 입력해봤습니다.

영상에서 보기 a, b, c, d 중 답을 고르라고 하지요. 그런데, 과연 답이 있을까요? 정답은 a,b,c 모두 아닌 d : 정답이 없음. 이 맞습니다. 청객들 모두 웃고있죠 ㅋㅋㅋ 자 그럼 답이 어떻게 나왔는지 제가 한 번 이클립스에서 코딩을 해 본 결과, 0.899999999999999911182158029987476766109466552734375 라는 어마어마한 값이 나왔습니다. 왜 그럴까요?

분명 영상에서도 BigDecimal 클래스를 사용하라고 권장은 했습니다. 하지만 BigDecimal 클래스를 사용하고, 인자값을 double 자료형을 사용했기 때문에 저런 결과값이 나오는 겁니다. BigDecimal(double val)은 double 값을 BigDecimal로 표현하는 경우이므로 그냥 double을 쓴 것이나 다름이 없지요. 

그래서 위 영상에서는 double이 아닌 String 으로 인자값을 사용하기를 권장합니다. 정확한 값의 도출은 항상 double 자료형이 아닌 String을 사용합시다.

OK? 쉬우면서도 정말 유용한 첫 번째 퍼즐이었습니다.

2. Size Matters

두 번째는 사이즈(크기)와 관련된 문제인데요. 여기서 다루는 것은 Map입니다. Map에는 종류가 많지요. HashMap, TreeMap, EnumMap .... 그 중 여기서는 HashMap과 EnumMap을 다루고 있습니다.

자 이 코드에서는 어떤 결과가 출력이 될까요?

영상에서는 2 1 이 출력된다고 나옵니다만  현재는 2 2 정확하게 나오고 있네요. 차례차례 살펴보도록 해보지요.

먼저 영상에서 잘못됐다고 지적하는 size 소스에서 MALE FEMALE을 넣어주고, 마지막에 Set 한 경우인 HashSet을 보도록합시다.

key값을 가져와서 계산한 다음 addAll 함수를 취하고 있군요.

addAll 함수를 보면, Iterator 패턴을 통해, hasNext를 통해서 끊임없이 반복하고, 그 반복을 통해 modified 를 리턴해주고 있습니다. 한 마디로 노가다이지요;;

Map으로 정의된 모든 값을 받아와서 저장하는군요.

영상에서 제기하는 문제는 바로 이 부분입니다. 바로 EntryIterator 부분인데요. 이 소스는 openjdk6-b14에 담겨있는 소스 코드입니다. 문제가 되는 부분은 openjdk6 버전에서만 오류를 냅니다. 영상이 2년 전 것이라 써나가다보니 그렇군요. 소스 코드를 살펴보자면 값을 가져오고 next로 반복을 하면서 this값을 리턴하고 있습니다. 즉, Iterator만 돌고 있고, Entry는 제자리 걸음을 치고 있군요. 보통 Next(); 문을 거치게 되면, 새로운 Entry가 생성되면서 return이 됩니다. 그런데 위 소스처럼 EnumMap EntryIterator는 Entry는 내버려두고, 순서값만을 가져오고, 또 새로 가져오고 이런식이지요. 즉, 영상에서 말하는 것처럼 Entry 없이 그냥 단순히 순서에 맞는 key, value만 가져다가 return하게 됩니다. EnumMap은 특성상 처리 속도가 빠르다는 특징이 있어 자주 사용하는 편이었는데, 이런 잘못된 값을 출력하는 부작용이 있었군요. 이 버그는 1997년부터 존재했었으며 IdentityHashMap, ConcurrentHashMap, EnumMap 모두 이런 형태로 갖춰져있어 같은 영향을 미친 모양입니다. 다행히 안드로이드에는 적용이 안되어있다고 하는군요 ㅋㅋ;

위 소스는 현재 고쳐진 openjdk7-b147 소스입니다. 위 소스와 달리 Iterator 반복과 동시에 Entry를 생성하면서 나아가고 있군요. EnumMap을 사용해서 소스 코드 작성시 참고바랍니다.

위 영상에서 제안하는 수정된 소스 코드입니다. 최신 버전에서 원 소스가 고쳐졌으니 굳이 AbstractMap을 써가면서 까지 추가하는 것은 추천하지 않습니다만 jdk6에서 꼭 사용해야할 경우에만 참고하시는걸 추천합니다.

3. The Match Game

Pattern이라는 메소드를 가지고 만든 Match Game 소스 코드입니다. 솔직히 말하자면 주어진 Pattern 부터가 조금 과한 Pattern 입니다만. 어쨌든 어떤 결과를 출력해줄까요?

아니나 다를까, Java에서 정확한 갯수를 표시해주지 않는군요. 

여기서 발표자가 언급하는 것이 바로 catastrophic backtracking이라는 것입니다. 

영상을 보면, 중첩되면서 실패하는 것까지 다 포함해서 매칭한다고 합니다. aab? 정규식과 비슷한 aa|aab? 방식을 써보니 JVM이 날아갈 듯이 멈추질 않더라구요 ㅋㅋ; 이처럼 Pattern 메소드를 이용해서 정규식을 사용해 색인을 하는데, 위 소스처럼 두 가지 이상의 조건으로 색인을 할 경우, 과부하가 발생합니다. 이는 Java 뿐만 아니라 PHP, Perl 등도 마찬가지라고 합니다. Java에서는 아마 순환되는 정규표현식을 탐지해내서 프로그램을 멈추고 0을 표시하는 듯합니다.

4. The Sinking Feeling

package javapuzzler;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

abstract class Sink<T> {

abstract void add(T... elements);

void addUnlessNull(T... elements) {

for(T element: elements) {

if(element != null) {

add(element);

}

}

}

}

public class StringSink extends Sink {

private final List<String> list = new ArrayList<String>();

void add(String... elements) {

list.addAll(Arrays.asList(elements));

}

public String toString() {

return list.toString();

}

public static void main(String[] args) {

Sink<String> ss = new StringSink();

ss.addUnlessNull("null", null);

System.out.println(ss);

}

}

이번 소스 코드는 추상 클래스를 사용한 코드인데요. 과연 어떤 결과가 나올까요?

오류를 뿜어냅니다. 잘못된 부분이 있지요?  하지만 영상의 보기에 있는 오류는 아닙니다 ^^; ClassCastException 오류가 뜨는데요. 영상에서는 패키지 선언하는 부분이 stack trace에 들어갔다는군요. 컴파일러의 버그인 듯합니다. openjdk7에서는 패치된 사항입니다. 

그 외, 영상에서 (1)로 표시된 부분은 Varargs로 처리하는데, 웃긴건, 얘가 Arrays 배열로 처리한다는 것입니다. 그래서 주석에 Creates String []을 붙여 ss.addUnlessNull = new String[] ("null", null)을 사용하는 것과 같다고 얘기합니다. 그 다음 (2)로 표시된 부분에 T... 로 된 부분 솔직히 저도 여기가 뭔지 궁금했었는데, 이 부분은 object[]로 받아서 JVM이 처리한다고 하는군요. 결국 String이라고 생각했던건 저의 착각이었습니다;; 그리고 Bridge Method라는 것이 영상에서 언급되고 있는데, 정말 미스테리어스 하한 부분이 많다는 주장과 덧붙여 설명합니다. 추상 클래스에서의 add부분, 이 부분 밑에서 사용하지요. 그런데 밑에서는 String[]을 사용하고 있고, 위에서 얘기했듯이 T... 로 된 부분은 object[]로 받는다고 하였습니다. object[]를 String[]으로 전달할 수 없는데도 java에서 오류를 내지 않고, 컴파일을 하는 것으로 보아 JVM에서 어떤 메소드를 생성하는데, 그것을 Bridge Method라고 하는군요. 그런데 실제로 Eclipse에서 코딩을 직접 해봤는데, 안됩니다;; ㅋㅋ Eclipse에서는 직접 @override를 적지 않으면 컴파일이 안되더군요. 나중에 알고보니 맨 첫 번쨰 줄에 있던 패키지 부분 stack trace가 바로 저걸 의미한다고 하더군요. 

위 소스가 바로 완전히 고쳐진 소스입니다. 영상에서 object에서 string으로 넘기는 bridged method의 사용은 매우 나쁘다고 주장하여 그 방법을 버리고, Collection을 사용하였습니다. Collection을 사용함으로써 코드의 수를 줄이고, 불필요한 과정을 생략했다고 얘기합니다. 그리고 영상에서 중요하게 언급한 것처럼 작은 오류, 경고 하나도 소홀히 하지 맙시다 ㅎㅎ

5. Glommer Pile

Arrays.asList로 1 2 3 을 주고 메소드대로 출력하라는 소스군요. 자 이 소스에서 나타나는 오류가 과연 있을까요? 영상의 기준은 openjdk6 버전이라는 것을 염려해두셔야 합니다 ㅎㅎ

자 답은 오류가 나온다죠, 여기서 언급하는 것은 Raw type은 위험하다고 합니다. 왜 그럴까요?

지금은 Raw type을 써도 JVM에서 알아서 처리해버리지만, 당시에는 Raw type으로 받을 경우, Generic Type (어떠한 객체를 미리 명시함으로써 형변환을 하지 않고 사용하는 타입) 객체들이 모두 없어진다는 것입니다. 이것도 컴파일러의 버그인 듯합니다. 

package javapuzzler;

import java.util.Arrays;

import java.util.Collection;

import java.util.List;

public class source5 {

String glom(Collection<?> objs) {

String result = "";

for(Object o : objs) {

result += o;

}

return result;

}

int glom(List<Integer> ints) {

int result = 0;

for(int i : ints) {

result += i;

}

return result;

}

public static void main(String[] args) {

List<String> strings = Arrays.asList("1", "2", "3");

System.out.println(new source5<Random>.glom(strings));

}

}

위 소스에서 고쳐야할 사항은 첫째로, 클래스의 파라미터 타입을 아무거나 넣어서 사용하라는 것. 어떤 것이든 상관없다고 합니다.

둘째, 클래스의 generic 파라미터를 사용하지 않는 것. 솔직히 이 소스에서 T 전혀 안 사용하기 때문에 지워도 무방합니다.

마지막으로, glom 메소드를 static 메소드로 정의하는 것입니다. glom 메소드도 아무런 영향이 없기 때문에 static으로 해도 영향이 없답니다  그리고 항상 영상에서 강조하는 것은 컴파일러 말좀 들어달라는 이야기군요 ㄱ-;; 

6. It's Elementary (2004; 2010 remix)

마지막은 굉장히 간단합니다. 첫번재 문제보다도 훨씬 간단하죠. 자 과연 출력 결과는 어떻게 나올까요?

숫자 가지고 놀아본 사람은 다 알만한 사실입니다. 그런데, 왜 이런 결과가 나오는걸까요?

Java에서 0을 앞에 놓게되면 decimal, 즉 8진수로 처리되어 10진수의 결과가 나와서 668이 찍혀버립니다. 이는 java 뿐만 아니라 C언어도 마찬가지입니다. 답은 간단하지요? 0 지워주시면 되겠습니다~

그리고 발표자분 께서  I l 가지고 장난치지 말라고하는군요.. ㅎㅎ 혹시 호기심에 해보신 분들 분명 있으실 것 같습니다. (저도 해봤지만요ㅜㅜ)

마지막으로 이 포스팅을 적게된 계기는....

2년 정도 넘어서 이제와서 보면, 조금 의미가 없는 부분도 있지만 어떻게 보면 꼭 남기고 싶은 영상이자 글이기도 합니다. 중요한 내용도 언급이 잘 되어 있고, 미래의 프로그래머들을 위한 대학생 내지 혹은 그걸 희망하고 있는 청소년들에게도 좋은 내용이 아닐까 합니다. 그리고, 제가 개인적으로 보관하고 싶은 아이템이기도 하구요. 이번 포스팅은 여기서 마치겠습니다.