[Java] ArrayList의 removeAll과 HashMap의 remove 비교.

일을 하다가 발견한 문제이다.

특정한 동작을 하는것이 있었는데..
이 놈이 유독스럽게 Mac 에서만 무진장 오래 걸린다는 문제 였다.

윈도우에서는 단 1초도 안되어서 끝나는 작업이었지만,
Mac 에서만 22초가 소요되고 있었다.

문제가 어디서 발생하는지는 찾았는데,
왜 Mac 에서만 유독 느린지 이유를 밝혀 내지는 못했다.


여하튼, 문제는 ArrayList의 removeAll 메소드에 있었다.
removeAll 메소드에 대해서 좀 살펴 보자.



ArrayList 의 상속 관계를 보면 아래와 같다.

여기서 removeAll 이라는 메소드는 Collection 에서 interface를 제공하고 있으며,
실제 그 구현은 AbstractCollection 에 아래와 같이 되어 있다.

보다시피 현재의 컬렉션에서 param 으로 들어온 컬렉션에 있는 item들을 모두 지우기 위해서
iterator 를 구하고, next를 하나꺼내와서
param으로 들어온 c 에 이미 들어 있는지 확인을 하고,
들어 있다면 지워주는 형태로 되어 있다.


여기서 다시 "c에 이미 들어 있는지 확인하는 c.contains( .. ) 의 코드는
indexOf(Object)가 0 보다 큰지 확인하게 된다.
이때 ArrayList의 indexOf(Object) 는 아래와 같이 구현되어 있다.

열심히 이미 가지고 있는 배열에서 루프를 돌면서 같은 놈이 있는지 확인을 한다.
물론 이 놈들이 Object 형태를 비교해야 하기 때문에 equals() 메소드를 사용하여서
비교를 한다.


그렇다면 내가 원래 있던 20개의 Collection 에서
10개의 데이터를 removeAll 한다고 해 보자.

1. AbstractCollection의 removeAll을 호출한다.
2. 20개에 대해서 iterator 를 구해서 20번 루프를 돌아야 한다.
2.1. 현재 선택되어 있는 아이템이 10개에 포함되어 있는지 확인해야 한다.
2.2. 이것을 확인하기 위해서는 indexOf() 를 수행해야 한다.
2.3. indexOf 내부에서는 10개에 대해서 루프를 돌아야 한다.
2.4. Object 비교이기 때문에 equals 를 수행하기 위해서 내부적인 연산을 해야 한다.


중요한것은 전체 배열에 대해서 이중 for loop 를 돌아서 처리 한다는것이다.




그렇다면 이 loop를 좀 더 덜 돌릴 수 있는 방향이 없을까?
항상 cpu 와 memory 사이에는 trade-off 가 있다.
물론 지금 이야기 하고자 하는 방법은 memory 측면에서는 손해 볼 수 있다.




내가 그래서 선택한 방법은 HashMap을 사용하는 방법이다.
안타깝게도 HashMap 에서는 removeAll 같은 메소드를 제공해주지 않기 때문에.
직접 for 루프를 돌아 가면서 데이터를 지워주어야 하는 귀찮은 점은 있다.

HashMap의 remove(Object) 코드는 아래와 같이 구성되어 있다.

remove(Object)를 수행하게 되면 removeEntryForKey(Object)를 수행하게 된다.

이때 removeEntryForKey(Object) 에서는
param으로 들어온 key에 대해서 hashCode() 를 구하고,
전체 배열 중에서 구해진 hash와 같은 값을 가지는 위치만을 비교 하게 된다.


그렇다면 HaspMap 에서 데이터를 지우는 순서를 보자.

1. removeAll이 없기 때문에 어쩔 수 없이 외부에서 for를 돌려서 remove 를 여러번 시켜 준다.
2. hashCode() 값을 구하고, hash 같은 배열 부분만을 검색한다.
3. equals()를 호출하여 비교하면서 처리 한다.

여기서도 사용자가 for를 외부에서 돌려 주고,
내부에서도 while loop를 도는 2중 loop 구조이기는 하지만,
hash 가 같은것만 돈다는것이 핵심이다.


이 결과는 equals()과 hashCode()를 구현하는 방식에 따라서 다른 결과를 도출할 수도 있다.



약 400개의 데이터에 대한 작업이었는데
ArrayList.removeAll()에서는 22 초가 걸렸었고,
HashMap.remove() + for 로 수정한 뒤에는 0.5 초대의 시간이 걸렸다.


이 결과는 Mac 에서만 유용할 수도 있다. 실제 윈도우에서도 약간 더 빨리 동작하기는 했다.
시간 날때  똑같은 코드가 왜 Mac 에서만 이렇게 느리게 동작하는가에 대한 조사를 해 보아야 겠다.


대학교 자료구조 수업 시간에 자주 등장하는 내용이지만,
실제로 이렇게 -_- 겁나게 차이를 느껴 보기는 처음이었다. -_-;


대학교때 공부 잘했던 사람들이 나와서도 잘 사는 이유가 있나 보다. ㅋㅋ