윈도우 XP 초기 사용자 사진 선택 알고리즘 분석
What algorithm did Windows XP use to choose your initial user picture?
Hacker NewsWindows XP가 초기 사용자 프로필 사진을 선택하는 알고리즘이 밝혀졌습니다. 이 과정은 시스템 시간을 시드로 사용하는 `RtlRandomEx` 난수 생성기를 활용합니다.
- 핵심 원리는 '원 패스 무작위 선택' 방식입니다. 이는 파일 시스템 접근 횟수를 최소화하여 효율성을 높이고 실행 중 디렉터리 변화에도 안정적입니다.
- 오래된 운영체제의 내부 동작 원리를 분석하는 것은 알고리즘 최적화와 OS 설계에 대한 깊은 통찰을 제공하며 개발자들에게 중요한 학습 자료가 됩니다.
- 대용량 디렉터리에서도 안정성을 유지하기 위해, 이 알고리즘은 샘플링할 사진 수를 최대 100장으로 제한하는 안전 장치를 갖추고 있습니다.
Windows XP는 사용자의 초기 프로필 사진을 `%ALLUSERSPROFILE%\Application Data\마이크로소프트\User Account Pictures\Default Pictures` 디렉터리에 있는 사진들 중에서 무작위로 선택합니다. 이 과정에서 난수 생성기(RNG)로는 `GetTickCount()`의 현재 값을 시드로 사용하는 `RtlRandomEx` 함수가 활용됩니다.
사진을 선택하는 핵심 원리는 '원 패스 무작위 선택 알고리즘'입니다. 이는 리저버 샘플링의 특수한 경우이며, 기존의 항목 개수를 세어 난수 인덱스를 찾는 방식보다 효율적이라는 장점이 있습니다. 이 방식은 파일 시스템 호출 횟수를 줄여 병목 현상을 완화하고, 코드가 실행되는 동안 디렉터리 내 파일 수가 변경되어도 안정적으로 작동합니다.
알고리즘의 동작 원리는 재귀적인 구조를 가집니다. 항목이 n개일 경우, 먼저 처음 n-1개의 항목 중 하나를 무작위로 선택한 후, 나머지 n번째 항목을 1/n 확률로 선택하는 방식으로 진행됩니다. 또한, 이 코드는 안전 장치로 최대 100장의 사진만 샘플링하도록 제한하여, 디렉터리에 수백만 개의 파일이 존재할 경우 발생할 수 있는 비정상적인 동작을 방지합니다.