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]

... 106  107  108  109  110  111  112  113  114  115  116  [117]  118  119  120  ...
NoWriterDateCnt.TitleFile(s)
11036정성태8/29/201625839개발 환경 구성: 297. 소스 코드가 없는 닷넷 어셈블리를 디버깅할 때 지역 변숫값을 확인하는 방법
11035정성태8/29/201621780오류 유형: 354. .NET Reflector - PDB 생성 화면에서 "Clear Store"를 하면 "Index and length must refer to a location within the string" 예외 발생
11034정성태8/25/201625849개발 환경 구성: 296. .NET Core 프로젝트를 NuGet Gallery에 배포하는 방법 [2]
11033정성태8/24/201623827오류 유형: 353. coreclr 빌드 시 error C3249: illegal statement or sub-expression for 'constexpr' function
11032정성태8/23/201623049개발 환경 구성: 295. 최신의 Visual C++ 컴파일러 도구를 사용하는 방법 [1]
11031정성태8/23/201618996오류 유형: 352. Error encountered while pushing to the remote repository: Response status code does not indicate success: 403 (Forbidden).
11030정성태8/23/201622231VS.NET IDE: 111. Team Explorer - 추가한 Git Remote 저장소가 Branch에 보이지 않는 경우
11029정성태8/18/201629531.NET Framework: 602. Process.Start의 cmd.exe에서 stdin만 redirect 하는 방법 [1]파일 다운로드1
11028정성태8/15/201622466오류 유형: 351. Octave 설치 시 JRE 경로 문제
11027정성태8/15/201624266.NET Framework: 601. ElementHost 컨트롤의 메모리 누수 현상
11026정성태8/13/201625417Math: 19. 행렬 연산으로 본 해밍코드
11025정성태8/12/201624342개발 환경 구성: 294. .NET Core 프로젝트에서 "Copy to Output Directory" 처리 [1]
11024정성태8/12/201623461오류 유형: 350. "nProtect GameMon" 실행 중에는 Visual Studio 디버깅이 안됩니다! [1]
11023정성태8/10/201625038개발 환경 구성: 293. Azure 구독 후 PaaS 서비스 만들어 보기
11022정성태8/10/201625712개발 환경 구성: 292. Azure Cloud Service 배포시 사용자 정의 작업을 추가하는 방법
11021정성태8/10/201622835오류 유형: 349. System.Runtime.Remoting.RemotingException - Type '..., ..., Version=..., Culture=neutral, PublicKeyToken=null' is not registered for activation [2]
11020정성태8/10/201625754VC++: 98. 원본과 대상 버퍼가 같은 경우 memcpy, wmemcpy 주의점
11019정성태8/10/201642391기타: 60. 도서: 시작하세요! C# 6.0 프로그래밍: 기본 문법부터 실전 예제까지 (2쇄 정오표)
11018정성태8/9/201626457.NET Framework: 600. 단일 메서드 내에서의 할당으로 알아보는 자바와 닷넷의 GC 차이점 [1]
11017정성태8/9/201627731웹: 33. HTTP 쿠키에 한글 값을 설정하는 방법
11016정성태8/7/201625918개발 환경 구성: 291. Windows Server Containers 소개
11015정성태8/7/201624243오류 유형: 348. Windows Server 2016 TP5에서 Windows Containers의 docker run 실행 시 encountered an error during Start failed in Win32
11014정성태8/6/201624948오류 유형: 347. Hyper-V Virtual Machine Management service Account does not have permission to open attachment
11013정성태8/6/201635778개발 환경 구성: 290. Windows 10에서 경험해 보는 Windows Containers와 docker [4]
11012정성태8/6/201625858오류 유형: 346. Windows 10에서 Windows Containers의 docker run 실행 시 encountered an error during CreateContainer failed in Win32 발생
11011정성태8/6/201627308기타: 59. outlook.live.com 메일 서비스의 아웃룩 POP3 설정하는 방법
... 106  107  108  109  110  111  112  113  114  115  116  [117]  118  119  120  ...