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]

... 46  47  48  49  50  51  52  53  54  55  56  57  [58]  59  60  ...
NoWriterDateCnt.TitleFile(s)
12580정성태3/28/202120623오류 유형: 708. SQL Server Management Studio - Execution Timeout Expired.
12579정성태3/28/202121388오류 유형: 707. 중첩 가상화(Nested Virtualization) - The virtual machine could not be started because this platform does not support nested virtualization.
12578정성태3/27/202122052개발 환경 구성: 560. Docker Desktop for Windows 기반의 Kubernetes 구성 (2) - WSL 2 인스턴스에 kind가 구성한 k8s 서비스 위치
12577정성태3/26/202122758개발 환경 구성: 559. Docker Desktop for Windows 기반의 Kubernetes 구성 - WSL 2 인스턴스에 kind 도구로 k8s 클러스터 구성
12576정성태3/25/202121490개발 환경 구성: 558. Docker Desktop for Windows에서 DockerDesktopVM 기반의 Kubernetes 구성 (2) - k8s 서비스 위치
12575정성태3/24/202120508개발 환경 구성: 557. Docker Desktop for Windows에서 DockerDesktopVM 기반의 Kubernetes 구성 [1]
12574정성태3/23/202125883.NET Framework: 1030. C# Socket의 Close/Shutdown 동작 (동기 모드)
12573정성태3/22/202123075개발 환경 구성: 556. WSL 인스턴스 초기 설정 명령어 [1]
12572정성태3/22/202122236.NET Framework: 1029. C# - GC 호출로 인한 메모리 압축(Compaction)을 확인하는 방법파일 다운로드1
12571정성태3/21/202119389오류 유형: 706. WSL 2 기반으로 "Enable Kubernetes" 활성화 시 초기화 실패 [1]
12570정성태3/19/202126174개발 환경 구성: 555. openssl - CA로부터 인증받은 새로운 인증서를 생성하는 방법
12569정성태3/18/202125753개발 환경 구성: 554. WSL 인스턴스 export/import 방법 및 단축 아이콘 설정 방법
12568정성태3/18/202118282오류 유형: 705. C# 빌드 - Couldn't process file ... due to its being in the Internet or Restricted zone or having the mark of the web on the file.
12567정성태3/17/202121546개발 환경 구성: 553. Docker Desktop for Windows를 위한 k8s 대시보드 활성화 [1]
12566정성태3/17/202121158개발 환경 구성: 552. Kubernetes - kube-apiserver와 REST API 통신하는 방법 (Docker Desktop for Windows 환경)
12565정성태3/17/202117793오류 유형: 704. curl.exe 실행 시 dll not found 오류
12564정성태3/16/202118474VS.NET IDE: 160. 새 프로젝트 창에 C++/CLI 프로젝트 템플릿이 없는 경우
12563정성태3/16/202121411개발 환경 구성: 551. C# - JIRA REST API 사용 정리 (3) jira-oauth-cli 도구를 이용한 키 관리
12562정성태3/15/202121540개발 환경 구성: 550. C# - JIRA REST API 사용 정리 (2) JIRA OAuth 토큰으로 API 사용하는 방법파일 다운로드1
12561정성태3/12/202120662VS.NET IDE: 159. Visual Studio에서 개행(\n, \r) 등의 제어 문자를 치환하는 방법 - 정규 표현식 사용
12560정성태3/11/202122154개발 환경 구성: 549. ssh-keygen으로 생성한 PKCS#1 개인키/공개키 파일을 각각 PKCS8/PEM 형식으로 변환하는 방법
12559정성태3/11/202122792.NET Framework: 1028. 닷넷 5 환경의 Web API에 OpenAPI 적용을 위한 NSwag 또는 Swashbuckle 패키지 사용 [2]파일 다운로드1
12558정성태3/10/202121681Windows: 192. Power Automate Desktop (Preview) 소개 - Bitvise SSH Client 제어 [1]
12557정성태3/10/202119747Windows: 191. 탐색기의 보안 탭에 있는 "Object name" 경로에 LEFT-TO-RIGHT EMBEDDING 제어 문자가 포함되는 문제
12556정성태3/9/202116621오류 유형: 703. PowerShell ISE의 Debug / Toggle Breakpoint 메뉴가 비활성 상태인 경우
12555정성태3/8/202121341Windows: 190. C# - 레지스트리에 등록된 DigitalProductId로부터 라이선스 키(Product Key)를 알아내는 방법파일 다운로드2
... 46  47  48  49  50  51  52  53  54  55  56  57  [58]  59  60  ...