Microsoft MVP성태의 닷넷 이야기
.NET Framework: 276. 중복 없는 숫자를 랜덤으로 배열하는 방법 [링크 복사], [링크+제목 복사],
조회: 50014
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 1개 있습니다.)

중복 없는 숫자를 랜덤으로 배열하는 방법

데브피아에서 재미있는 질문이 있었군요. ^^

계산량 문제좀 질문 드리겠습니다. - 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위는 했습니다. 무조건 코드가 짧다고 해서 성능이 좋은 것은 아닌 것 같습니다. ^^

이야기는 여기까지가 끝이고... 혹시 더 좋은 알고리즘이 생각나시는 분 계신가요? ^^

(첨부된 파일은 위의 코드를 포함한 예제 프로젝트입니다.)




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]






[최초 등록일: ]
[최종 수정일: 6/22/2021]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 



2011-12-09 02시53분
[당근천국] 4번방법에 값을 출력시킨후 출력된 자리에 배열의 맨마지막 값을 넣은후 랜덤구하는 범위를 하나 줄여서 구현하는 방법도 있습니다.
ㅎㅎㅎ

이 글을 토대로 테스트 프로그램을 만들어 보았습니다.
제가 말한 방법에 대한 자세한 설명도 해두었습니다.
http://blog.danggun.net/791
[guest]
2011-12-09 04시22분
방법이 정말 여러가지로 나오는 군요. ^^ 메모리를 2배로 쓴다는 작은 단점만 빼면 제시하신 방법 6도 괜찮은 것 같습니다.
정성태
2012-01-02 10시18분
[게스트] 저런걸 random suffle이라고 하죠
http://blog.naver.com/ezkun78/30071908611
요 링크 재밌네요
[guest]
2012-01-15 11시08분
[yeti] 제가 원하는 함수인데, 재미있게 봤습니다. 꾸뻑^^
[guest]
2023-03-17 10시29분
.NET 8부터 Random.Shuffle이 제공됩니다.

Random.Shuffle Method
; https://learn.microsoft.com/en-us/dotnet/api/system.random.shuffle
정성태

1  2  3  4  5  6  [7]  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
13466정성태11/29/20232665닷넷: 2175. C# - DllImport 메서드의 AOT 지원을 위한 LibraryImport 옵션
13465정성태11/28/20232420개발 환경 구성: 689. MSBuild - CopyToOutputDirectory가 "dotnet publish" 시에는 적용되지 않는 문제파일 다운로드1
13464정성태11/28/20232527닷넷: 2174. C# - .NET 7부터 UnmanagedCallersOnly 함수 export 기능을 AOT 빌드에 통합파일 다운로드1
13463정성태11/27/20232429오류 유형: 881. Visual Studio - NU1605: Warning As Error: Detected package downgrade
13462정성태11/27/20232430오류 유형: 880. Visual Studio - error CS0246: The type or namespace name '...' could not be found
13461정성태11/26/20232507닷넷: 2173. .NET Core 3/5+ 기반의 COM Server를 registry 등록 없이 사용하는 방법파일 다운로드1
13460정성태11/26/20232446닷넷: 2172. .NET 6+ 기반의 COM Server 내에 Type Library를 내장하는 방법파일 다운로드1
13459정성태11/26/20232482닷넷: 2171. .NET Core 3/5+ 기반의 COM Server를 기존의 regasm처럼 등록하는 방법파일 다운로드1
13458정성태11/26/20232488닷넷: 2170. .NET Core/5+ 기반의 COM Server를 tlb 파일을 생성하는 방법(tlbexp)
13457정성태11/25/20232381VS.NET IDE: 187. Visual Studio - 16.9 버전부터 추가된 "Display inline type hints" 옵션
13456정성태11/25/20232724닷넷: 2169. C# - OpenAI를 사용해 PDF 데이터를 대상으로 OpenAI 챗봇 작성 [1]파일 다운로드1
13455정성태11/25/20232625닷넷: 2168. C# - Azure.AI.OpenAI 패키지로 OpenAI 사용파일 다운로드1
13454정성태11/23/20232927닷넷: 2167. C# - Qdrant Vector DB를 이용한 Embedding 벡터 값 보관/조회 (Azure OpenAI) [1]파일 다운로드1
13453정성태11/23/20232380오류 유형: 879. docker desktop 설치 시 "Invalid JSON string. (Exception from HRESULT: 0x83750007)"
13452정성태11/22/20232490닷넷: 2166. C# - Azure OpenAI API를 이용해 사용자가 제공하는 정보를 대상으로 검색하는 방법파일 다운로드1
13451정성태11/21/20232616닷넷: 2165. C# - Azure OpenAI API를 이용해 ChatGPT처럼 동작하는 콘솔 응용 프로그램 제작파일 다운로드1
13450정성태11/21/20232421닷넷: 2164. C# - Octokit을 이용한 GitHub Issue 검색파일 다운로드1
13449정성태11/21/20232537개발 환경 구성: 688. Azure OpenAI 서비스 신청 방법
13448정성태11/20/20232876닷넷: 2163. .NET 8 - Dynamic PGO를 결합한 성능 향상파일 다운로드1
13447정성태11/16/20232749닷넷: 2162. ASP.NET Core 웹 사이트의 SSL 설정을 코드로 하는 방법
13446정성태11/16/20232702닷넷: 2161. .NET Conf 2023 - Day 1 Blazor 개요 정리
13445정성태11/15/20233025Linux: 62. 리눅스/WSL에서 CA 인증서를 저장하는 방법
13444정성태11/15/20232746닷넷: 2160. C# 12 - Experimental 특성 지원
13443정성태11/14/20232788개발 환경 구성: 687. OpenSSL로 생성한 사용자 인증서를 ASP.NET Core 웹 사이트에 적용하는 방법
13442정성태11/13/20232557개발 환경 구성: 686. 비주얼 스튜디오로 실행한 ASP.NET Core 사이트를 WSL 2 인스턴스에서 https로 접속하는 방법
13441정성태11/12/20232940닷넷: 2159. C# - ASP.NET Core 프로젝트에서 서버 Socket을 직접 생성하는 방법파일 다운로드1
1  2  3  4  5  6  [7]  8  9  10  11  12  13  14  15  ...