중복 없는 숫자를 랜덤으로 배열하는 방법
데브피아에서 재미있는 질문이 있었군요. ^^
계산량 문제좀 질문 드리겠습니다. - Random함수 관련
; http://www.devpia.com/MAEUL/Contents/Detail.aspx?BoardID=17&MAEULNO=8&no=141505&ref=141505
이야기를 정리하자면, a[50000] 배열이 있는데 이 안에 0 ~ 49999까지의 숫자를 중복되지 않게 random으로 배치하고 싶다는 것입니다.
우선, 질문자가 스스로 한 답변을 한번 볼까요?
=== [방법 1] ===
List<int> Area = Enumerable.Range(0, 50000).ToList();
Random rand = new Random((int)DateTime.Now.Ticks);
List<int> list = new List<int>(50000);
for (int i = 0; i < Area.Count; i++)
{
int num = rand.Next(Area.Count);
int num2 = Area[num];
Area.RemoveAt(num);
list.Add(num2);
}
Stopwatch로 시간을 재어보면, ElapsedMilliseconds == 418이 걸립니다. 자, 이것이 느린 걸까요? 빠른 걸까요?
계속해서 "계산량 문제좀 질문 드리겠습니다. - Random함수 관련" 글의 마지막 답변을 보면 다음과 같은 해결책이 나옵니다.
=== [방법 2] ===
List<int> lstChk = new List<int>(50000);
for(int i = 0; i < lstChk.Capacity; i++)
{
Random rd = new Random()
int iChk = rd.Next(lstChk.Capacity);
while(true)
{
if(lstChk.Contains(iChk) == false)
{
lstChk.Add(iChk);
break;
}
else
{
iChk = rd.Next(lstChk.Capacity);
}
}
}
답변자 스스로도 쓰고 있지만 2분이 넘게 걸린다고 합니다. 말할 필요도 없이 "[방법 1]"이 "[방법 2]"보다 낫습니다.
그런데, '방법 2'에는 상당한 비효율이 있습니다. 즉, List에 담아 놓고 Contains 비교를 하기 때문에 O(n)의 검색 시간이 걸리는 것입니다. 따라서, 이 시간을 줄이면 될 텐데요. 간단하게 HashSet으로 바꿔서 구현하면 비약적으로 성능이 향상됩니다.
=== [방법 3] ===
HashSet<int> rands = new HashSet<int>();
Random rand = new Random((int)DateTime.Now.Ticks);
while (true)
{
int number = rand.Next(50000);
if (rands.Contains(number) == false)
{
rands.Add(number);
if (rands.Count == 50000)
{
break;
}
}
}
검색 시간이 이제는 O(1)로 바뀌었으니 당연히 성능향상이 기대되는데요. 실제로 Stopwatch로 구해 보면 ElapsedMilliseconds == 68이 나오니 오히려 이제는 "방법 1"보다도 7배 정도나 빨라졌습니다.
그런데, '방법 3'에도 단점이 있습니다. 바로 시간이 지날수록 비어있는 자리들이 줄어들어서 충돌 횟수가 꽤나 잦아진다는 것입니다. 그런 시간은 그야말로 확률적으로 시간을 소비하게 됩니다.
다행히도, "계산량 문제좀 질문 드리겠습니다. - Random함수 관련" 글의 이원진 님 답변 글에 보면 재미있는 방법이 하나 제시됩니다.
"
만약 1부터 10까지의 숫자를 뽑아야 한다면 배열을 만들어 1부터 10까지 순서대로 넣는다.
그 배열을 랜덤하게 섞는다.
배열 왼쪽부터 뽑고싶은 갯수만큼 뽑는다.
"
위와 같이만 해준다면 충돌 횟수가 줄어들기 때문에 속도가 더욱 빨라질 수 있을 텐데요. 이를 실제로 코드로 구현해 보면 다음과 같겠지요. ^^
=== [방법 4] ===
Random rand = new Random((int)DateTime.Now.Ticks);
int[] list = Enumerable.Range(0, 50000).ToArray();
int idx, old;
for (int i = 0; i < 50000; i++)
{
idx = rand.Next(50000);
old = list[i];
list[i] = list[idx];
list[idx] = old;
}
시간을 구해 보면, ElapsedMilliseconds == 4로 가장 빠른 시간을 보여줍니다. 그런데, '방법 4'와 '방법 1'을 잠시 비교해 보시겠어요?
=== [방법 1] ===
List<int> Area = Enumerable.Range(0, 50000).ToList();
Random rand = new Random((int)DateTime.Now.Ticks);
List<int> list = new List<int>(50000);
for (int i = 0; i < Area.Count; i++)
{
int num = rand.Next(Area.Count);
int num2 = Area[num];
Area.RemoveAt(num);
list.Add(num2);
}
아이디어 면에서 보면 '방법 1'도 충돌이 발생하지 않기 때문에 괜찮아 보이지만, 어째서 '방법 4'와 비교해서 100배 가깝게 낮은 성능을 보이는 걸까요? 문제는 Area.RemoveAt에 있습니다. 특정 index 지점의 요소를 삭제하고 그 이하의 메모리를 앞으로 복사시키는 작업이 포함되기 때문에 엄청난 오버헤드가 발생하는 것입니다. 이 때문에 배열의 요소가 늘어날수록 '방법 1'의 오버헤드가 심각해집니다.
예를 들어 50000 * 2로 요소 수를 늘리면 시간은 다음과 같이 차이가 납니다.
방법 1: 1657 (4배 증가)
방법 2: 120 (2배 증가)
방법 3: 8 (2배 증가)
좀 더 검색을 해보니, 더욱 재미있는 방법이 나오는군요. ^^
LINQ Enumerable 클래스, 1부
; https://docs.microsoft.com/ko-kr/archive/msdn-magazine/2008/july/advanced-basics-the-linq-enumerable-class-part-1
다음과 같이, 코드가 굉장히 간단하게 나옵니다.
=== [방법 5] ===
Random rand = new Random((int)DateTime.Now.Ticks);
int[] list = Enumerable.Range(0, 50000).OrderBy(o => rand.Next()).ToArray();
그런데, 실행 시간은 ElapsedMilliseconds == 42로 '방법 3'에 비하면 좋지 않지만 그래도 2위는 했습니다. 무조건 코드가 짧다고 해서 성능이 좋은 것은 아닌 것 같습니다. ^^
이야기는 여기까지가 끝이고... 혹시 더 좋은 알고리즘이 생각나시는 분 계신가요? ^^
(
첨부된 파일은 위의 코드를 포함한 예제 프로젝트입니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]