'알고리즘'에 해당되는 글 1건

  1. 2010.07.28 [Java] equals의 활용. 더 나아가 코드 구현의 방법. - 1 -
이번에 작성하는 내용은
딱히 어떤 주제를 정하기가 좀 그렇네요..

먼저 이 내용은 어떤 코드가 제일 좋다 나쁘다를 얘기하기 위한 것은 아닙니다.
약간의 생각의 전환이 많이 다른 결과를 가져 올 수도 있다는 것을 이야기 하고 싶어서
작성하는 글 입니다.

제가 최근에 한 소스에서 본 내용을
리팩토링 했던 내용을 적어 보려고 합니다.

7일치의 검색어와 그 검색어의 검색 횟수를 합산하는 프로그램이 있습니다.

일단, 어딘가의 로그에서 하루 단위의 각 검색어와 그 검색어의 검색 횟수는 가져 올 수 있다고 가정하고
하루에 검색횟수 상위 5만개의 검색어를 7일치 가져와서
각 검색어의 검색 횟수를 합산하고 이것을 merge하여 다시 검색 횟수순으로
정렬하여 보여주는 프로그램입니다.

어떻게 보면 map and reduce고요..
어떻게 보면 그냥 group by 검색어 sum(검색횟수) 정도가 될 것 입니다.

아무튼..
raw 데이터가 검색어:검색횟수이기 때문에
이것을 가지고 위의 내용을 구현한 소스가 있었습니다.

일단, 검색어와 검색횟수를 받을 수 있는 domain 클래스를 하나 만들었습니다.


TestDomain.java

검색어는 keyName으로, 검색횟수는 count로 들어갑니다.
이것은 실제 테스트 클래스에서는 INNER CLASS로 사용 될 것 입니다.

초기 데이터 (일 상위 5만개의 7일치 검색어 리스트)는 아래와 같이 셋팅하려 합니다.

초기 데이터 셋팅
하루치 검색어 리스트에 해당하는 list_N 을 7개 만들고
각 리스트에 대해 5만번씩 loop를 돌면서 i를 검색어를 셋팅합니다. (하루 단위의 검색어:검색횟수는 이미 집계되어
있기 때문에 하나의 리스트에 중복되는 검색어는 없다고 가정합니다.)
그리고 각 검색어의 카운트는 3000까지의 정수 중 random으로 나오는 정수를 셋팅합니다.

이렇게 하면 각 list를 add한 initDatas의 사이즈는 350000이 될 것 입니다.

그럼 이제 각 리스트에서 검색어를 뽑아서 어떻게 7일치의 검색어와 검색횟수를 구할 수 있을까요..?

제가 처음 본 소스는 아래와 같이 되어 있었습니다.

일단, merge된 결과를 담을 List를 생성합니다.
List<TestDomain> resultList = new ArrayList<TestDomain>();

그리고, 전체 키워드:검색횟수가 담겨있는 initDatas를 loop 돌면서
resultList를 뒤져서 그 키워드가 resultList에 있으면 각각의 count를 더해서 set하고
resultList에 없으면 resultList에 TestDomain을 add하는 형태로 되어 있었습니다.

기본 룰은 맞는데
문제는 resultList에 검색어가 있냐 없냐를 구분하는 것을
contains를 사용하지 않고(못 했을 수도 있죠..) keyname을 get하여 equals로 비교하고 있었습니다.


Test.java 첫번째 방법
위 소스를 돌려보면..
상황에 따라 조금 다르겠지만

initData size : 350000
loopCnt  : 8750475000
수행시간 : 1110초

이정도가 나오게 됩니다. 2번째 for문에서 break가 얼마나 빨리 실행되냐에 따라서 약간의 차이가 있겠지만
대략 수행시간은 큰 차이가 없을 것 같습니다.

1110초면 약 18분 정도의 시간이 소요됩니다.

그럼 이 코드를 살짝 바꿔보겠습니다.

예전에 OOP에 대한 이야기를 하면서 Object 클래스의 메서드인 equals 메서드에 대한 이야기를 한 적이 있습니다.
(http://devyongsik.tistory.com/290)
List에 어떤 객체가 있냐 없냐는 loop를 돌면서 equals로 계산 할 것이 아니라
equals 메서드를 구현하여 List의 contains 메서드를 활용하자는 이야기였죠.

이것을 바탕으로 TestDomain 클래스에 equals 메서드를 구현하고 이것을 가지고
약간의 소스를 수정해보겠습니다.



Test.java 두번째
TestDomain에 equals 메서드를 구현하고 List의 contains 메서드와 indexOf 메서드를 사용하여
같은 로직을 구현하도록 하였습니다.

initData size : 350000
loopCnt  : 350000
수행시간 : 856초


일단, 성능은 둘째치고라도 for문이 하나로 줄어들었고 이에 따라 loop의 횟수도
줄어들게 됩니다. (하지만 내부적으로 contains와 indexOf 메서드가 결국 해당 object를 찾기 위해서 배열을 loop 돌면서
같은 행동을 하고 있습니다.)

그럼에도 불구하고 속도가 빨라진건 당연히 loop 하나가 사라졌기 때문이겠죠...

하지만 뭐 획기적인 속도 개선은 없는 것 같습니다.

다른 방법이 무엇이 또 있을까요? loop를 줄일 수 있는 방법. 현재는 최대 350000번의 loop를 contains와 indexOf안에서
또 각각 돌고 있기 때문에 이것을 줄이기 위한 방법을 찾아야 할 것 같습니다.

굉장히 간단한 방법이 있죠.. contains 메서드를 indexOf 한번으로 대체하는 것 입니다.



이렇게만 해줘도
결과는 아래와 같이 나옵니다.

initData size : 350000
loopCnt  : 350000
수행시간 : 472초

그럼 또 다른 방법은 없을까요?

-계속-
Posted by 용식