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]

... 91  92  93  94  95  96  97  98  99  100  101  102  [103]  104  105  ...
NoWriterDateCnt.TitleFile(s)
11394정성태12/8/201719428개발 환경 구성: 342. 비주얼 스튜디오에서 실행하던 ASP.NET Core (.NET Framework) 응용 프로그램을 명령행에서 실행하는 방법
11393정성태12/7/201724607Windows: 145. 윈도우 10 빌드 17046부터 WSL에서 백그라운드 작업 지원 [5]
11392정성태12/7/201719090개발 환경 구성: 341. openSUSE에 닷넷 코어 설치
11391정성태12/7/201722140개발 환경 구성: 340. WSL을 이용해 윈도우 PC 1대에서 openSUSE 응용 프로그램을 Visual Studio로 개발하는 방법 [1]
11390정성태12/7/201731050개발 환경 구성: 339. WSL을 이용해 윈도우 PC 1대에서 Linux 응용 프로그램을 Visual Studio로 개발하는 방법 [6]
11389정성태12/7/201719714오류 유형: 440. .NET Core 오류 - 0x80131620 Unable to load DLL 'libuv'
11388정성태12/6/201723530개발 환경 구성: 338. WSL 또는 Ubuntu에 닷넷 코어 설치 [3]
11387정성태12/6/201723438오류 유형: 439. 이벤트 로그 - Data Sharing Service 서비스의 %%3239247874 오류 메시지
11386정성태12/5/201719477오류 유형: 438. Hyper-V - '...' failed to add device 'Virtual CD/DVD Disk'
11385정성태12/5/201732627VC++: 121. DXGI를 이용한 윈도우 화면 캡처 소스 코드(Visual C++) [16]파일 다운로드1
11384정성태12/5/201722087오류 유형: 437. Visual C++ - Cannot open include file: 'SDKDDKVer.h'
11383정성태12/4/201724691디버깅 기술: 110. 비동기 코드 실행 중 예외로 인한 ASP.NET 프로세스 비정상 종료 현상 [1]
11382정성태12/4/201723674오류 유형: 436. System.Data.SqlClient.SqlException (0x80131904): Connection Timeout Expired 예외 발생 시 "[Pre-Login] initialization=48; handshake=1944;" 값의 의미
11381정성태11/30/201720234.NET Framework: 702. 한글이 포함된 바이트 배열을 나눈 경우 한글이 깨지지 않도록 다시 조합하는 방법(두 번째 이야기)파일 다운로드1
11380정성태11/30/201720235디버깅 기술: 109. windbg - (x64에서의 인자 값 추적을 이용한) Thread.Abort 시 대상이 되는 스레드를 식별하는 방법
11379정성태11/30/201719963오류 유형: 435. System.Web.HttpException - Session state has created a session id, but cannot save it because the response was already flushed by the application.
11378정성태11/29/201721850.NET Framework: 701. 한글이 포함된 바이트 배열을 나눈 경우 한글이 깨지지 않도록 다시 조합하는 방법 [1]파일 다운로드1
11377정성태11/29/201721436.NET Framework: 700. CommonOpenFileDialog 사용 시 사용자가 선택한 파일 목록을 구하는 방법 [3]파일 다운로드1
11376정성태11/28/201726144VS.NET IDE: 123. Visual Studio 편집기의 \r\n (crlf) 개행을 \n으로 폴더 단위로 설정하는 방법
11375정성태11/28/201719894오류 유형: 434. Visual Studio로 ASP.NET 디버깅 중 System.Web.HttpException - Could not load type 오류
11374정성태11/27/201725899사물인터넷: 14. 라즈베리 파이 - (윈도우의 NT 서비스처럼) 부팅 시 시작하는 프로그램 설정 [1]
11373정성태11/27/201724889오류 유형: 433. Raspberry Pi/Windows 다중 플랫폼 지원 컴파일 관련 오류 기록
11372정성태11/25/201727420사물인터넷: 13. 윈도우즈 사용자를 위한 라즈베리 파이 제로 W 모델을 설정하는 방법 [4]
11371정성태11/25/201721237오류 유형: 432. Hyper-V 가상 스위치 생성 시 Failed to connect Ethernet switch port 0x80070002 오류 발생
11370정성태11/25/201721459오류 유형: 431. Hyper-V의 Virtual Switch 생성 시 "External network" 목록에 특정 네트워크 어댑터 항목이 없는 경우
11369정성태11/25/201723189사물인터넷: 12. Raspberry Pi Zero(OTG)를 다른 컴퓨터에 연결해 가상 키보드 및 마우스로 쓰는 방법 (절대 좌표, 상대 좌표, 휠) [1]
... 91  92  93  94  95  96  97  98  99  100  101  102  [103]  104  105  ...