Microsoft MVP성태의 닷넷 이야기
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
(연관된 글이 1개 있습니다.)

C# - 재귀호출을 스택 자료구조와 반복문을 이용해 대체하는 방법을 Paralle.For와 함께?

아래의 글에 대해,

C# - 재귀호출을 스택 자료구조와 반복문을 이용해 대체하는 방법 
; https://www.sysnet.pe.kr/2/0/1599

Parallel.For를 이용한 재귀호출에도 사용이 가능하냐는 질문이 있었습니다. 예제로 보내온 소스코드는 다음과 같은데요.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MonteCarlo
{
    class Program
    {
        static void Main(string[] args)
        {
            double dblSt = 0, dblEn = 0;

            Console.Write("Input the Start and End Value for Integration: ");
            string strBuff = Console.ReadLine();

            string[] strParams = strBuff.Split(' ');
            dblSt = double.Parse(strParams[0]);
            dblEn = double.Parse(strParams[1]);

            double dblInt = MonteCarloIntegral((x) =>
            {
                return (x + Math.Sin(x));
            }, dblSt, dblEn);
            Console.WriteLine("The Integration Result = {0}", dblInt);

            Console.ReadKey();
        }

        static double MonteCarloIntegral(Func<double, double> Func, double Init, double Fin)
        {
            double dblVolume = Fin - Init, dblIntg = 0;

            if (dblVolume <= 0.05) // Monte Carlo Integration: I = integral f(x) dx = (1/n) * Sum(i = 1 to n) f(x[i])
            {
                Random rndRand = new Random(100);
                long lngTrial = 10000 * ((long) ((Func(Fin) - Func(Init)) / dblVolume) + 1);

                for (long cnt = 0; cnt < lngTrial; cnt++) // Using I = integral f(x) dx = integral f(x(t)) * dx(t)/dt dt
                {
                    double dblRand = rndRand.NextDouble();
                    double dblReal = Math.Sqrt((dblRand * dblVolume * (Fin + Init)) + Math.Pow(Init, 2)); 
                    dblIntg += (Math.Pow(Fin, 2) - Math.Pow(Init, 2)) * Func(dblReal) / (2 * dblReal);
                }

                dblIntg /= lngTrial;
            }
            else
            {
                double[] dblPartSums = new double[8]; 
                double dblPartVol = dblVolume / dblPartSums.Length; 

                Parallel.For(0, dblPartSums.Length, (cnt) =>
                {
                    double dblStart = Init + (cnt * dblPartVol), dblEnd = Init + ((cnt + 1) * dblPartVol); 
                    dblPartSums[cnt] = MonteCarloIntegral(Func, dblStart, dblEnd);
                });

                dblIntg += dblPartSums.Sum();
            }

            return dblIntg;
        }
    }
}

정말 가능한지... 한번 해볼까요? ^^

우선, 예제 코드를 쉽게 이해할 수 있도록 병렬처리를 원래의 for 루프로 돌려놓겠습니다.

double[] dblPartSums = new double[8]; 
double dblPartVol = dblVolume / dblPartSums.Length; 

for (cnt i = 0; cnt < dblPartSums.Length; cnt ++)
{
    double dblStart = Init + (cnt * dblPartVol), dblEnd = Init + ((cnt + 1) * dblPartVol); 
    dblPartSums[cnt] = MonteCarloIntegral(Func, dblStart, dblEnd);
}

dblIntg += dblPartSums.Sum();

그럼, 이제 그다지 어렵지 않게 Stack + 반복문 유형으로 바꿀 수 있습니다.

public struct SnapShotStruct
{
    public double Init;
    public double Fin;

    public double dblVolume;
    public double dblIntg;

    public int stage;
}

