전
후
3배정도 더 빨라졌네요!! 코세님 짱짱 ㅋㅋ
그 20개 중에 하나는 큰 수가 나왔는데, 원인이 무엇일가요??
코세님의 조언대로 최적화한 결과
dddd(121.187)
2016-05-16 04:28
추천 0
댓글 78
다른 게시글
-
제한된 조건의 정수정렬에 대한 Radix VS qsort함수 속도 비교 [59]dddd(121.187) | 16.05.16추천 0
-
c++ 교집합 만드는거 [22]익명(163.180) | 16.05.16추천 0
-
[경희대]<몸과 문명>느낌과 감각 없이 존재하지 않는 것 [1]에어로홍(aerohong) | 16.05.16추천 0
-
어느 귀차니스트의 문제풀이 [3]익명(182.227) | 16.05.16추천 0
-
답은 "가독성"이다 [1]익명(210.113) | 16.05.16추천 0
-
컴공에서 제일 중요한 과목은 무엇인가익명(203.229) | 16.05.16추천 0
-
자바는 어떻게 압도적 1위를 이루어 낸것일까 [3]익명(203.229) | 16.05.16추천 0
-
1~100 까지 3과 5의 배수 표현 내 스타일. [9]codesafer(codesafer) | 16.05.16추천 0
-
왜 이클립스는 존나게 느린가? [3]dd(203.229) | 16.05.16추천 0
-
헬조선 기업에서 보는 인성이란 [1]ㅋㅋ(124.254) | 16.05.16추천 3
일단 정상동작하는지 확인을 해보셔야 해요. 그다음이 성능측정 ㅋㅋ
가끔 OS 가 시비걸때가있긴한데 아직은 특정할 수 없고, 성능을 위해 수정해야 될 포인트는 많아요.
가령, 마지막에 tmp 를 arr 에 복사하는게 낭비죠. tmp 를 외부에서 할당해 넘겨준다면, arr, tmp, arr, tmp .. 순서로 번갈아 넣어주며 복사 한번을 줄일 수 있죠.
정렬된 결과는 다 제대로 나오네요
radixSort 내부에서 tmp 를 동적할당해서 counterSort 의 추가 인자로 전달해주는 방법이 좋아요.
arr, tmp, arr, tmp .. 순서로 번갈아 넣어주며 복사 한번을 줄일 수 있죠. <= 쉽게 설명해주실수 있나요??
그러면 가장 큰 메모리인 힙을 이용해서 정렬하니 큰 배열 정렬할때도 유리하죠.
첨에 counterSort( arr, tmp, ... ) 를 전달해주고
counterSort 안에서 정렬된 결과를 arr 에 복사할 필요없이 그냥 리턴하면
그 다음 부를때는 counterSort( tmp, arr, ... ) 을 전달해주게 하는거죠
그럼 tmp 엔 앞선 버켓의 정렬결과가 들어 있으니 두번째 턴에서 arr 에 결과가 복사되게 되겠죠?
즉, arr 과 tmp 를 별도의 포인터 변수에 담아 놓고 두 변수의 주소값만 swap 하면서 루프를 돌고 나와서
최종 결과 포인터가 arr 이 아닐때만 복사해주면 끝.
이 방법을 쓰면 counterSort 의 마지막 복사 for 문 하나를 없앨 수 있다는 말씀.
그러면 arr도 동적으로 할당해서 사용해야 하는거죠??
아뇨 arr 은 radixSort 외부에서 만들어 던져줄테니
달리 그리하실 필욘 없어요.
tmp 만 radixSort 안에서 동적 할당
단 int* pages[] = { arr, tmp }; 처럼 선언해 놓고
int page_index = 0; 처럼 하고
for( .... ) counterSort( pages[ page_index ], pages[ page_index ^ 1 ], .... ); 로 호출하시면서
page_index ^= 1; 해주시면 알아서 뒤집어지겠죠.
감사합니다!! 그그. 번갈아 가면서 호출하려면 for (int exp = 0; (m >> exp) > 0; exp += 4) 여기서 if문을 줘서 번갈아 가면서 호출하면 되나요?
그런 뒤 정렬하고 나온 결과 page_index 가 0이 아니면 최종 결과가 tmp 에 들어 있는거니까 복사~!
if 가 필요없게 해 놨는디요.
page_index 를 뒤집게 해놨잖아요
page_index ^= 1 뒤집는다는게... swap된다는 말인가요/.?
저렇게 하면 첨엔 pages[ 0 ], pages[ 1 ] 로 호출되고 두 번짼 pages[ 1 ], pages[ 0 ] 으로 호출되죠. 물론 page_index ^= 1 을 루프 어딘가에서 해준다는 가정.
page_index 가 0 으로 초기화 되어 들어왔으니 XOR 1 을 하면 0일땐 1로 1일땐 0 으로 바뀌죠.
토글입니다.
사실상 변수 하나에 xor 하는걸로 swap 하는 역할을 한거죠.
대입 세 번 보단 싸니까유.
뭐 비슷하겠네요 배열을 이용한 간접 억세스라.
1.5 + 1.5 = 약 3
int* buf1 = arr; int* buf2 = tmp; 해 놓고 어딘가에서 swap( buf1, buf2 ); 하는거랑 삐까삐까 할듯.
존경합니다. !!!
다 했습니다!! 이해도 99.8% 완료했어요 ㅎㅎㅎㅎ
http://ideone.com/cvpXmI
countSort랑 radixSort만 확인해주시겠어요??
countSort랑 radixSort만 확인해주실 수 있나요?
호!
이해 속도가 빠르시네요.
동적 할당 하실거면 static 빼시구요 ㅋㅋ
getMaxValue 는 이제 이름이 바뀌어야 할듯.
그리고 getMaxValue 의 결과랑 비트 대역 비교한 보정 값을 구하는식으로 바꿔야하고
최종적으로 토글된 페이지 인덱스를 참고해 마지막 결과가 tmp 에 저장되어 있는 경우 arr 로 복사하는 작업이 들어가야 하죠.
counterSort 가 불리는 회수가 짝수면 상관없는데 홀수번 불린다면 필요하죠.
그런 자잘한 처리를 하고 나면 int 배열이 아닌 template 으로 바꾸셔야 하구요.
( 어차피 음수 처리도 못하는데 int 는 웃기죠 )
아아!! 그래서 여러번 while문 돌리니 런타임 에러가 나는 거였군요!
그러고 나서 고민해야 할 것은
부동소수도 처리할 것인가! 랑 음수 처리 테마예용.
http://cafe.daum.net/codeinside/b8FO/62
여기 보시면
부동소수를 서수로 서수를 부동소수로 바꿔주는 함수가 있어요.
만약 float 형 배열 같은걸 radix sort 하고 싶으시다면,
정수형과 달리 부호부 떼어 내면 절대값 처럼 비트가 증가하기 땜에, 저런식으로 비트연산으로 서수화 할 수 있죠. (부호무시 부동소수점 무시하게 만들어줌)
for 문으로 원본 float 값들을 모조리 unsigned int 로 바꾸고 나서 radix 돌리고 다시 unsigned int 서수를 float 으로 합성하면 정렬완료되는거죠.
기수 정렬의 특징이 음수와 부동소수에서 사용불가하다는건데 저걸 쓰면 동작합니다.
제가 심심해서 만들어본것.
double 형도 만들어뒀는데 어디뒀더라 =_=
여기서 서수란 표현은 좀 적합하지 않지만... 실제 값이 차곡차곡 쌓여있는 형태는 아니고, 일단 단순증가 형태의 monotone 은 보장한다는거죠.
홀수번 체크를 이렇게 햇는데 맞는거죠??.if (page_index & 1) {swap} 으로 했는데
아 정수 음수의 경우는 저걸로 동작안해요 저건 float 전용. 음수는 걍 2의 31승 더해서 돌리는게 속편하죠.
부동소수는 하.. 나중에 해봐야겠네요.. 어려울거 같아요 ㅠㅠㅠ
swap 을 해선 안되죠. if( page_index ) memcpy( arr, tmp ... ); 형태여야 하지 않을까요?
저기 제가 링크된 페이지에 가면 함수 두개가 있어요
코세님 정말 감사합니다!! 많은걸 얻어간거 같습니다!!
하나는 부동소수 -> 양의 정수인것처럼 바꿔주는거
다른건 양의정수인것 처럼 바꿔놓은걸 다시 부동소수로 바꿔주는거
아아!! 그러네요
넵 감사합니다!!!
그러니 그냥 float 타입의 배열 값들을 저걸로 바꿔친 다음 int* 로 캐스팅해서 radix 에 던져주고
정렬된 결과를 다시 저 두번째 함수를 이용해서 실제 float 값으로 변환해주면 됩니다.
저 링크 소스는 내일 분석해봐야겟네요.. 4시에 잘려다가 벌써 5시가 넘엇네요.. 4시간후에 학교 ㅠㅠ
for 문 한 줄이 radix 앞 뒤로 추가되는거죠 뭐.
ㅇㅇ 잘자유~
이 글은 에버노트에 넣어서 내일 다시 볼게요!! float도 구현해보겠습니다!! 감사합니다! 코세님