Microsoft MVP성태의 닷넷 이야기
.NET Framework: 276. 중복 없는 숫자를 랜덤으로 배열하는 방법 [링크 복사], [링크+제목 복사],
조회: 50351
글쓴 사람
정성태 (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)
13632정성태5/20/2024206Phone: 17. C# MAUI - Android 내에 Web 서비스 호스팅
13631정성태5/19/2024250Phone: 16. C# MAUI - /Download 등의 공용 디렉터리에 접근하는 방법
13630정성태5/19/2024402닷넷: 2263. C# - Thread가 Task보다 더 빠르다는 어떤 예제(?)
13629정성태5/18/2024480개발 환경 구성: 710. Android - adb.exe를 이용한 파일 전송
13628정성태5/17/2024436개발 환경 구성: 709. Windows - WHPX(Windows Hypervisor Platform)를 이용한 Android Emulator 가속
13627정성태5/17/2024449오류 유형: 903. 파이썬 - UnicodeEncodeError: 'ascii' codec can't encode character '...' in position ...: ordinal not in range(128)
13626정성태5/15/2024635Phone: 15. C# MAUI - MediaElement Source 경로 지정 방법파일 다운로드1
13625정성태5/14/20241052닷넷: 2262. C# - Exception Filter 조건(when)을 갖는 catch 절의 IL 구조
13624정성태5/12/20241221Phone: 14. C# - MAUI에서 MediaElement 사용파일 다운로드1
13623정성태5/11/20241299닷넷: 2261. C# - 구글 OAuth의 JWT (JSON Web Tokens) 해석파일 다운로드1
13622정성태5/10/20241288닷넷: 2260. C# - Google 로그인 연동 (ASP.NET 예제)파일 다운로드1
13621정성태5/10/20241187오류 유형: 902. IISExpress - Failed to register URL "..." for site "..." application "/". Error description: Cannot create a file when that file already exists. (0x800700b7)
13620정성태5/9/20241231VS.NET IDE: 190. Visual Studio가 node.exe를 경유해 Edge.exe를 띄우는 경우
13619정성태5/7/20241183닷넷: 2259. C# - decimal 저장소의 비트 구조파일 다운로드1
13618정성태5/6/20241292닷넷: 2258. C# - double (배정도 실수) 저장소의 비트 구조파일 다운로드1
13617정성태5/5/20241244닷넷: 2257. C# - float (단정도 실수) 저장소의 비트 구조파일 다운로드1
13616정성태5/3/20241187닷넷: 2256. ASP.NET Core 웹 사이트의 HTTP/HTTPS + Dual mode Socket (IPv4/IPv6) 지원 방법파일 다운로드1
13615정성태5/3/20241133닷넷: 2255. C# 배열을 Numpy ndarray 배열과 상호 변환
13614정성태5/2/20241092닷넷: 2254. C# - COM 인터페이스의 상속 시 중복으로 메서드를 선언
13613정성태5/1/20241117닷넷: 2253. C# - Video Capture 장치(Camera) 열거 및 지원 포맷 조회파일 다운로드1
13612정성태4/30/20241140오류 유형: 902. Visual Studio - error MSB3021: Unable to copy file
13611정성태4/29/20241142닷넷: 2252. C# - GUID 타입 전용의 UnmanagedType.LPStruct - 두 번째 이야기파일 다운로드1
13610정성태4/28/20241200닷넷: 2251. C# - 제네릭 인자를 가진 타입을 생성하는 방법 - 두 번째 이야기
13609정성태4/27/20241250닷넷: 2250. PInvoke 호출 시 참조 타입(class)을 마샬링하는 [IN], [OUT] 특성파일 다운로드1
13608정성태4/26/20241353닷넷: 2249. C# - 부모의 필드/프로퍼티에 대해 서로 다른 자식 클래스 간에 Reflection 접근이 동작할까요?파일 다운로드1
[1]  2  3  4  5  6  7  8  9  10  11  12  13  14  15  ...