시드 세팅에 따른 성능 비교

quick sort 성능 테스트 중 랜덤 피봇에대한 성능 저하가 심각했었는데 시드를 매 반복마다 초기화할때 얼마나 느려지는지에 대해서 실제 테스트를 했었던 수치이다.

1. 고정 인덱스

퀵소트 테스트 돌리는데 피봇으로 고정 인덱스 박아넣으면 소팅하는 정렬상태는 비중복 값으로 완전랜덤으로 섞여있음

n = 10000000

2. 여기서 매 파티션마다 시드값을 새로 줄경우에

1
2
3
std::mt19937_64 rng;
rng.seed(std::random_device()());
std::uniform_int_distribution<int>distribution(start, end)

n = 1000000 첫번째보다 n은 10배 작음.

3. 시드생성을 전역에

다음코드를 전역과 메인함수에 넣고,

1
2
std::mt19937_64 rng;
rng.seed(std::random_device()());

1
std::uniform_int_distribution<int>distribution(start, end)

이것만 재귀에 넣어서 구했을때 n은 두번째와 동일