static double MonteCarloIntegralLoop(Func<double, double> Func, double Init, double Fin)
{
    double retVal = 0.0;

    Stack<SnapShotStruct> snapshotStack = new Stack<SnapShotStruct>();

    SnapShotStruct currentSnapshot = new SnapShotStruct();
    currentSnapshot.Init = Init;
    currentSnapshot.Fin = Fin;

    currentSnapshot.dblVolume = 0;
    currentSnapshot.dblIntg = 0;

    currentSnapshot.stage = 0;

    snapshotStack.Push(currentSnapshot);

    while (snapshotStack.Count != 0)
    {
        currentSnapshot = snapshotStack.Pop();

        switch (currentSnapshot.stage)
        {
            case 0:
                currentSnapshot.dblVolume = currentSnapshot.Fin - currentSnapshot.Init;

                if (currentSnapshot.dblVolume <= 0.05)
                {
                    Random rndRand = new Random(100);
                    long lngTrial = 10000 * ((long)((Func(currentSnapshot.Fin) - Func(currentSnapshot.Init)) / currentSnapshot.dblVolume) + 1);

                    for (long cnt = 0; cnt < lngTrial; cnt++)
                    {
                        double dblRand = rndRand.NextDouble();
                        double dblReal = Math.Sqrt((dblRand * currentSnapshot.dblVolume * (currentSnapshot.Fin + currentSnapshot.Init)) + Math.Pow(currentSnapshot.Init, 2));
                        currentSnapshot.dblIntg += (Math.Pow(currentSnapshot.Fin, 2) - Math.Pow(currentSnapshot.Init, 2)) * Func(dblReal) / (2 * dblReal);
                    }

                    currentSnapshot.dblIntg /= lngTrial;

                    retVal += currentSnapshot.dblIntg;
                    continue;
                }

                currentSnapshot.stage = 1;
                snapshotStack.Push(currentSnapshot);

                int length = 8;
                double dblPartVol = currentSnapshot.dblVolume / length;

                for (int i = 0; i < length; i++)
                {
                    double dblStrt = currentSnapshot.Init + (i * dblPartVol);
                    double dblEnd = currentSnapshot.Init + ((i + 1) * dblPartVol);

                    SnapShotStruct newSnapShot = new SnapShotStruct();
                    newSnapShot.Init = dblStrt;
                    newSnapShot.Fin = dblEnd;
                    newSnapShot.stage = 0;

                    snapshotStack.Push(newSnapShot);
                }
                break;

            case 1:
                retVal = currentSnapshot.dblIntg + retVal;
                continue;
        }
    }

    return retVal;
}

Stack + 반복문으로 구현된 이 코드를 이제 원래의 Parallel.For로 돌려보면 어떻게 될까요?

int length = 8;
double dblPartVol = currentSnapshot.dblVolume / length;

Parallel.For(0, length, (idx) =>
{
    double dblStrt = currentSnapshot.Init + (idx * dblPartVol);
    double dblEnd = currentSnapshot.Init + ((idx + 1) * dblPartVol);

    SnapShotStruct newSnapShot = new SnapShotStruct();
    newSnapShot.Init = dblStrt;
    newSnapShot.Fin = dblEnd;
    newSnapShot.stage = 0;

    snapshotStack.Push(newSnapShot);
});

별 쓸모가 없죠? ^^ 물론 이렇게 바꾼다고 해서 해답이 달라지는 것은 아닙니다. 하지만, 재귀호출을 Stack + 반복문으로 고치는 것 자체가 함수 호출을 리스트 형식으로 직렬화하는 것과 유사하기 때문에 Parallel.For를 호출하는 것도 역시 목록에 포함시켜 다음에 실행하도록 스케쥴링하는 것에 불과하므로 그다지 효용성이 없습니다.

만약 위의 코드를 굳이 병렬화 되도록 고쳐야 한다면 Parallel.For 내의 코드를 별도의 함수 처리로 바꿔야 하고 이는 다시 메서드의 재귀호출로 이어지기 때문에 결국 바꾸기 전과 후의 차이가 없게 됩니다.

그나저나, 이번 질문을 통해서 새롭게 알게 되는군요. 재귀호출이 loop 내에서 불려지는 경우, 재귀호출 방법으로는 병렬화가 가능하지만 Stack + 반복문으로 처리하는 경우 병렬화 처리가 무의미하다는 것!

(위의 처리 코드는 첨부 파일에 넣어두었으니 참고하세요.)




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

[연관 글]






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

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

비밀번호

댓글 작성자
 



2014-01-20 04시07분
[자유주의] 오호~^^ 루프 내에서의 스택 + 반복문 처리는 병렬화가 무의미하군요. 저 코드를 비재귀적으로 바꿀 수 있을까 하고 고민을 했는데, 비로소 답을 알게 되었네요.^^ 정말로 감사합니다.^^
[guest]

