wwiiiii   3달 전

같은 알고리즘이라도 구현에 따라 시간이 꽤 차이나던데, 코드를 짤 때 이렇게 하면 꽤 빨라지더라 하는 팁같은게 있으면 공유해주세요!

제가 알고 있는건 적절한 루프 풀기, 다차원 배열에서 이터레이터 중첩 순서(캐시 효율), 정수 나눗셈 대신 비트 연산자, inline/매크로 함수, 루프 이터레이터 register 변수로 쓰기 정도인데 다른건 뭐가 있을까요?

dtc03012   3달 전

cin cout 말고 scanf 랑 printf 하면 빨라져요

그리고 printf 하는것보단 getchar 가 더 빨라요(이 부분은 확실하지 않으니 주의하세요)

yukariko   3달 전

나눗셈 대신 비트연산자 사용 register 변수 등은

대부분의 컴파일러는 자체적으로 최적화를 해줍니다.

2의 배수 뿐만 아니라 3으로 나누는 경우에도 그렇습니다. (gcc로 실제 확인)

최적화 기법은 찾아보면 여러가지 있지만 빠른시간에 문제를 풀어야하는 PS에서 적용하기엔 무리가 있는 경우도 많죠.. (loop unrolling 같은)

제가 생각하는 실용적인 최적화는

1. 적절한 자료형 선택

문제를 풀다보면 숫자의 범위가 int 인것도 있지만 0~10000 같은 작은범위일 때도 종종있습니다. 이런숫자를 배열에 담을때 int로 하는것보다 short로 할때 확실하게 성능차이가 있습니다. 메모리 감소는 덤으로.. 특히 bool 형으로 표시 가능한 경우 int형의 경우보다 체감하기 좋습니다.

2. 초기화에 memset 활용

배열을 0이나 -1등으로 초기화 하는 방법은 배열을 선언과 동시에 초기화 하는 방법(0 한정), for문으로 직접 적용, memset, std::fill 등이 있는데 저는 memset을 추천합니다.

memset은 내부적으로 8바이트 단위의 초기화가 되어있습니다. 따라서 int형 배열 초기화에 for문보다 적어도 2배이상 빠르게 동작함을 알 수 있죠.. 특히 테스트케이스가 존재하는 문제에서 효과가 많습니다.

3. 테스트케이스 번호로 초기화

초기화에 memset을 권장하였는데 배열이 크고 테스트케이스 수가 많은 경우는 이것도 시간초과로 연결되는 경우가 있습니다. (경험 有) 이 방법은 visit 체크같은 중복처리 방법에 특화되어있는데,

중복처리를 0이나 -1등 정해진 숫자로 하지않고 테스트케이스 번호로 하는 방법입니다.

예를들면

if(visit[pos] == true)

  return;

visit[pos] = true;

이런 코드 대신


if(visit[pos] == tc)

 return;

visit[pos] = tc;

이런 코드를 사용한다면 매번 초기화할 필요가 없어집니다. 만약 배열의 용도가 t/f 가 아니라 정수범위로 저장해야한다면, 아예 visit을 위한 새 배열을 만들어주는것도 방법입니다.

이미 다 아실거라고 생각합니다만.. 이정도가 일반적인 경우에서 사용하는 최적화가 아닐까 싶네요.. 더 있을법도 한데 당장에 기억나진 않네요.

사실 캐시효율만 고려하면서 코딩해도 최적화 옵션을 포함하여 웬만큼은 최적화가 된다고 생각합니다..


추가적으로 wwiiiii님의 미로탐색 bfs코드를 보았는데, bfs에서 모든쌍의 최단경로가 필요한게 아니라 미로문제처럼 시작-도착 간의 최단경로만 필요하다면 visit 배열을 bool형으로 선언하여 최단경로를 구할수도 있습니다. int형이 bool형이 되니 시간은 더 줄어들겠죠.

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