이 문제는 fread나 mmap 등의 충분히 빠른 입력 방법을 적용하고 나면 입력을 파싱하는 과정이 실행 시간에서 큰 비중을 차지하게 됩니다. 이때 파싱 전략의 설계 및 구현, 그리고 입력 데이터의 구성에 따라 성능이 달라지는데, 현재 모든 데이터의 답이 2×1013 이상인 것으로 볼 때(#63701001) 모든 데이터가 균등 분포에 따라 랜덤하게 생성되었거나 큰 수로만 이루어진 것으로 추측됩니다.
아래 제너레이터로 생성되는 데이터는 각 자릿수가 모두 균등하게 등장하며, 제가 작성한 풀이들(#63700007, #63700020, #63700036) 및 일부 공개된 풀이들을 사용해 실험했을 때 균등 분포 랜덤 데이터에 비해 1.9~3.3배의 성능 하락을 일으켰습니다.
현재 데이터에서는 큰 수를 우선적으로 처리할수록 시간 측정에서 유리하며, 위에서 언급한 성능 하락 역시 이런 풀이들에서 두드러집니다. 이 데이터를 추가해 이런 bias를 완화했으면 좋겠습니다.
doju 3년 전 4
(07-18 23:15 본문 재작성)
이 문제는
fread나mmap등의 충분히 빠른 입력 방법을 적용하고 나면 입력을 파싱하는 과정이 실행 시간에서 큰 비중을 차지하게 됩니다. 이때 파싱 전략의 설계 및 구현, 그리고 입력 데이터의 구성에 따라 성능이 달라지는데, 현재 모든 데이터의 답이 2×1013 이상인 것으로 볼 때(#63701001) 모든 데이터가 균등 분포에 따라 랜덤하게 생성되었거나 큰 수로만 이루어진 것으로 추측됩니다.아래 제너레이터로 생성되는 데이터는 각 자릿수가 모두 균등하게 등장하며, 제가 작성한 풀이들(#63700007, #63700020, #63700036) 및 일부 공개된 풀이들을 사용해 실험했을 때 균등 분포 랜덤 데이터에 비해 1.9~3.3배의 성능 하락을 일으켰습니다.
현재 데이터에서는 큰 수를 우선적으로 처리할수록 시간 측정에서 유리하며, 위에서 언급한 성능 하락 역시 이런 풀이들에서 두드러집니다. 이 데이터를 추가해 이런 bias를 완화했으면 좋겠습니다.