qktlf789456   3년 전

자료구조 힙 공부중에 Upheap 과 downheap 에 대해서 배워서 실습을 해보았습니다.

측정을 해보았는데 결과는 완전 반대였습니다.downheap 1.2초 1000만개데이터 중..upheap 7.2초 10만개 데이터 중.

이렇게 데이터수도 100배 차이나는데도 불구하고 upheap 은 7배가 더 느렸네요.. upheap 이 왜 이렇게 이론과 다르게 성능이 안 좋을까요?혹시나 코드가 잘못됬나 해서 여러번 다른코드랑 비교도해보았고,heap 이 제대로 된 heap 인지도 검증을 마쳤습니다.. 코드는 아래입니다.

doju   3년 전

구현 실수입니다. 반복문의 종료 조건으로 쓰이는 cur 변수의 값이 반복문 안에서 바뀌고 있습니다.

qktlf789456   3년 전

doju 님 예를들어 처음에 heap 에 추가할때, 0번인덱스에 가장 작은값이 들어갈경우(즉, 0번인덱스에 있는 값이 리프노드로 가야함) 이런경우에

바로 아래만 비교해서 처리하는 구문만으로는 맨 아래까지 보낼 수 없지 않나요? ㅠ

qktlf789456   3년 전

@doju

상향식에서 맨 아래만 비교했을때 한번이라도 swap 연산이 있었다면, swap이 없을때까지 맨 아래만 비교하는방식으로 구현해보아도 하향식보다 1.5배 가량 느린것을 확인했습니다.. 코드는 아래입니다.. 혹시 어떤부분이 구현이 잘못된걸까요?

doju   3년 전

반복문 내부(59~76번째 줄)의 동작이 57번째 줄의 cur 변수의 값을 변경해서는 안 된다는 뜻입니다. 예를 들어 말씀하신 대로 1번 노드가 하강을 거듭하여 100만 번째 위치로 가게 될 경우, 1번 노드까지 재배정이 끝났으니 heapify가 완료되었음에도 불구하고 cur = 1000000이 되었으므로 무의미한 반복문을 100만 번 돌게 됩니다.

qktlf789456   3년 전

너무감사드립니다. 정말 말 그대로 실수였네요 실수도 실력이지만, 그 결함을 발견하시고 바로 캐치하신 doju 님이 더 존경스럽습니다.

많은 프로그래밍을 해보셔서 이런식의 구현방식이 어떻게 다르게 동작하나 다 보이시나봅니다 대단하세요..

댓글을 작성하려면 로그인해야 합니다.