... 76  77  78  79  80  [81]  82  83  84  85  86  87  88  89  90  ...
NoWriterDateCnt.TitleFile(s)
12001정성태8/10/201929411.NET Framework: 852. WPF/WinForm에서 UWP의 기능을 이용해 Bluetooth 기기와 Pairing하는 방법 [1]
12000정성태8/9/201928722.NET Framework: 851. WinForm/WPF에서 Console 창을 띄워 출력하는 방법파일 다운로드1
11999정성태8/1/201921458오류 유형: 563. C# - .NET Core 2.0 이하의 Unix Domain Socket 사용 시 System.IndexOutOfRangeException 오류
11998정성태7/30/201924531오류 유형: 562. .NET Remoting에서 서비스 호출 시 SYN_SENT로 남는 현상파일 다운로드1
11997정성태7/30/201922942.NET Framework: 850. C# - Excel(을 비롯해 Office 제품군) COM 객체를 제어 후 Excel.exe 프로세스가 남아 있는 문제 [2]파일 다운로드1
11996정성태7/25/201926078.NET Framework: 849. C# - Socket의 TIME_WAIT 상태를 없애는 방법파일 다운로드1
11995정성태7/23/201931674.NET Framework: 848. C# - smtp.daum.net 서비스(Implicit SSL)를 이용해 메일 보내는 방법 [2]
11994정성태7/22/201924698개발 환경 구성: 454. Azure 가상 머신(VM)에서 SMTP 메일 전송하는 방법파일 다운로드1
11993정성태7/22/201919315오류 유형: 561. Dism.exe 수행 시 "Error: 2 - The system cannot find the file specified." 오류 발생
11992정성태7/22/201921630오류 유형: 560. 서비스 관리자 실행 시 "Windows was unable to open service control manager database on [...]. Error 5: Access is denied." 오류 발생
11991정성태7/18/201919007디버깅 기술: 128. windbg - x64 환경에서 닷넷 예외가 발생한 경우 인자를 확인할 수 없었던 사례
11990정성태7/18/201920217오류 유형: 559. Settings / Update & Security 화면 진입 시 프로그램 종료
11989정성태7/18/201919165Windows: 162. Windows Server 2019 빌드 17763부터 Alt + F4 입력시 곧바로 로그아웃하는 현상
11988정성태7/18/201923396개발 환경 구성: 453. 마이크로소프트가 지정한 모든 Root 인증서를 설치하는 방법
11987정성태7/17/201929595오류 유형: 558. 윈도우 - KMODE_EXCEPTION_NOT_HANDLED 블루스크린(BSOD) 문제 [1]
11986정성태7/17/201921224오류 유형: 557. 드라이브 문자를 할당하지 않은 파티션을 탐색기에서 드라이브 문자와 함께 보여주는 문제
11985정성태7/17/201920667개발 환경 구성: 452. msbuild - csproj에 환경 변수 조건 사용 [1]
11984정성태7/9/201929047개발 환경 구성: 451. Microsoft Edge (Chromium)을 대상으로 한 Selenium WebDriver 사용법 [1]
11983정성태7/8/201918025오류 유형: 556. nodemon - 'mocha' is not recognized as an internal or external command, operable program or batch file.
11982정성태7/8/201917824오류 유형: 555. Visual Studio 빌드 오류 - result: unexpected exception occured (-1002 - 0xfffffc16)
11981정성태7/7/201921648Math: 64. C# - 3층 구조의 신경망(분류)파일 다운로드1
11980정성태7/7/201930920개발 환경 구성: 450. Visual Studio Code의 Java 확장을 이용한 간단한 프로젝트 구축파일 다운로드1
11979정성태7/7/201922377개발 환경 구성: 449. TFS에서 gitlab/github등의 git 서버로 마이그레이션하는 방법
11978정성태7/6/201921998Windows: 161. 계정 정보가 동일하지 않은 PC 간의 인증을 수행하는 방법 [1]
11977정성태7/6/201925888오류 유형: 554. git push - error: RPC failed; HTTP 413 curl 22 The requested URL returned error: 413 Request Entity Too Large
11976정성태7/4/201920937오류 유형: 553. (잘못 인증 한 후) 원격 git repo 재인증 시 "remote: HTTP Basic: Access denied" 오류 발생
... 76  77  78  79  80  [81]  82  83  84  85  86  87  88  89  90  ...