성태님의 글을 보다가 '겹치지 않는 랜덤값'을 구하는 알고리즘에 대해 쓸 글을 보았습니다.
성태님의 홈페이지 - 중복없는 숫자를 랜덤으로 배열하는 방법
저도 예전에 '숫자야구'와 '로또 번호 생성기' 때문에 이 알고리즘에 대한 생각을 많이 했었습니다.
지금은 클래스 화 시켜놨죠.
저 글을 보면서 느낌 점은 '기존 세대'와 '객체지향 세대'의 갭이였습니다 ㅡ,.ㅡ;
제가 이 알고리즘을 만들 때만 해도 리스트나 해쉬 같은건 생각도 못 했는데 말이죠 ㅎㅎㅎㅎ
어찌됐건 성태님의 글의 방법1~5번까지 숙지하시면 이 포스팅을 읽는 데 도움이 됩니다.
(안 읽어도 크게 지장은 없습니다.ㅎㅎㅎ)
편의상 제가 만든 알고리즘을 '방법 6'이라고 하겠습니다.
1. '방법6' 이해하기
겹치지 않는 숫자를 배열하려면 순서가 이렇습니다.
1) 순서대로 배열을 만든다.
2) 랜덤값을 구한다.
3) 구한 랜덤값에 위치하는 값을 출력한다.
4) 구한 랜덤값의 위치에 배열의 맨 마지막 값을 넣는다.
5) 구하는 랩덤값의 범위를 한 칸 줄인다.
입니다.
그림으로 표현하자면
이렇게 됩니다.
이 알고리즘의 장점은 빠르고 어떤 언어에도 호환된다는 점입니다.
문법만 살짝살짝 만지면 아무 데서나 다 사용이 가능합니다.
2. 구현
구현 방법은 간단합니다.
C# 기준으로 아래와 같습니다.
public int[] Renew(
int nStart
, int nEnd
, int nCount)
{
//랜덤 개체
Random rand = new Random();
//추출된 숫자를 저장하는 배열
int[] arrResult = new int[nCount];
//추출할 원본 생성
int[] listOri = Enumerable.Range(nStart, nEnd).ToArray();
//추출한 인덱스
int idxGetCount = 0;
//추출할 범위
int nRandRange = nEnd - nStart;
for (int i = 0; i < nEnd; i++)
{
//숫자 추출
idxGetCount = rand.Next(nRandRange);
//추출한 숫자 저장
arrResult[i] = listOri[idxGetCount];
//추출한 자리에 마지막 숫자를 이동시키고
//추출할 범위를 한칸 줄인다.
listOri[idxGetCount] = listOri[--nRandRange];
}
return arrResult;
}
3. 속도 비교
체크 박스에 1~5번까지는 성태님의 글에 나와 있는 것이고 6번이 제가 이 글에서 쓴 방법입니다.
다른 방법들과 비교해도 괜찮은 속도가 나오고 있습니다.
아래 예제로 테스트할 수 있습니다.
각 원하는 방법을 채크하면 체크한것만 출력됩니다.
너무 큰 숫자를 넣으면 브라우저가 다운된 것 처럼 보일 수 있으니 주의하세요.
각자 컴퓨터 환경이나 사양에 따라 속도 차가 발생할 수 있습니다.
정확한 테스트를 원하시면 10번 이상 500000이상의 값으로 체크를 하시기 바랍니다.
'출력'을 눌렀을 때 다른 작업을 하지 않아야 정확한 값이 나옵니다.
마무리
알고리즘 자체 문제도 있지만 이런류의 알고리즘은 기존 메모리를 정리하느냐 안 하느냐에 따라서 속도 차이가 많이 발생합니다.
긴 시간 을 두고 사용해야 한다면 매번 정리하는 것이 좋겠고 한 번에 많이 추출할때는 정리를 하지 않는 것이 유리하죠.
상황에 맞춰서 위 방법의 하나를 선택해서 쓰면 됩니다.
