제한된 조건의 정수정렬에 대한 Radix VS qsort함수 속도 비교
dddd(121.187)
2016-05-16 03:36
추천 0
댓글 59
다른 게시글
-
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
-
저 문제가 왜 Python이면 달라질 게 없냐? [2]밍고스사랑..(mingosudaisuki) | 16.05.16추천 0
10개짜리 버킷은 안좋아라하는데 ㅋㅋ
16개로 해주세유!
비트연산도배가능.
16진수로 하라는 말씀이신가여??
16 개로 하면 % 10 대신 & 0xF ( 15 )
아아
/ 16 대신 >> 4
* 10 대신 << 4
위에 /10 대신 : )
글고 tmp 를 지역변수로 선언하면 확장성이 없음유.
코세님 로 하게되면 나머지가 0, 1,2~14으로 나오는데.. 으로 하면 안되나여?
1메가 이상 되는 자료를 처리할 수 없으니.
나머지가 0~15 가 되쥬.
그래서 버킷 크기를 15로 잡아야 되는거구.
아니지 16
/, *, % 만 >>, <<, & 로 바꾸시면 됩니당.
R 값도 16으로 바꾸시구유
혼자 따로 놀고 있는 % 10 도 사실은 % R 이쥬?
*= 10 도 * R
감사합니다!! 지금 수정중이에요 !!
코세님 / exp 를 >>4로 처리하게되면 다음 exp (exp<<=4)가 적용이 안되지 않나요??
아 / exp 는 그대로 둬야 하죠.
음 위랑 엉기는구나. 그냥 exp 를 비트 쉬프트 할 자릿수로 두시면 됩니다.
getMaxValue 랑 개념이 엉기는데요
일단 조금 안이쁘지만 if( m & 0xF0000000 ) mm = 28; else if( m & 0x0F000000 ) mm = 24; ... 해서 mm 이 비트수 한계를 표현하게 해 놓고
코세님
mm 이랑 exp 랑 비교하는 루프로 바꾸시면 될듯.
넵.
그그 제가 고치긴 고쳤는데.. 계속 tmp[numberCnt[(arr[i] >> exp) & 0xF] - 1] = arr[i]; 이부분에서 런타임 오류가 나요 ㅠㅠ 소스를 올릴게요 잠시만여
사실 이경우 getMaxValue 가 부적절하죠. max 값을 구하는게 아니라 전체 OR 을 구하는게 더 효율적 조건문도 하나 줄일수 있고.
http://ideone.com/3lEK5a
전체 OR이여??
넵
모든 요소에 대해 OR 을 누적시키면, 몇번째 비트까지 처리해야 하는지 보이겠죠
그러면 적정 버킷 스탭이 나옵니다. 버킷 크기는 16을 쓸거니까요.
아아아!!!
OR 이 max 구하는것 보다 싸죠. 당연히 조건문 하나 빠지니까.
근데 전 저 max 구하는거 안좋아해요.
작은값 가지고 놀땐 이득도 있지만
float 나 double 에 적용할땐 소용없거든요.
지수부가 0인 경우가 거의 없어서리 ㅋㅋ
max 구하는것도 비용이기도 하고.
소스코드 볼게유~
max 함수도 고쳤는데,, 숫자들이 정렬이 안되요 ㅠㅠ
일단 다시 확인해볼게요..
글고 tmp 를 지역변수로 선언하면 확장성이 없음유. <<== 이 말이 무슨 뜻인지 알려주실 수 있나요?
ㅋㅋ 16개랑 15개랑 착각하셨네유
배열은 16개여야 하고 & 는 15 여야하고.
음 지역변수는 스택에 할당되는데 윈도우에서는 기본스택크기가 1메가바이트로 설정되어 있어서 25만개를 넘는 int 를 선언해버리면 바로 프로그램이 뻗죠.
getMaxValue 결과가 쓰레기 값이 나오네요.. 머지
1000 * 1000 짜리 1메가 픽셀 이미지의 픽셀 밝기값을 정렬해야 한다면 좌절이죠.
아아!! 그럼 전역변수로 선언해야 하는거죠?
0xF가 15인걸로 알고이는데.. 0xE로 하면 런타임 에러가 안나는데 0xF로 & 하면 런타임 에러가 나요
http://ideone.com/nxXWNN
아아 배열!!
오오 됬어요 !!
우와 속도가 ㄷㄷㄷ
전역이든 static 지역이든유~
qsort 는 원래 얼빵하니 std::sort 랑 비교해보세요