doju   3년 전

(07-18 23:15 본문 재작성)

이 문제는 fread나 mmap 등의 충분히 빠른 입력 방법을 적용하고 나면 입력을 파싱하는 과정이 실행 시간에서 큰 비중을 차지하게 됩니다. 이때 파싱 전략의 설계 및 구현, 그리고 입력 데이터의 구성에 따라 성능이 달라지는데, 현재 모든 데이터의 답이 2×1013 이상인 것으로 볼 때(#63701001) 모든 데이터가 균등 분포에 따라 랜덤하게 생성되었거나 큰 수로만 이루어진 것으로 추측됩니다.

아래 제너레이터로 생성되는 데이터는 각 자릿수가 모두 균등하게 등장하며, 제가 작성한 풀이들(#63700007, #63700020, #63700036) 및 일부 공개된 풀이들을 사용해 실험했을 때 균등 분포 랜덤 데이터에 비해 1.9~3.3배의 성능 하락을 일으켰습니다.

현재 데이터에서는 큰 수를 우선적으로 처리할수록 시간 측정에서 유리하며, 위에서 언급한 성능 하락 역시 이런 풀이들에서 두드러집니다. 이 데이터를 추가해 이런 bias를 완화했으면 좋겠습니다.

startlink   3년 전

재채점했습니다.

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