Windows XP는 초기 사용자 사진을 어떤 알고리듬으로 골랐을까?

• 계정 생성 시 초기 사용자 사진은 Default Pictures 디렉터리에 있는 사진 중 하나를 무작위로 골라 사용함
• 난수 생성에는 RtlRandomEx 를 쓰며, GetTickCount()의 현재 값으로 초기 시드를 설정함
• 선택 방식은 저수지 샘플링(reservoir sampling) 의 k = 1 특수 사례로, 한 번 순회하면서 n번째 사진을 만날 때마다 1/n 확률로 선택을 교체함
• 파일 수를 세고 다시 순회하는 방식보다 파일 시스템 호출이 적으며, 실행 도중 디렉터리의 파일 수가 바뀌어도 두 순회 사이의 불일치를 처리할 필요가 없음
• 사진 100개를 샘플링하면 중단하므로, 디렉터리에 파일을 100만 개 넣는 극단적인 상황에서도 처리량이 과도해지는 것을 방지함

사진 후보와 난수 생성

• 초기 사용자 사진은 %ALLUSERSPROFILE%\Application Data\Microsoft\User Account Pictures\Default Pictures에 있는 사진 가운데 무작위로 선택함
• 난수 생성기는 RtlRandomEx 이며, 초기 시드는 GetTickCount()의 현재 값임

한 번의 순회로 무작위 선택

• 저수지 샘플링 에서 k = 1인 경우를 사용하며, 하나만 뽑는 조건 덕분에 알고리듬을 단순화할 수 있음
  • 항목 수를 세는 count는 0, 현재 선택을 저장하는 winner는 null로 초기화함
  • 다음 항목을 읽을 때마다 count를 늘리고, 1부터 count까지의 균등 난수가 count와 같으면 winner를 현재 항목으로 교체함
  • 순회를 마치면 winner를 반환함
• 선택 원리의 핵심은 마지막 항목의 선택 확률이 1/n 이라는 점임
  • 항목이 하나뿐이면 반드시 그 항목을 선택함
  • 항목이 n개라면 앞의 n − 1개에서 무작위로 고른 선택을 유지하되, 1/n 확률로 n번째 항목으로 교체함
  • 마지막 항목을 선택하지 않는 경우는 앞의 n − 1개에서 무작위로 고르는 문제로 줄일 수 있음
• 단일 순회는 전체 항목 수를 세고, 1부터 n 사이의 번호를 뽑은 뒤 해당 위치를 찾으러 다시 순회하는 방식보다 효율적임
  • 병목인 파일 시스템 호출이 줄어듦
  • 코드 실행 중 디렉터리의 파일 수가 달라져도 두 번의 순회 사이에서 발생하는 복잡성을 피할 수 있음
• 안전장치로 사진 100개를 샘플링한 뒤 중단하며, Default Pictures 디렉터리에 파일을 100만 개 넣는 등의 극단적인 상황에 대비함