블로그 이미지
bro.Yobi

Rss feed Tistory
CSE/Algorithm 2009.06.08 19:50

데이터가 많으면

학생때는 생각하지 못했던 문제들에 부닥치게 된다.

 최단경로 문제를 흔히 많이 쓰는 Dijkstra 알고리즘으로 구현하려고 했다.

하지만 Bellman Ford가 구현이 더 쉽기 때문에 1차적으로 벨만 포드로 구현했다. (또한 결과 값을 비교해보려고..)

그/런/데 Out of memory exception…

보통 그래프를 2차원 행렬로 표시한다. 하지만 노드의 개수가 10만개가 되어버리면..

Edge 정보를 1byte로만 잡아도 10의 10승(10기가) byte가 필요하다. ㅋㅋㅋ

 

그래서 대안적으로 리스트로 구현했다.

당연히 아주 느릴거란걸 예상하면서..

그런데 그 아주가 그렇게 아주인지…. 도무지 끝날 생각을 않는다.

 

그래서 리스트에 해시테이블까지 써가면서 복잡한 자료구조를 구현했다.

물론 많이 빨라졌다. 그래도 문제 푸는데 1시간 정도 걸린다.

 

퇴근 시간 조금전에 처음으로 돌아가서 Dijkstra로 해결해보려 Heap까지 만들어가면서 만들었다. 아주빨랐다. 파일로부터 데이터를 읽는 시간이 알고리즘 돌리는 시간보다 길었다.

하/지/만 결과가 Bellman Ford로 얻은 결과에 비춰볼 때 약간 이상한게 있었다.

"어디가 잘못됐을까나.." 생각하다가 집에 왔다.

밥먹으면서 생각났다.

ref를 빼먹었다는거..

TOTAL 238,851 TODAY 2