ksjb2897   1년 전

비트마스킹을 쓰는 이유가 시간절약이 아니라 메모리 절약뿐밖에 없나요?

간단한 사칙연산으로 여러개의 연산을 수행할 수 있어서 시간도 더 빨라질 것 같은데,

이 문제를 배열을 20개 구현하여 푼 속도가 비트마스크로 구현하여 푼 속도보다 빠릅니다...

배열로 집합을 구현하니까 600ms근처인데 비트마스크는 700ms가 넘어요..

밑의 코드는 배열로 구현한 것인데 왜 비트마스크보다 빨랐는지 설명 들을 수 있을까요? ㅠㅠ

munji123   1년 전

엄밀하지 않지만 그래도 제 의견을 적어보자면

배열로 구현하신거는 84byte의 배열밖에 접근하지 않아서 한번 캐싱해놓으면 캐시미스가 안뜨는 반면,

비트마스킹으로 구현하게 된다면 마스킹 연산을 위해 추가적인 상수를 이것저것 쓰게 되는데 (예를들어 1<<x 이런식으로) 자주 사용하지 않는 상수들은 캐시미스가 뜰 확률이 높기때문에 그렇지 않을까 조심스럽게 생각해봅니다. 물론 이것도 최적화 레벨에 따라 다를 수는 있을 것 같습니다

djm03178   1년 전

먼저, 두 코드의 속도를 비교하려면 말로만 차이를 설명할 것이 아니라 두 코드를 모두 온전하게 올려주셔야 정말로 단지 그 차이만으로 속도가 달라진 것인지 알 수 있습니다.

제출하셨던 코드를 직접 찾아서 봤는데, 두 코드의 차이는 비트마스킹이 느려서 발생한 것이 아닙니다. 비트마스킹을 한 코드에서는 check 명령에 대한 출력을 %d를 이용하여 하고 있는데, printf가 서식 문자를 해석하고 그에 따라 주어진 정수값을 대응하는 문자열로 변환하여 출력하는 것은 고정된 문자열을 바로 출력하는 것에 비해 현저히 느립니다. 그래서 코드에서 직접 분기를 나누어 "0\n" 또는 "1\n"을 바로 출력한 코드에 비해 훨씬 느린 것입니다.

http://boj.kr/c5338ee47a174652...

이와 같이 출력문 부분을 동일하게 바꾸어주면 배열로 구현한 코드와 거의 차이가 나지 않는 것을 볼 수 있습니다.

ksjb2897   1년 전

친절한 답변 감사드립니다 !! 이해했습니다 감사합니다!

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